Link: ACM Portal
Summary
The concept of an event happening before another event 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.
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.
What is 'happened before'? Assume that our system is composed of a collection of processes. Each process consists of a sequence of events that are totally defined. We also assume that sending or receiving a message is an event in a process. We can then define the 'happened before' relation (->) as: (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, and (3) If a -> b and b -> c then a -> c.
Logical Clocks: In the simplest case, the clock is just a way of assigning a number to an event, where the number is thought of as the time at which the event occurred. More precisely, 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 such a system to be considered correct, the strongest reasonable condition (called Clock condition) is: For any events a, b, if a -> b then C(a) < C(b).
To guarantee that the system of clocks satisfies the Clock condition, we will insure that: (1) Each process Pi increments Ci between any two successive events, and (2) If event a is the sending of a message m by process Pi, then the message m contains a timestamp Tm = Ci(a). Upon receiving a message m, process Pj sets Cj greater than or equal to its present value and greater than Tm.
No comments:
Post a Comment