Instead of synchronizing clocks, event ordering can be used

If two events occurred at the same process *pi* (*i* = 1, 2, … *N*) then theyoccurred in the

order observed by *pi*, that is order →*i*

when a message, *m* is sent between two processes, *send(m)* happened before *receive(m)*

Lamport[1978] generalized these two relationships into the **happened-before relation:** ** e **→

*i e’*

HB1: if *e* →*i e’* in process *p*i, then *e* → e*‘*

HB2: for any message *m*, send(*m*) → receive(*m*)

HB3: if *e* → *e’* and *e’* → *e*”, then *e* → *e”*

Lamport‘s logical clocks

Each process *pi* has a logical clock *Li*

a monotonically increasing software counter

not related to a physical clock

Apply Lamport timestamps to events with happened-before relation

LC1: *Li* is incremented by 1 before each event at process *pi*

LC2: when process *pi* sends message *m*, it piggybacks *t* = *Li*

when *pj* receives *(m,t),* it sets *L*j := *max*(*L*j, *t*) and applies LC1 before timestamping the event *receive* (*m)*

*e *→*e*‘ implies* L*(*e*)<*L*(*e*‘), but* L*(*e*)<*L*(*e’*) does not imply* e*→*e*‘

Totally ordered logical clocks

Some pairs of distinct events, generated by different processes, may have numerically identical Lamport timestamps

Different processes may have same Lamport time

Totally ordered logical clocks

If e is an event occurring at pi with local timestamp Ti, and if e‘ is an event occurring at pj with local timestamp Tj

Define global logical timestamps for the events to be (*Ti, i* ) and (*Tj, j*)

Define (*Ti, i* ) < (*Tj, j* ) iff

*Ti *<* Tj *or

*Ti *=* Tj *and* i < j*

No general physical significance since process identifiers are arbitrary

**Vector clocks**

Shortcoming of Lamport clocks:

*L(e) < L(e’) *doesn’t imply* e *→* e’*

Vector clock: an array of N integers for a system of N processes

Each process keeps its own vector clock *Vi* to timestamp local events

Piggyback vector timestamps on messages

Rules for updating vector clocks:

*Vi*[*i*]] is the number of events that* pi *has timestamped

*Vi*j*i*] (* j*≠* i*) is the number of events at* pj *that* pi *has been affected* *by VC1: Initially, *Vi*[ *j* ] := 0 for *pi*, *j=*1.. *N* (*N* processes)

VC2: before *pi* timestamps an event, *Vi*[ *i* ] := *Vi*[ *i *]+1 VC3:* pi *piggybacks* t *=* Vi *on every message* *it sends

VC4: when *pi* receives a timestamp *t*, it sets *Vi*[ *j* ] := max(*Vi*[ *j* ] , *t*[ *j* ]) for

*j*=1..*N *(merge operation)

Compare vector timestamps

V=V‘ iff V[j] = V‘[j] for j=1..N

V>=V‘ iff V[j] <= V‘[j] for j=1..N

V<V‘ iff V<= V‘ ^ V!=V‘

Figure 11.7 shows

*a*→*f *since V(a) < V(f)

c || e since neither V(c) <= V(e) nor V(e) <= V(c)