Logical Clocks
Last updated
Last updated
How do we keep a global vision of the system's behavior through the relations happened-before?
We associate a timestamp C(e) to each event e, thus satisfying the following properties:
If a and b are two events of the same process, and a -> b, then we demand that C(a) < C(b).
If a corresponds to the moment at which message m was sent, and b to the moment at which it was received, then C(a) < C(b).
If there isn't a global clock, how do we do the timestamp?
The consistency is kept through a set of logical clocks, 1 per process.
Each Pi process keeps a counter, Ci, and adjusts this counter.
At every new event that occurs in Pi, Ci is incremented by 1.
Every time a message m is sent by the Pi process, the message receives a timestamp ts(m)=Ci.
Every time a message m is received by a Pj process, Pj adjusts its local counter Cj to max(Cj, ts(m)) and executes the first step before it passes the message m to the application.