from Hacker News

Who invented vector clocks?

by rntz on 4/9/23, 8:35 PM with 39 comments

• by gwern on 4/9/23, 9:49 PM

  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...)

• by ChuckMcM on 4/9/23, 10:20 PM

  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.

• by hinkley on 4/9/23, 9:48 PM

  > 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.

• by nitwit005 on 4/10/23, 5:33 AM

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

• by vivegi on 4/11/23, 6:16 AM

  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

• by uvdn7 on 4/10/23, 1:23 AM

  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?

• by dboreham on 4/10/23, 3:26 AM

  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 ;)

• by baryphonic on 4/10/23, 12:05 PM

  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

• by infogulch on 4/9/23, 9:16 PM

  It depends on your reference frame...

• by IIAOPSW on 4/10/23, 12:38 AM

  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.

• by gslin on 4/9/23, 10:06 PM

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

• by DantesKite on 4/10/23, 3:27 AM

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

• by sublinear on 4/9/23, 9:28 PM

  > 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.