Who invented vector clocks? | Hacker News Reader

Who invented vector clocks?

decomposition.al

125 pointsrntz39 comments

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

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.

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.

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.

Even worse when it is not just some random credits but patent.

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.

I'd wager that the first person to mention an idea in a publication is almost never the originator of the idea. The obstacles for publishing something are so enormously high that the effort to publish is often much larger than the effort to invent the thing being published.

As a result, academia and industrial science are largely institutions that formalize and describe ideas, not institutions where ideas originate, even though those ideas are often (wrongly) attributed to them.

It's even worse in the humanities, of course. I can pretty much guarantee that no philosophical idea was first conceived by the person it is usually attributed to. Most of those ideas are ultimately so trivial that countless people probably had them in the Stone Age already.

The obstacles for publishing something today are pretty much nil. Just put it on your website, or on the arXiv. If you put it on your website, make sure that you can prove later on what you put there when (https://en.wikipedia.org/wiki/Trusted_timestamping).

Self-publishing doesn't count as "publishing" for most purposes. Trying to claim academic priority based on something you uploaded to your website or the arXiv is a recipe for getting laughed at, or, even more likely, for getting ignored outright. At least outside of those very few fields where the arXiv has become somewhat established, like math, computer science, and to a lesser extent, physics.

arXiv isn’t a great cite. It’s like “technical report”, and it doesn’t really count for points so much as it is a courtesy provided to the reader (well, the only real points that should matter).

I once dug out the invention of IDE code completion coming from a structured programming system called Alice Pascal from the mid 80s via a magazine article. That was a fun investigation, but no one really cared.

Sounds interesting, maybe write a paper about it?

I did! Onward 2010 I think. It was a fun paper. Escape from the maze of twisty classes.

2012! https://www.microsoft.com/en-us/research/publication/escape-...

You can (and should) always go for some more respected form of publishing afterwards, especially if you need points for academia. But if you were first, and you didn't document that properly, and you couldn't get it published in any "respectable" form, guess who is laughing now? If the arXiv is good enough for Perelman, it is good enough for me.

Of course, a certain amount of immunity to social values is helpful here.

One problem with this approach though is the "double-blind review" policy of some prestigious publications. If your stuff is on the arXiv, it's difficult to double-blind it. One of the reasons why I think double-blind is a bad idea.

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.

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

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

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

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?

In the work place a manager will heroically claim credit.

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.

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

https://xkcd.com/664/

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

It depends on your reference frame...

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

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.

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?

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.

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

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

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

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

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.

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.

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

> [...] for most topics I think many would rather see no article than a crap one.

I'm sure that many people would support just the opposite. And in the case of Wikipedia, it is even more probable: the first person who finds the weak points in an article can (and often does) add comments (or - nowadays - opinions on the discussion page), which usually instigate discussion and corrections.

Of course, in the case of scientific articles, the practices are different, and your statement holds. However, IMO Wikipedia only struggles to get as close as possible to the role of a real encyclopedia, and definitely isn't (and won't be) Asimov's Encyclopedia Galactica.

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

I’ve contributed code to a few open source projects…this is true for exactly zero of them — blender, at least, tried to have accurate python documentation.

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

Reply on news.ycombinator.com