[HN Gopher] Who Invented Vector Clocks?
___________________________________________________________________
Who Invented Vector Clocks?
Author : rntz
Score : 35 points
Date : 2023-04-09 20:35 UTC (2 hours ago)
(HTM) web link (decomposition.al)
(TXT) w3m dump (decomposition.al)
| ChuckMcM wrote:
| 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 wrote:
| > 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.
| infogulch wrote:
| It depends on your reference frame...
| topaz0 wrote:
| 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).
| gwern wrote:
| 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...)
| sublinear wrote:
| > 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 wrote:
| > 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?
| gslin wrote:
| It's interesting to see someone trying to decide the invention
| clock in the real world...
___________________________________________________________________
(page generated 2023-04-09 23:00 UTC)