In a centralized system, we can always determine the order in which two events occurred, since the system has a single common memory and clock. Many applications may require us to determine order. For example, in a resourceallocation scheme, we specify that a resource can be used only after the resource has been granted. A distributed system, however, has no common memory and no common clock. Therefore, it is sometimes impossible to say which of two events occurred first. The liappened-before relation is only a partial ordering of the events in distributed systems.
Since the ability to define a total ordering is crucial in many applications, we present a distributed algorithm for exterfding the happened-before relation to a consistent total ordering of all the events in the system.
The Happened-Before Relation
Since we are considering only sequential processes, all events executed in a single process are totally ordered. Also, by the law of causality, a message can be received only after it has been sent. Therefore, we can define the happenedbefore relation (denoted by -») on a set of events as follows (assuming that sending and receiving a message constitutes an event):
1. If A and B are events in the same process, and A was executed before B, then A -» B.
2. If A is the event of sending a message by one process and B is the event of receiving that message by another process, then A —»• B. 3. If A -> B and B -» C then A -• C. Since an event cannot happen before itself, the -> relation is an irreflexive partial ordering.
If two events, A and B, are not related by the —> relation (that is, A did not happen before B, and B did not happen before A), then we say that these two events were executed concurrently. In this case, neither event can causally affect the other. If, however, A -> B, then it is possible for event A to affect event B causally.
A space-time diagram, such as that in Figure 18.1, can best illustrate the definitions of concurrency and happened-before. The horizontal direction represents space (that is, different processes), and the vertical direction represents time. The labeled vertical lines denote processes (or processors). The labeled dots denote events.
A wavy line denotes a message sent from one process to another. Events are concurrent if and only if no path exists between them. For example, these are some of the events related by the happened-before relation in Figure 18.1:
happened first. It is important only that any processes that care about the order of two concurrent events agree on some order.
To determine that an event A happened before an event B, we need either a common clock or a set of perfectly synchronized clocks. Since neither of these is available in a distributed system, we must define the happened-before relation without the use of physical clocks.
We associate with each system event a timestamp. We can then define the global ordering requirement: For every pair of events A and B, if A —> B, then the timestamp of A is less than the timestamp of B. (Below, we will see that the converse need not be true.) How do we enforce the global ordering requirement in a distributed environment? We define within each process P; a logical clock, LQ. The logical clock can be implemented as a simple counter incremented between any two successive events executed within a process.
Since the logical clock has a monotonically increasing value, it assigns a unique number to every event, and if an event A occurs before event B in process P;, then LC,-(A) < LC,-(B). The timestamp for an event is the value of the logical clock for that event. This scheme enstires that for any two events in the same process the global ordering requirement is met. Unfortunately, this scheme does not ensure that the global ordering requirement is met across processes. To illustrate the problem, consider two processes Pi and P2 that communicate with each other.
Suppose that Pi sends a message to Pi (event A) with LCi(A) = 200, and Pi receives the message (event B) with LCjiB) = 195 (because the processor for P2 is slower than the processor for P]r its logical clock ticks more slowly). This situation violates our requirement, since A ~> B but the timestamp of A is greater than the timestamp ofB. To resolve this difficulty, we require a process to advance its logical clock when it receives a message whose timestamp is greater than the current value of its logical clock. In particular, if process P, receives a message (event B) with timestamp f and LC,(B) < t, then it should advance its clock so that LC,-(B) - t + 1.
Thus, in our example, when P2 receives the message from Pi, it will advance its logical clock so that LC2(B) = 201. Finally, to realize a total ordering, we need only observe that, with 6ur timestamp-ordering scheme, if the timestamps of two events, A and B, are the same, then the events are concurrent. In this case, we may use process identity numbers to break ties and to create a total ordering