Of logical clocks and total ordering
Lamport defines a system of logical clocks that simply assigns a number to each event, in order to sequence them in the order of their actual occurrence. The system of clocks assigns to any process b, a number C(b) where the function C could be implemented using simple counters with no actual timing mechanisms at all. The function however, should satisfy what is termed the 'clock' condition to prove its correctness.
The clock condition in simple terms requires that if an event a occurs before an event b (in the ordering based on the system of clocks), then a should happen at an earlier time than b. More formally,
Clock Condition: For events a and b:
if a -> b then C(a) < C(b)
Clearly, the case of concurrent events makes it wrong to expect the converse condition to hold as well.
It is important to note that the function C is local to individual processes. Since send and receive events belong to separate processes, we need what Lamport calls 'implementation rules' to guarantee that the system of clocks satisfies the clock condition.
One, obviously the function C has to increment its value between any 2 successive events. Two, there must be a mechanism to make sure that the receive event must always get a higher value than the send event that caused it. The second condition is achieved by a simple implementation rule. Upon receiving a message, the receiving process sets the value of C to greater than or equal to its present value (value of C in the receiving process) and greater than the value assigned by the sending process. Mathematically,
Cj = max(Cj(b), Ci(a) + 1)
The system of logical clocks described above is clearly an irreflexive partial order. A relation of the sort 'a -> a' does not make sense in a physical system. Also, it is only a partial order since totality is absent (with concurrent events, neither of a -> b and b -> a is true). The ordering nonetheless, is a causal order.
Ideally, we would like to obtain a total ordering with causal consistency. In an attempt to extend Lamport's system of logical clocks to achieve total ordering, Lamport suggests using an ordered pair of the form T(i,j) where i is the process identifier and j is the event's time stamp (or value C(a)). If Cj(b) = Ci(a), the value i acts as the arbiter. Clearly, the 'i' part of the ordered pair establishes a priority among processes and results in a total ordering of events. It is only the partial ordering given by j that is uniquely determined by the system of events. This total ordering is denoted by '=>'.
Total Ordering and distributed systems
As described in an earlier section, being able to totally order events is of great help while building distributed systems. Lamport uses the example of solving the mutual exclusion problem in a distributed system to show this fact. The problem in general, can be termed a 'resource allocation' problem. The following is the problem definition taken straight from his paper:
Lamport defines a system of logical clocks that simply assigns a number to each event, in order to sequence them in the order of their actual occurrence. The system of clocks assigns to any process b, a number C(b) where the function C could be implemented using simple counters with no actual timing mechanisms at all. The function however, should satisfy what is termed the 'clock' condition to prove its correctness.
The clock condition in simple terms requires that if an event a occurs before an event b (in the ordering based on the system of clocks), then a should happen at an earlier time than b. More formally,
Clock Condition: For events a and b:
if a -> b then C(a) < C(b)
Clearly, the case of concurrent events makes it wrong to expect the converse condition to hold as well.
It is important to note that the function C is local to individual processes. Since send and receive events belong to separate processes, we need what Lamport calls 'implementation rules' to guarantee that the system of clocks satisfies the clock condition.
One, obviously the function C has to increment its value between any 2 successive events. Two, there must be a mechanism to make sure that the receive event must always get a higher value than the send event that caused it. The second condition is achieved by a simple implementation rule. Upon receiving a message, the receiving process sets the value of C to greater than or equal to its present value (value of C in the receiving process) and greater than the value assigned by the sending process. Mathematically,
Cj = max(Cj(b), Ci(a) + 1)
The system of logical clocks described above is clearly an irreflexive partial order. A relation of the sort 'a -> a' does not make sense in a physical system. Also, it is only a partial order since totality is absent (with concurrent events, neither of a -> b and b -> a is true). The ordering nonetheless, is a causal order.
Ideally, we would like to obtain a total ordering with causal consistency. In an attempt to extend Lamport's system of logical clocks to achieve total ordering, Lamport suggests using an ordered pair of the form T(i,j) where i is the process identifier and j is the event's time stamp (or value C(a)). If Cj(b) = Ci(a), the value i acts as the arbiter. Clearly, the 'i' part of the ordered pair establishes a priority among processes and results in a total ordering of events. It is only the partial ordering given by j that is uniquely determined by the system of events. This total ordering is denoted by '=>'.
Total Ordering and distributed systems
As described in an earlier section, being able to totally order events is of great help while building distributed systems. Lamport uses the example of solving the mutual exclusion problem in a distributed system to show this fact. The problem in general, can be termed a 'resource allocation' problem. The following is the problem definition taken straight from his paper:
- A process that has been granted a resource must release it before it can be granted to another process.
- Different requests for the resource must be granted in the order in which they were made.
- If every resource which is granted the resource eventually releases it, then every request is eventually granted.
How Lamport solves the mutual exclusion problem in a distributed system and a little more to close this essay, coming up in the next blog post.
No comments:
Post a Comment