Distributed Computing Wikiclass | TutorialAnswer / TimeDistributedSystems

Tutorial : Time in Distributed Systems

Question 1: Lamport's Timestamp

    P1: a=1, b=4, c=5
    P2: d=2, e=3, f=4, g=5
    P3: h=1, i=6, j=7

Question 2: Vector Clock

    P1: a=[1,0,0] b=[2,2,1] c=[3,2,1]
    P2: d=[0,1,1] e=[0,2,1] f=[1,3,1] g=[1,4,1]
    P3: h=[0,0,1] i=[3,2,2] j=[3,4,3]

Question 3: Logical time in distributed systems

(c) Advantage: By using Lamport’s clocks, we cannot conclude that e→e’ if L(e)<L(e’). However, we can conclude a causal relationship using the vector clock. Disadvantage: The amount of storage and message payload is proportional to the number of processes in a group

(d) The causality problem occurs because process B receives M7 before M5. Using vector clocks, we detech that the M5 timestame vector is strictly less than the M7 vector.

(e) Suggested algorithm to avoid causal problem (in other words, to implement causal ordering) using vector timestamps.

    On initialization Vi[j] = 0(j = 1; 2; …N );
    Process i: Before multicast each message, Vi[i] = Vi[i] + 1, include new timestamp in the message
    Process i: For each multicast message Vj received, place the message in hold-back queue;
    Wait until Vj[j] == Vi[j] + 1 and Vj[k] <= Vi[k](k ≠ j);
    Deliver message and Vi[j] = Vi[j] + 1;