When there is no shared “now”, what can the processes of a distributed system still agree on?
Computing has always abstracted time away, but distributed systems cannot: each machine has its own drifting clock, and there is no global one. Physical clocks can be synchronised, to UTC or to each other, and that is enough when you need the time of day or the length of an interval. Often, though, what matters is not when events happened but in which order, and ordering only needs to respect what could have influenced what. Lamport's happens-before relation captures exactly that, and logical clocks turn it into numbers. Scalar clocks respect causality but cannot detect concurrency. Vector clocks can, at the cost of n integers per timestamp. Ordering is still not the whole story: coordinating a system also depends on what its actions are.
The chapter opens with Edward Lee's argument [Lee, 2009]. Computing's foundations (Turing, Church, von Neumann) are about transforming data, and they say nothing about the dynamics of physical processes. Meanwhile the two worlds are merging. Special-purpose devices (cars, medical devices, robots, toys) now have general-purpose architectures and are networked in the IoT, their complexity possibly costing dependability. General-purpose computers, in turn, are asked to sense and control physical dynamics. The result is cyber-physical systems (CPS): the integration of physical processes with networked computing, “to create new science, techniques, and products”.
Remarkable examples of CPS [Lee, 2009]
Lee's point is that “the passage of time is essentially absent in computing”. He lists four common beliefs that keep it absent:
Four misconceptions about time [Lee, 2009]
The conclusion: core computing abstractions should be rethought to include time.
What notion of time should we use? The dictionary gives a “measurable continuum”, but physics has not believed in a single one since relativity. Summarising Rovelli [2017]: there is no true time and no unique time. Physics describes how things evolve in their own times and how those times relate. There is no privileged direction, no global “now”, time is not independent, and time is related to change: events happen, and time is a way of relating their dynamics. Keep that last sentence in mind, because logical clocks are exactly that idea made operational.
Recall the definitions from Ch. 1. A computation is parallel when all processes share the same temporal context T, concurrent when at least two have different temporal contexts (T ≠ T′), and distributed when at least two have different spatial contexts (S ≠ S′). Distributed concurrent computing (S ≠ S′, T ≠ T′) is the most natural and general model of a distributed system. It is also the one where time stops being obvious:
Time is unambiguous. There is one clock; a process asks the kernel for the time, and any later request gets a higher value. The result is a total order of events for free.
There is no natural notion of time: no global clock, no common memory. Every process has its own clock, and clocks drift apart by up to several seconds a day. Even clocks synchronised at start tick differently.
The slides then ask four questions, and the rest of the chapter answers them in turn. Is there a useful, well-founded notion of time in a distributed system? Is there a coherent notion of global time? If not, what can we do, and how do we synchronise activities? (“Synchronous” literally means existing or occurring at the same time.) Behind them are two sharper questions: is it possible to build a global notion of time, and is it useful?
A computer clock is really a timer: an oscillating quartz crystal with a counter and a holding register. When the counter reaches zero it raises an interrupt and reloads from the register. Each interrupt is a clock tick. Two quartz crystals never oscillate at exactly the same rate, which is why clocks drift.
The process of ensuring that physically distributed processors have a common notion of time.
Most applications need physical time for one of three reasons:
Keep the third one in mind. It is the only one that logical clocks can replace.
For machines a, b with clocks Ca, Cb, where t is real time:
| Term | Definition | Formula |
|---|---|---|
| Time | the reading of the clock at real time t; a perfect clock has Ca(t) = t | Ca(t) |
| Frequency | the rate at which the clock progresses | C′a(t) |
| Offset | difference from real time; relative offset between two clocks | Ca(t) − t ; Ca(t) − Cb(t) |
| Skew | frequency difference from the perfect clock; relative skew | C′a(t) − 1 ; C′a(t) − C′b(t) |
| Drift | the second derivative of the clock | C″a(t) ; C″a(t) − C″b(t) |
Manufacturers specify a maximum skew rate ρ. A clock works within its specification when
1 − ρ ≤ dC/dt ≤ 1 + ρA fast clock has dC/dt > 1, a perfect one = 1, a slow one < 1. The instrument below exaggerates ρ so you can see it.
A fast and a slow clock, both within spec, against UTC. Move the skew rate and the resynchronisation period, then scrub along real time.
Two clocks within spec can drift apart at up to 2ρ per second. To keep them within δ of each other you must resynchronise at least every δ / 2ρ seconds. Because clocks only run forward (see NTP below), a fast clock is not set back but slowed down (slewed) until real time catches up; otherwise timestamps would go back in time and make would misjudge which files are newer. Real NTP daemons slew small offsets but step the clock, even backwards, when the offset is large.
To synchronise to real time, clocks need an accurate standard. That standard is UTC, officially Coordinated Universal Time (the slides write “Universal Coordinated Time”). The BIPM in Sèvres combines and averages the atomic time standards of member nations into a single official UTC. It is broadcast as a short radio pulse every UTC second (e.g. NIST's WWV station) and by satellites providing a UTC service. If one machine has access to UTC, an algorithm can synchronise all the others to it. The standard example is NTP (Network Time Protocol, v4 in RFC 5905): a time server holds global absolute time and other machines synchronise to it. And, again, clocks can only run forward.
Sometimes applications need a time related to physical time: global absolute time. Sometimes a time server is not stably available, or not available at all, and all the processes need is a common time, whatever its relation to UTC: global relative time. Then active servers poll each other, estimate an average and apply corrections, and no machine needs UTC. Two examples:
So far synchronisation has meant physical time. Relative time was already a hint that we can loosen it: processes may need to share a clock that is not real time. One step further, what many algorithms need is not a clock at all but an agreed order of events.
A bank account of $1000 is replicated in LA and NY. At the same time, a customer adds $100 and an employee applies 1% interest. Each replica applies both updates, but in a different order, so LA ends with $1110 and NY with $1111. That is an inconsistency caused by concurrent updates on a replicated database. Better clocks would not fix it. What fixes it is both replicas applying the updates in the same order, and which order does not even matter.
If two processes do not interact, they need no synchronisation, because lack of synchronisation would not be observable. What usually matters is not the exact time at which events occur but the order in which they occur. Synchronising non-physical, logical clocks is therefore both admissible and useful.
The slides' example is UNIX make (or Gradle). It rebuilds a target when a source is newer than the target, so it only needs the order of the two edits, not their exact times. On a distributed file system with unsynchronised clocks, that order can come out wrong, and an edited file does not get rebuilt.
Following Baquero & Preguiça [2016]: any computational system can be modelled as a sequence of executed actions, each defined by a change of state in the system or, more generally, in the world (reading memory, writing a file, switching on a lamp). In a distributed system actions execute in many places and are represented as events: sending or receiving a message, updating a database record. The places may be two processes on the same machine or two sites on opposite sides of the globe.
Not all events are related, but some can cause or influence later ones: a reply to an email is influenced by that email. Detecting potential cause-and-effect relations is fundamental to distributed algorithms. Replica consistency, garbage collection, checkpointing (Ch. 4) and concurrency analysis all rely on it.
Cause-and-effect the system itself can perceive: messages it carries, the order of steps inside a process. This is the scope we reason about.
Cause-and-effect in the outside world. Alice books dinner for two and tells Bob; Bob books movie tickets for after dinner. Even if both booking systems belong to the same multiplex, they cannot know that Alice's booking caused Bob's. External causality generally cannot be detected, and without domain knowledge it can only be approximated with physical time.
When can event c cause event e? Exactly when e could know about c. Either they are on the same process and c ran first, or they are on different processes and e learned about c through a message from some process that knew about c. Otherwise there is no way c could be a cause of e.
“a happens before b”: all processes agree that a occurs first, then b. It is observed directly in two situations, and closed under transitivity:
Happens-before is a partial order. When neither a → b nor b → a, nothing can be said about their order. They are concurrent: a ∥ b.
This gives a practical test. c is a possible cause of e iff there is at least one causal path, a directed path through process lines and messages, from c to e. e plus everything with a path to it is its causal history: the events that could have influenced it. Concurrent does not mean “at the same physical instant”. In the run below, a1 happens well before c2 in physical time, yet a1 ∥ c2.
The slides' Alice / Bob / Chris run. Click an event to light up its causal past (cobalt) and future (vermilion); dashed events are concurrent with it. Click a second event to compare the two. Try a1 then c3, and a1 then c2. Switch to Blank sandbox to build your own run.
Physical time can approximate causality: something earlier might be a cause of something later. But then we lose the explicit connection between events, which is the message. And a common physical time might not be available at all. What we want is a logical time: a value C(a) for each event that every process agrees upon.
With H the domain of events and T the domain of logical time, a logical clock is a function C : H → T satisfying the monotonicity property called the clock consistency condition:
∀ a, b ∈ H : a → b ⇒ C(a) < C(b)If the implication also holds backwards, the system of clocks is strongly consistent:
∀ a, b ∈ H : a → b ⇔ C(a) < C(b)Consistency says timestamps never contradict causality. Strong consistency says timestamps also reveal it: comparing two timestamps tells you whether the events are causally related or concurrent.
Any implementation has to settle two issues:
Systems of logical clocks differ in how they represent time and in their protocol. All of them implement these two rules and guarantee the monotonicity property, and each adds specific properties of its own.
Scalar time squashes both clocks into a single integer lci per process, with an increment δi (usually 1):
The timestamp of event a on pi is C(a) = lci(a), a distributed implementation of logical global time. Clocks only increase along process lines and across messages, so scalar clocks are consistent by construction. They have three further properties, one of which is a limit:
A run built to show every property above. Select b2 to see rule 3 (max, then tick). Compare a3 with b2 (equal timestamps, broken by process id) and a3 with b3 (3 < 4 but concurrent). Check a4's height: 8, so 7 events precede it on its longest causal path. Then switch the labels to Vector.
The problem with scalar clocks in one line: a → b ⇒ C(a) < C(b), but C(a) < C(b) ⇏ a → b. Timestamps can be totally ordered when events are not, so comparing timestamps of unrelated events is meaningless, and scalar clocks cannot tell you whether events are unrelated. Causal histories could, but they grow without bound. Vector clocks keep just enough of the history.
For a system of n processes, a vector clock is an array of n logical clocks, one per process. It assumes n is known; smaller vectors are possible, but the properties are proven for n. Process pi keeps a vector vci in which:
Here the order of tick and merge does not change the result. A sender can never know more events of pj than pj itself has executed, so the max never touches entry j. That is exactly the protection the scalar clock lacks.
This relation is antisymmetric and transitive, subsumes simple logical clocks, and captures causality:
vc(a) < vc(b) ⇔ a → bSo vector clocks are strongly consistent, even though the order on vectors is not total. When neither vector is below the other, the events are concurrent.
What does a vector mean? Each ts(m)[i] counts the events at pi that causally precede the sending of m. So ts(m) summarises everything m may depend on. Information about the “chain of events” is preserved and shared among processes: every process knows how many events preceded the sending of a received message at the sender. In Instrument 2, compare Causal history with Vector. b2's history is {a1, a2, b1, b2} and its vector is [2,2,0]. The vector is the history, compressed to one count per process. The compression works because each process's events are totally ordered.
1 integer per event and message. Consistent. Gives a total order with tie-breaking. Cannot detect concurrency.
n integers per event and message; n must be known. Strongly consistent: detects causality and concurrency.
Some squashing still happens in vectors. Matrix clocks extend logical time further; the slides “stop here”.
In a matrix clock, row j of pi's matrix is pi's knowledge of pj's vector: what pi knows that pj knows. A process can then tell when everyone has seen an event. That is useful for discarding obsolete information, such as log entries every replica already has.
M6 ends by widening the frame. Communication is only half the story; interaction is the general issue. Governing interaction means doing the right thing at the right time, and “at the right time” is the critical problem. Yet ordering events is not always enough:
More fundamentally, synchronisation is about when things happen, but actions are more than sending messages. Meaningful interaction depends on the nature of the actions, not just on their being suitably ordered as undifferentiated steps.
Governing interaction based both on time and on the nature of actions, aimed at achieving some global objective of the distributed system.
| You need… | Use | Because |
|---|---|---|
| time of day, time intervals, timeouts | physical clocks (UTC / NTP) | only physical time measures duration |
| a common clock without UTC | global relative time (Berkeley, RBS) | agreement, not accuracy, is the goal |
| one agreed order of all events | Lamport clock + process id | consistent with causality, total, cheap |
| to know if two events are related or concurrent | vector clocks | strongly consistent |
| to act on what the events mean | coordination | order is necessary, not sufficient |
Practise each out loud in two minutes.
The receive is an event, so rule 1 applies to it. With only max, a process at 1 receiving timestamp 2 would give the receive the value 2, the same as the send, violating a → b ⇒ C(a) < C(b). Show it on a two-process diagram.
No. It is a linear extension of happens-before. Causally related events keep their order; concurrent events are ordered arbitrarily (by timestamp, then process id). That is fine because concurrent events are independent. It is useful because everyone computes the same order, e.g. the two bank replicas applying updates identically.
Logical time only replaces the third use (relative ordering). Time of day and intervals between events on different machines, including timeouts, leases and failure detection, need physical time. External causality (Alice tells Bob) can also only be approximated by physical time.
pi knows that at least k events of pj precede its current state causally. The cost is n integers per event and per message, and n must be known: awkward under dynamic membership.
Synchronisation fixes when things happen relative to each other. Coordination also depends on what actions are (reading vs writing, acquiring vs releasing) and on a global objective. Mutual exclusion and election are coordination algorithms, not clocks.
| Slides | Content | Here |
|---|---|---|
| M6 · Prologue | Computing needs time; CPS I–III; four misconceptions [Lee, 2009] | §1 |
| M6 · Time & Computation | Which notion of time; time after relativity [Rovelli, 2017] | §2 |
| M6 · Time in DS | Parallel / concurrent / distributed recap; basic questions; the issue of time | §2, Ch. 1 |
| M6 · Physical time | Timers; synchronisation I–III; terminology; UTC/BIPM/WWV; NTP; inaccuracies (ρ); absolute vs relative; Berkeley, RBS | §3 |
| M6 · Logical time | Physical vs logical; bank example; logical clocks [Lamport, 1978]; make/Gradle | §4 |
| M6 · Toward coordination | Communication & interaction; beyond synchronisation I–III; coordination | §9 |
| C5 · Actions, events, causes | Actions & events; events & causes; internal vs external causality | §5 |
| C5 · Logical clocks | Detecting causality; happens-before; causal paths; causal histories | §5 |
| C5 · Logical clocks | Time, causes, events; logical time I–III | §6 |
| C5 · Lamport I–IX | Algorithm; middleware support; implementation; consistency; total order; event counting; no strong consistency | §7 |
| C5 · Vector clocks | Problem; definition; rules; example; ordering; result; matrix time | §8 |