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
