Who invented vector clocks?

[gwern]

This is a good example of how academic citation practices subtly launder out the role of compute, trial-and-error, and practitioners in favor of academia. OP concludes that if you want to cite Fidge & Mattern for credit for 'developing the theory', that's fine. But notice, that's not how it started and is an answer to a different - no one was asking, 'who finally explained why vector clocks work in a rigorous way', the very title is 'who invented vector clocks' (repeated in the first sentence, and in various forms thereafter as 'system...developed', 'introduced', 'idea...developed', etc), and she objects to WP describing her as uncovering who really 'invented' vector clocks. The actual answer to her question would seem to be Parker 1983. (And looking at the description of 'LOCUS' in https://pages.cs.wisc.edu/~remzi/Classes/739/Papers/parker83... , it sounds more like they are reverse-engineering why LOCUS works...)

[seanmcdirmid]

Even “who was the first person to mention X in a publication” can be different from “who invented X”. Inventions can fly around the industry for awhile before they get documented, and it is unclear who really invented them, or perhaps they were invented multiple times independently.

[wolfram74]

In free wheeling evolutionary processes, seeing that a process works is enough, but when some level of intentionality can be applied, I feel the group that explains /why/ a process works can offer more to the community for improvement, or realize when all the gains have been found and new avenues must be pursued.

[mathisfun123]

this is absolutely the opposite how the citation game works - very often the first person to hit the buzzer gets all the credit and the people that come after and actually give a clean, rigorous, expository treatment gets absolutely zero credit/cites.

[eru]

This reminds me a bit of the relationship between the inventors of various steam engines, and the then fledging science of thermodynamics that sprang up to explain them.

[ChuckMcM]

Vector clocks are pretty neat. I didn't invent them but I used a crude approximation when I was designing what was to become NIS+ at Sun Microsystems.

Given the problem that you want to accept updates to a database at multiple servers but cannot guarantee that all of those servers have the same notion of time and thus creating an accurate mutation vector that leaves the state of the database consistent, NIS+ used a tuple of (update, secondary-server-time) which the primary could query the secondary and compute a time delta (positive or negative) that would allow it to sort updates to the same database entry from multiple secondaries into a primary relative time order. It could then apply the updates and produce deltas for all secondaries which would apply any necessary changes to their database.

As a systems problem I really enjoyed the challenge.

[hinkley]

> The idea of vector timestamps was developed independently by Ladin and Liskov [LL86].

A few years ago when I ended up down the rabbit hole on CRDTs and alternatives I learned of Liskov’s work on time vectors, which is still my top “things you didn’t know about Barbara Liskov” fact.

[nitwit005]

I get the feeling this was written specifically to have something to cite in a wikipedia correction.

[vivegi]

Time, Clocks and the Ordering of Events in a Distributed System. Communications of the ACM 21, 7 (July 1978), 558-565. Reprinted in several collections, including Distributed Computing: Concepts and Implementations, McEntire et al., ed. IEEE Press, 1984. PDF https://lamport.azurewebsites.net/pubs/time-clocks.pdf

Lamport cites

> The origin of this paper was the note The Maintenance of Duplicate Databases by Paul Johnson and Bob Thomas. I believe their note introduced the idea of using message timestamps in a distributed algorithm. I happen to have a solid, visceral understanding of special relativity (see [5]). This enabled me to grasp immediately the essence of what they were trying to do.

The Maintenance of Duplicate Databases, Paul Johnson and Bob Thomas (1975). https://www.rfc-archive.org/getrfc.php?rfc=677

Leslie Lamport's website link to Time Clocks. https://lamport.azurewebsites.net/pubs/pubs.html#time-clocks

[uvdn7]

The same happens in work place as well, when multiple people have similar ideas and it is unclear or impossible to credit who came up with the idea first. It is often the case that people with shared context had similar ideas independently when facing the same set of problems.

I have the impression that it is controversial about who invented the hybrid logical clock first as well. Although most people cite the Kulkani paper from 2015 I think?

Do people know who else claims to invent HLC first?

[nitwit005]

In the work place a manager will heroically claim credit.

[dboreham]

Whoever it was I guarantee they didn't publish an academic paper. They shipped their product, then probably spent a few years fixing convergence bugs ;)

[a_e_k]

https://xkcd.com/664/

[baryphonic]

David Reed's 1978 PhD thesis describes "pseudo-time," which is a precursor to the work Liskov and Lamport did.[0] (Reed calls his overall system he developed "NAMOS," with pseudo-time being the coordination mechanism.) In fact, the pseudo-time algorithm has some flaws which Liskov described in the mid-80s. I believe Lamport's PAXOS is a sort of pun on NAMOS.

[0]https://dl.acm.org/doi/book/10.5555/889815

[infogulch]

It depends on your reference frame...

[topaz0]

Unlikely: assuming all of the authors of the various papers were on earth at the time, the spacetime intervals separating their discoveries were almost certainly timelike, in which case there is no ambiguity in their ordering. Unless they were within a few ms of each other (in the earth's reference frame).

[IIAOPSW]

I mean, if you have multiple different parties each of which might have a slightly different, out of sync copy of a shared reality, the first and most obvious representation of state you could have is just list them all out. Obviously there's at least a half dozen people who had that exact idea around the dawn of the distributed system.

[gslin]

It's interesting to see someone trying to decide the invention clock in the real world...

[DantesKite]

I like how the Wikipedia entry for this still hasn't been updated.

[sublinear]

> So, the current version of the Wikipedia page on vector clocks is wrong, or at least misleading, about the origin of the idea, and it’s kind of my fault.

No. 0% fault of the author and 100% the fault of the Wikipedia editor. Generally speaking, people who are unwilling to ensure the accuracy of their work don't deserve the privilege to do that work.

[threatofrain]

> Generally speaking, people who are unwilling to ensure the accuracy of their work don't deserve the privilege to do that work.

This is all volunteer labor. Anyone can be a volunteer if they'd like. Wikipedia encourages mistakes (or "boldness") and assumes that due to a network of volunteers and the density of interest, an article will eventually become better.

Programming docs in open source often have errors. Do the volunteers not deserve the "privilege" of offering their time for free?

[pcshah1996]

As usual, a (semi-)relevant xkcd: https://xkcd.com/978/ (Citogenesis)