TE
科技回声
首页24小时热榜最新最佳问答展示工作
GitHubTwitter
首页

科技回声

基于 Next.js 构建的科技新闻平台,提供全球科技新闻和讨论内容。

GitHubTwitter

首页

首页最新最佳问答展示工作

资源链接

HackerNews API原版 HackerNewsNext.js

© 2025 科技回声. 版权所有。

Who invented vector clocks?

125 点作者 rntz大约 2 年前

13 条评论

gwern大约 2 年前
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 &amp; Mattern for credit for &#x27;developing the <i>theory</i>&#x27;, that&#x27;s fine. But notice, that&#x27;s not how it started and is an answer to a different - no one was asking, &#x27;who finally explained why vector clocks work in a rigorous way&#x27;, the very title is &#x27;who <i>invented</i> vector clocks&#x27; (repeated in the first sentence, and in various forms thereafter as &#x27;system...developed&#x27;, &#x27;introduced&#x27;, &#x27;idea...developed&#x27;, etc), and she objects to WP describing her as uncovering who really &#x27;invented&#x27; vector clocks. The actual answer to her question would seem to be Parker 1983. (And looking at the description of &#x27;LOCUS&#x27; in <a href="https:&#x2F;&#x2F;pages.cs.wisc.edu&#x2F;~remzi&#x2F;Classes&#x2F;739&#x2F;Papers&#x2F;parker83detection.pdf" rel="nofollow">https:&#x2F;&#x2F;pages.cs.wisc.edu&#x2F;~remzi&#x2F;Classes&#x2F;739&#x2F;Papers&#x2F;parker83...</a> , it sounds more like they are reverse-engineering why LOCUS works...)
评论 #35509500 未加载
评论 #35508610 未加载
评论 #35508843 未加载
评论 #35508776 未加载
ChuckMcM大约 2 年前
Vector clocks are pretty neat. I didn&#x27;t invent them but I used a crude approximation when I was designing what was to become NIS+ at Sun Microsystems.<p>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.<p>As a systems problem I really enjoyed the challenge.
hinkley大约 2 年前
&gt; The idea of vector timestamps was developed independently by Ladin and Liskov [LL86].<p>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大约 2 年前
I get the feeling this was written specifically to have something to cite in a wikipedia correction.
vivegi大约 2 年前
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 <a href="https:&#x2F;&#x2F;lamport.azurewebsites.net&#x2F;pubs&#x2F;time-clocks.pdf" rel="nofollow">https:&#x2F;&#x2F;lamport.azurewebsites.net&#x2F;pubs&#x2F;time-clocks.pdf</a><p>Lamport cites<p>&gt; The origin of this paper was the note <i>The Maintenance of Duplicate Databases</i> 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.<p>The Maintenance of Duplicate Databases, Paul Johnson and Bob Thomas (1975). <a href="https:&#x2F;&#x2F;www.rfc-archive.org&#x2F;getrfc.php?rfc=677" rel="nofollow">https:&#x2F;&#x2F;www.rfc-archive.org&#x2F;getrfc.php?rfc=677</a><p>Leslie Lamport&#x27;s website link to Time Clocks. <a href="https:&#x2F;&#x2F;lamport.azurewebsites.net&#x2F;pubs&#x2F;pubs.html#time-clocks" rel="nofollow">https:&#x2F;&#x2F;lamport.azurewebsites.net&#x2F;pubs&#x2F;pubs.html#time-clocks</a>
uvdn7大约 2 年前
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.<p>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?<p>Do people know who else claims to invent HLC first?
评论 #35510257 未加载
dboreham大约 2 年前
Whoever it was I guarantee they didn&#x27;t publish an academic paper. They shipped their product, then probably spent a few years fixing convergence bugs ;)
评论 #35510203 未加载
baryphonic大约 2 年前
David Reed&#x27;s 1978 PhD thesis describes &quot;pseudo-time,&quot; which is a precursor to the work Liskov and Lamport did.[0] (Reed calls his overall system he developed &quot;NAMOS,&quot; 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&#x27;s PAXOS is a sort of pun on NAMOS.<p>[0]<a href="https:&#x2F;&#x2F;dl.acm.org&#x2F;doi&#x2F;book&#x2F;10.5555&#x2F;889815" rel="nofollow">https:&#x2F;&#x2F;dl.acm.org&#x2F;doi&#x2F;book&#x2F;10.5555&#x2F;889815</a>
infogulch大约 2 年前
It depends on your reference frame...
评论 #35507218 未加载
IIAOPSW大约 2 年前
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&#x27;s at least a half dozen people who had that exact idea around the dawn of the distributed system.
gslin大约 2 年前
It&#x27;s interesting to see someone trying to decide the invention clock in the real world...
DantesKite大约 2 年前
I like how the Wikipedia entry for this still hasn&#x27;t been updated.
sublinear大约 2 年前
&gt; 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.<p>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&#x27;t deserve the privilege to do that work.
评论 #35506800 未加载
评论 #35509165 未加载