Lindsey Kuper

Back in spring 2020, I was wrapping up the distributed systems course I was teaching, and for the last lecture, decided to spend a little time poking at the question of who actually invented vector clocks. Most people who need something to cite for vector clocks cite Friedemann Mattern’s “Virtual Time and Global States of Distributed Systems”, dated 1989 (although the workshop at which it originally appeared apparently actually took place in 1988), and Colin Fidge’s “Timestamps in Message-Passing Systems That Preserve the Partial Ordering”, dated 1988.1 (The done thing is to cite both Fidge and Mattern, who apparently worked independently without knowledge of each other’s work on the topic, though Mattern does cite Fidge in the version of his paper dated 1989.)

I wanted to dig further. I noticed that Kshemkalyani and Singhal’s 2011 distributed systems textbook (see also Kshemkalyani’s web page for the book) also cited a third source:

The system of vector clocks was developed independently by Fidge [4], Mattern [12], and Schmuck [23].

Citations 4 and 12 are the aforementioned Fidge and Mattern papers, respectively. Looking up citation 23 brings us to Frank Schmuck’s 1988 Cornell Ph.D. dissertation. The PDF hosted by Cornell doesn’t seem to be searchable, but here’s a version that is. If we search for the word “vector” in there, we find:

In [Lam78] Lamport introduced logical timestamps, integers assigned to each event in such a way that if all events are ordered by their timestamp this order is consistent with “→”. We can generalize this idea to timestamps which are vectors of integers [Sch85].

The “Lam78” citation is of course Lamport’s 1978 paper “Time, Clocks, and the Ordering of Events in a Distributed System”, which didn’t introduce vector clocks; the logical clocks in that paper, which we now know as Lamport clocks, are scalars, not vectors. The tantalizing “Sch85” citation is:

[Sch85] F. Schmuck. Software clocks and the order of events in a distributed system. Unpublished manuscript, November 1985.

So Schmuck is citing his own unpublished manuscript from 1985 as the place vector clocks came from. Well, then. But wait! Schmuck also includes a footnote:

The idea of vector timestamps was developed independently by Ladin and Liskov [LL86].

Here “LL86” is a pointer to Barbara Liskov and Rivka Ladin’s PODC 1986 paper “Highly available distributed services and fault-tolerant distributed garbage collection”. The word “vector” doesn’t occur in it, but if we dig in a little, we find that the logical timestamps they describe in section 2.2 indeed sound just like vector clocks:

We solve this problem by using multipart timestamps, where there is one part for each replica. Thus if there are n replicas, a timestamp t is

t = ⟨t1, …, tn⟩

where each part is a positive integer. Since there will typically be a small number of replicas (e.g., 3 to 7), using such a timestamp is practical.

A replica generates a new timestamp by incrementing its part of its timestamp by one, while leaving all other parts unchanged. Since each part can be advanced by only a single replica, we guarantee that the resulting timestamps are unique. Some timestamps can be compared: For two timestamps t1 and t2, t1 ≤ t2 provided t1i ≤ t2i for each part i of the timestamp. Other timestamps are incomparable. Two timestamps t1 and t2 are merged by retaining the larger value for each part; as required, the result of the merge is ≥ t1 and t2.

That’s kind of where the citation trail dried up, and I didn’t feel like digging around further, so I told my spring 2020 class that the Liskov and Ladin ‘86 paper was the oldest paper I could find in the literature that discussed vector clocks. (If you care to see the part of my lecture where I talked about this, it’s a long-winded ~25-minute journey starting at about 18:50 in this video. But really, if you read all of the above, you won’t get much more out of watching the video.)

Now, I didn’t go so far as to claim that Liskov and Ladin were actually first; I didn’t claim to have an authoritative answer to that question. But someone watched my video and interpreted it as saying that Liskov and Ladin invented vector clocks, and then they credited me in the footnotes of the Wikipedia page on vector clocks with having “discovered” the Liskov and Ladin paper, which is hilarious – I didn’t “discover” anything! 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. Sorry.

OK, so who did invent vector clocks, then? In their delightfully named 1994 survey “Detecting causal relationships in distributed computations: In search of the holy grail”, Schwarz and Mattern sum up the situation thusly in a footnote:

Actually, the concept of vector time cannot be attributed to a single person. Several authors “re-invented” time vectors for their purposes, with different motivation, and often without knowing of each other. To the best of our knowledge, the first applications of “dependency tracking” vectors [70] appeared in the early 80’s in the field of distributed database management [21, 74]. In [17] and [44], however, vector time is introduced as a generalization of Lamport’s logical time, and its mathematical structure and its general properties are analyzed.

Here, citations 17 and 44 are the aforementioned Fidge and Mattern papers, respectively. Citation 70 is Strom and Yemini’s 1985 “Optimistic recovery in distributed systems”, citation 21 is Fischer and Michael’s 1982 “Sacrificing serializability to attain high availability of data in an unreliable network”, and citation 74 is Wuu and Bernstein’s 1984 “Efficient solutions to the replicated log and dictionary problems”. All of these papers predate Fidge and Mattern by years, and all of them do things that look rather vector-clock-ish. (Wuu and Bernstein’s clock is actually a matrix clock, a generalization of vector clocks! They call it a “2-Dimensional Time Table”.)

Raynal and Singhal’s 1996 survey article on logical clocks (publisher’s version; local version) has a nice historical sidebar called “Vector clocks: A historical perspective” on the fourth page that makes note of several pre-Mattern-and-Fidge papers involving uses of vector clocks. These include the aforementioned Liskov and Ladin paper, the aforementioned Strom and Yemini paper, and a couple more by Raynal and Singhal respectively. And the oldest of the bunch is “Detection of mutual inconsistency in distributed systems” by Parker et al. from 1983, which is, as far as I can tell, the paper that introduced the term “version vector”.2 And Mattern does actually cite Parker et al. in his own 1989 paper, describing Parker et al.’s version vectors as “very similar to our time vectors”.

In the end, I have to agree with Schwarz and Mattern’s take: vector clocks (and matrix clocks, even) were originally thought up and used by a bunch of people in the early-to-mid-80s, including Liskov and Ladin, Wuu and Bernstein, Parker et al., and more. But the papers that established the interesting mathematical properties of vector clocks would have been Fidge’s and Mattern’s papers in 1988, which is why those have become the canonical ones to cite (plus possibly Schmuck’s dissertation as well). And this is unsurprising – in computer science there are many cases of things being used for years (because they work!) before we develop the theory that explains why they work. While we could wish that Fidge and Mattern had been more thorough in citing existing uses of vector clocks back in 1988, it nevertheless seems appropriate to give them the credit for developing the theory.

  1. It can be hard to find authoritative versions of older papers online! I can’t find publisher editions of either the Mattern or Fidge vector clock papers. Instead, I’ve linked to the most authoritiative versions I can find for each. For the Mattern paper, I’ve linked to the version that’s hosted on www.vs.inf.ethz.ch (which is his research group’s website) and linked to from their list of publications. For the Fidge paper, I checked his web page, which links to this list of his publications, which links to a version of the paper. ↩

  2. And one of the authors is my friend Alley Stoughton, it turns out! ↩

Comments