時間、時鐘與分散式系統中事件的排序

The concept of one event happening before another in a distributed system is examined, and is shown to define a partial ordering of the events. A distributed algorithm is given for synchronizing a system of logical clocks which can be used to totally order the events. The use of the total ordering is illustrated with a method for solving synchronization problems. The algorithm is then specialized for synchronizing physical clocks, and a bound is derived on how far out of synchrony the clocks can become.

The concept of time is fundamental to our way of thinking. It is derived from the more basic concept of the order in which events occur. We say that something happened at 3:15 if it occurred after our clock read 3:15 and before it read 3:16.

In a distributed system, it is sometimes impossible to say that one of two events occurred first. The relation “happened before” is therefore only a partial ordering of the events in the system. We have found that problems often arise because people are not fully aware of this fact and its implications.

Most people would probably say that an event a happened before an event b if a happened at an earlier time than b. … However, if a system is to meet a specification correctly, then that specification must be given in terms of events observable within the system. … We will therefore define the “happened before” relation without using physical clocks.

Definition. The relation “→” on the set of events of a system is the smallest relation satisfying the following three conditions: (1) If a and b are events in the same process, and a comes before b, then a → b. (2) If a is the sending of a message by one process and b is the receipt of the same message by another process, then a → b. (3) If a → b and b → c then a → c. Two distinct events a and b are said to be concurrent if a ↛ b and b ↛ a.

Another way of viewing the definition is to say that a → b means that it is possible for event a to causally affect event b. Two events are concurrent if neither can causally affect the other.

This definition will appear quite natural to the reader familiar with the invariant space-time formulation of special relativity … In relativity, the ordering of events is defined in terms of messages that could be sent. However, we have taken the more pragmatic approach of only considering messages that actually are sent.

We define a clock Ci for each process Pi to be a function which assigns a number Ci(a) to any event a in that process. … For now, we make no assumption about the relation of the numbers Ci(a) to physical time, so we can think of the clocks Ci as logical rather than physical clocks. They may be implemented by counters with no actual timing mechanism.

The strongest reasonable condition is that if an event a occurs before another event b, then a should happen at an earlier time than b. We state this condition more formally as follows.

Note that we cannot expect the converse condition to hold as well, since that would imply that any two concurrent events must occur at the same time.

It is easy to see … that the Clock Condition is satisfied if the following two conditions hold. C1. If a and b are events in process Pi, and a comes before b, then Ci(a) < Ci(b). C2. If a is the sending of a message by process Pi and b is the receipt of that message by process Pj, then Ci(a) < Cj(b).

IR1. Each process Pi increments Ci between any two successive events.

IR2. (a) If event a is the sending of a message m by process Pi, then the message m contains a timestamp Tm = Ci(a). (b) Upon receiving a message m, process Pj sets Cj greater than or equal to its present value and greater than Tm.

Hence, the simple implementation rules IR1 and IR2 imply that the Clock Condition is satisfied, so they guarantee a correct system of logical clocks.