Home | | Distributed Systems | | Distributed Systems | Logical time and logical clocks

Chapter: Distributed Systems - Synchronization and Replication

| Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail |

Logical time and logical clocks

Instead of synchronizing clocks, event ordering can be used

Logical time and logical clocks

 

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 ei e' in process pi, then e → e'

 

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

 

HB3: if ee' and e'e'', then ee''

 

 

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 Lj := max(Lj, 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 ee


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

 

Viji] ( 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

 

af since V(a) < V(f)

 

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


Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail


Copyright © 2018-2020 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.