Distributed Systems: An Algorithmic Approach

Distributed Systems: An Algorithmic Approach, Second Edition, Edition 2
COMMON SUBPROBLEMS
Leader Election
Mutual exclusion
Time synchronization
Global State
Multicasting
Replica management

Time in a Distributed System

Consistency maintenance among replicated data relies on which update is the most recent one. Important authentication services (like Kerberos) rely on synchronized clocks.

Causal order is the basis of logical clocks, introduced by Lamport.

To settle such issues, we depend on an obvious law of nature: no message can be received before it is sent. Tis is an example of causality. Tus, if Bobs ends a message to Alice, then the event of sending the message must have happened before the event of receiving that mes- sage regardless of the clock readings.

Rule 1: Let each process have a physical clock whose value is monotonically increasing. If a, b are two events within a single process P, and the time of occurrence of a is earlier than the time of occurrence of b, then a <b. Rule 2: If a is the event of sending a message by process P, and b is the event of receiving the same message by another process Q, then a  b. Rule 3: (a <b)(b <c) -> (a < c).