6 ms·

Who invented vector clocks?

125 points by rntz 3y ago

DantesKite 3y ago
I like how the Wikipedia entry for this still hasn't been updated.
infogulch 3y ago
It depends on your reference frame...
- topaz0 3y ago
  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).
  - iudqnolq 3y ago
    But (taking the joke closer towards absurdity) when using vector timestamps independent actions by people not communicating with each other don't have a well-defined order.
    - eru 3y ago
      That's true, but I'm not sure you call that point of view a 'reference frame'? And some of them seem to have talked?
sublinear 3y ago
> 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 3y ago
  > 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?
  - lallysingh 3y ago
    Have you tried a simple edit of an article? It'll get reverted under a reference to some policy that links to some giant body of in-group norms for Wiki.
    - threatofrain 3y ago
      Yes, my math and CS edits on Wikipedia tend to be durable, sometimes more durable than I'd like as I would've wanted a professional in the field to take over. It took me a few hours over the course of a week to appreciate the collection of pros and cons which keeps technical Wikipedia to be what it is.
  - sublinear 3y ago
    > 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. The accuracy of an article depends on the effort (or ability) for contributors to check facts more than its "density of interest". In other words, experts find this easier than amateurs, and for most topics I think many would rather see no article than a crap one. Also worth a conjecture that the interest in writing cannot possibly always be equal to the interest in reading for all topics. If true this is perhaps the ugliest aspect of Wikipedia. > Programming docs in open source often have errors. Do the volunteers not deserve the "privilege" of offering their time for free? This is a non sequitur and I don't think I can answer it. What I will say is that the code review process for a pull request usually includes making sure docs are updated accordingly. Much of that documentation might even be automatically generated from structured comments and validated by passing tests such as in API docs. Humans still of course review after that which mistakes even less likely especially since everyone involved is writing about their own work.
hinkley 3y ago
> 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.
gwern 3y ago
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/parker83detection.pdf https://pages.cs.wisc.edu/~remzi/Classes/739/Papers/parker83... , it sounds more like they are reverse-engineering why LOCUS works...)
- wolfram74 3y ago
  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.
- eru 3y ago
  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.
- mathisfun123 3y ago
  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.
  - ilyt 3y ago
    Even worse when it is not just some random credits but patent.
gslin 3y ago
It's interesting to see someone trying to decide the invention clock in the real world...
ChuckMcM 3y ago
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.
IIAOPSW 3y ago
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.
uvdn7 3y ago
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 3y ago
  In the work place a manager will heroically claim credit.
  - hvmonk 3y ago
    If that happens, raise it his boss. If that doesn't work and you feel like vomiting on your mgr's face, do it. Don't hold back.
dboreham 3y ago
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 3y ago
  https://xkcd.com/664/ https://xkcd.com/664/
nitwit005 3y ago
I get the feeling this was written specifically to have something to cite in a wikipedia correction.
baryphonic 3y ago
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 https://dl.acm.org/doi/book/10.5555/889815
vivegi 3y ago
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 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 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 https://lamport.azurewebsites.net/pubs/pubs.html#time-clocks

125 points by rntz 3y ago

DantesKite 3y ago

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

infogulch 3y ago

It depends on your reference frame...

topaz0 3y ago
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).
- iudqnolq 3y ago
  But (taking the joke closer towards absurdity) when using vector timestamps independent actions by people not communicating with each other don't have a well-defined order.
  - eru 3y ago
    That's true, but I'm not sure you call that point of view a 'reference frame'? And some of them seem to have talked?

sublinear 3y ago

> 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 3y ago
> 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?
- lallysingh 3y ago
  Have you tried a simple edit of an article? It'll get reverted under a reference to some policy that links to some giant body of in-group norms for Wiki.
  - threatofrain 3y ago
    Yes, my math and CS edits on Wikipedia tend to be durable, sometimes more durable than I'd like as I would've wanted a professional in the field to take over. It took me a few hours over the course of a week to appreciate the collection of pros and cons which keeps technical Wikipedia to be what it is.
- sublinear 3y ago
  > 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. The accuracy of an article depends on the effort (or ability) for contributors to check facts more than its "density of interest". In other words, experts find this easier than amateurs, and for most topics I think many would rather see no article than a crap one. Also worth a conjecture that the interest in writing cannot possibly always be equal to the interest in reading for all topics. If true this is perhaps the ugliest aspect of Wikipedia. > Programming docs in open source often have errors. Do the volunteers not deserve the "privilege" of offering their time for free? This is a non sequitur and I don't think I can answer it. What I will say is that the code review process for a pull request usually includes making sure docs are updated accordingly. Much of that documentation might even be automatically generated from structured comments and validated by passing tests such as in API docs. Humans still of course review after that which mistakes even less likely especially since everyone involved is writing about their own work.

hinkley 3y ago

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

gwern 3y ago

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/parker83detection.pdf https://pages.cs.wisc.edu/~remzi/Classes/739/Papers/parker83... , it sounds more like they are reverse-engineering why LOCUS works...)

wolfram74 3y ago
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.
eru 3y ago
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.
mathisfun123 3y ago
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.
- ilyt 3y ago
  Even worse when it is not just some random credits but patent.

gslin 3y ago

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

ChuckMcM 3y ago

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.

IIAOPSW 3y ago

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.

uvdn7 3y ago

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 3y ago
In the work place a manager will heroically claim credit.
- hvmonk 3y ago
  If that happens, raise it his boss. If that doesn't work and you feel like vomiting on your mgr's face, do it. Don't hold back.

dboreham 3y ago

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 3y ago
https://xkcd.com/664/ https://xkcd.com/664/

nitwit005 3y ago

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

baryphonic 3y ago

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 https://dl.acm.org/doi/book/10.5555/889815

vivegi 3y ago

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 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 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 https://lamport.azurewebsites.net/pubs/pubs.html#time-clocks