A distributed system consist of a collection of distinct processes which are spatially separated, and which communicate via messaging. Here considered the concept of events ordering in a distributed systems. First, discussed the partial ordering defined by "happened before" relation and give a distributed algorithm for extending it to a consistent total ordering of all events.
The relation "happened before" (->) on the set of events of a system is the smallest relation satisfying the following three conditions:
The "happens before" relation describes partial ordering of the events in the system.
Logical Clock can be represented by the following condition (it doesn't specifically means physical clock):
We can use a system of clocks that satisfying Clock Condition to define a total ordering (=>).
If a is an event in process Pi and b is an event in process Pj, then a => b if and only if either:
We can use use the concept of total ordering to solve simple synchronization problem. We wish to find the algorithm for granting access to shared resource to the process which satisfy following conditions:
Algorithm which satisfy conditions I-III and uses concept of total ordering can be described with the following 5 rules:
Such approach and principles can be generalized and allow to implement any desired form of multiprocess synchronization in a distributed system. But it depends from operating of all processes and failure of one process will halt other processes. The problem of failure not considered here.
There can be an anomalous behaviour if some events which satisfy condition a -> b happens outside the system then system can assign resource access in the wrong order since from the point of view of the system a !-> b which can contradict to expected behaviour by the users. This can be prevented by the use of properly synchronized physical clocks. It can be formally shown how closely the clocks can be synchronized.
References:
Partial Ordering
The relation "happened before" (->) on the set of events of a system is the smallest relation satisfying the following three conditions:
- If a and b are events in the same process, and a comes before b, then a -> b.
- 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.
- If a -> b and b -> c then a -> c.
The "happens before" relation describes partial ordering of the events in the system.
Logical Clock can be represented by the following condition (it doesn't specifically means physical clock):
Clock Condition. For any events a, b: if a -> b then C(a) < C(b).
Note that converse condition doesn't hold so if C(a) < C(b) then we cannot expect that a -> b and two cases are possible either a -> b or a and b are concurrent events. Which means that by knowing just the clock values you cannot distinguish concurrent events.
From the definition of "happens before", Clock Condition is satisfied if the following two conditions hold:
Implementation rules:
Java implementation of Clock Condition as an illustration to this post can be found at Logical Clocks repository. The base classes are LogicalTimestamp which represent specific moment of time and LogicalClock class which provides thread-safe methods to store and update time according to implementation rules and conditions described above during events at each process of distributed system.
From the definition of "happens before", 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).
Implementation rules:
- 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.
Java implementation of Clock Condition as an illustration to this post can be found at Logical Clocks repository. The base classes are LogicalTimestamp which represent specific moment of time and LogicalClock class which provides thread-safe methods to store and update time according to implementation rules and conditions described above during events at each process of distributed system.
Total Ordering
We can use a system of clocks that satisfying Clock Condition to define a total ordering (=>).
If a is an event in process Pi and b is an event in process Pj, then a => b if and only if either:
- (i) Ci(a) < Cj(b) or
- (ii) Ci(a) = Cj(b) and Pi < Pj.
We can use use the concept of total ordering to solve simple synchronization problem. We wish to find the algorithm for granting access to shared resource to the process which satisfy following conditions:
- (I) A process which has been granted resource must release it before it can be granted to another process;
- (II) Different requests for the resource must be granted in the order in which they are made;
- (III) If every process which is granted the resource eventually release it, then every request is eventually granted.
Algorithm which satisfy conditions I-III and uses concept of total ordering can be described with the following 5 rules:
- To request the resource, process Pi sends the request resource message Tm:Pi to every other process, and puts that message on its request queue, where Tm is the timestamp of the message.
- When process Pj receives the request resource message Tm:Pi, it places it on its request queue and sends a (timestamped) acknowledgment message to Pi.
- To release the resource, process Pi removes any Tm:Pi request resource message from its request queue and sends a (timestamped) Pi release resource message to every other process.
- When process Pj receives a Pi release resource message, it removes any Tm:Pi request resource message from its request queue.
- Process Pi is granted the resource when the following two conditions are satisfied: (i) There is a Tm:Pi request resource message in its request queue which is ordered before any other request in its queue by the total ordering relation (=>); (ii) Pi has received a message from every other process timestamped later than Tm.
Such approach and principles can be generalized and allow to implement any desired form of multiprocess synchronization in a distributed system. But it depends from operating of all processes and failure of one process will halt other processes. The problem of failure not considered here.
Anomalous Behavior
There can be an anomalous behaviour if some events which satisfy condition a -> b happens outside the system then system can assign resource access in the wrong order since from the point of view of the system a !-> b which can contradict to expected behaviour by the users. This can be prevented by the use of properly synchronized physical clocks. It can be formally shown how closely the clocks can be synchronized.
References:
