Q1.
Berkeley Algorithm with Clock Drift (8 Marks)
Four machines (M1 to M4) are part of a distributed system. Their clocks read as follows at
synchronization time (in seconds past 00:00):
M1: 120.0 (coordinator)
M2: 122.5
M3: 118.0
M4: 119.0
The round-trip time (RTT) from M1 to each machine and back is:
RTT(M2) = 4.0s
RTT(M3) = 2.0s
RTT(M4) = 6.0s
Tasks:
1. Estimate each machine’s time delay (assume symmetric RTT).
2. Calculate the clock drift (offset) for each machine as seen by M1.
3. Determine the average offset (excluding coordinator’s own time).
4. Compute the adjustment values that each machine should apply.
Q2. Lamport Logical Clocks with Concurrent Events (9 Marks)
Three processes P1, P2, and P3 execute the following events in order. Events with messages
are indicated.
vbnet
CopyEdit
P1: a → b → c → (send m1 to P2)
P2: d → e (receive m1) → f → (send m2 to P3)
P3: g → h → i (receive m2)
Tasks:
1. Assign Lamport timestamps to each event.
2. Identify pairs of concurrent events (no causal relationship).
3. Show which event(s) happened-before event 'i'. Justify using the happened-before
relation.
Q3. Vector Clocks with Message Overtaking (8 Marks)
Three processes P1, P2, and P3 start with vector clocks [0,0,0]. The events occur in the
following order:
1. P1 sends m1 to P2
2. P1 sends m2 to P3 (before m1 is received)
3. P2 receives m1
4. P3 receives m2
5. P2 sends m3 to P3
6. P3 receives m3
Tasks:
1. Show the vector clock updates at each step.
2. Demonstrate how message m2 appears to overtake m1.
3. Analyze whether m3 can be causally linked to m1.
Q1. Cristian’s Algorithm (6 Marks)
A client wants to synchronize its clock with a time server using Cristian’s algorithm.
The client sends a request at T1 = 10:00:00.100 and receives a response at T4 =
10:00:00.300.
The server’s timestamp (T2 = T3) is 10:00:00.200.
Tasks:
1. Compute the round-trip time (RTT).
2. Estimate the offset.
3. Calculate the new client time.
Q2. Lamport Logical Clocks (7 Marks)
Three processes P1, P2, and P3 perform events as follows:
Event Process Type
A P1 Internal Event
B P1 Sends message to P2
C P2 Receives message from P1
D P2 Sends message to P3
E P3 Receives message from P2
Assumptions:
Each process increments its clock by 1 for each event.
Each message transmission includes the sender’s clock timestamp.
Tasks:
1. Assign Lamport timestamps to each event (A–E).
2. Show the logical clock values for each process after each event.
Q3. Vector Clocks (7 Marks)
Consider three processes P1, P2, and P3. Their vector clocks are initially all [0, 0, 0].
The following events occur:
1. P1 sends message m1 to P2.
2. P2 sends message m2 to P3.
3. P3 sends message m3 to P1.
Tasks:
Show the vector clock values at each step.
Demonstrate how causality is preserved.
Q1. Fault-Tolerant Berkeley Synchronization (10 Marks)
A distributed system has 5 nodes (M1 to M5). M1 acts as the coordinator. The clocks (in
milliseconds past reference time) and RTTs (ms) are as follows:
Node Local Time (ms) RTT to M1 (ms)
M1 5000 0
M2 5200 4
M3 4900 2
M4 5300 6
M5 5500 8
However, M5 is suspected to be faulty, as its drift is large and irregular.
Tasks:
1. Compute clock offsets using Berkeley algorithm, assuming symmetrical RTTs.
2. Discard outliers using majority consensus (exclude M5).
3. Calculate final average offset.
4. Determine how much each node (including M1) should adjust its clock.
Q2. Hybrid Logical Clock with Event Causality (10 Marks)
Consider three processes P1, P2, and P3. Each maintains a Hybrid Logical Clock (HLC) in
the form (L, C), where:
L: Lamport timestamp
C: Counter to break ties on equal Lamport values.
The events occur as follows:
1. P1: e1 (internal), e2 (send m1 to P2)
2. P2: e3 (receive m1), e4 (send m2 to P3)
3. P3: e5 (receive m2), e6 (internal)
Assume that:
Initial HLC at each process is (0,0)
Message delay is negligible
Internal events increment logical time
Message reception: if Lrecv < Lmsg, then Lrecv = Lmsg and Crecv = Cmsg + 1
Tasks:
1. Assign HLC timestamps to all events e1–e6
2. Analyze which events are concurrent
3. Show the happened-before graph
4. Discuss how HLC resolves ambiguities compared to pure Lamport clocks
Q3. Vector Clock with Forked Causality & Message Reordering (10 Marks)
A system has 3 processes (P1, P2, P3) initialized at vector [0,0,0]. Events happen as follows:
1. P1 sends m1 to P2
2. P1 sends m2 to P3
3. P2 receives m1 and immediately sends m3 to P3
4. P3 receives m2
5. P3 receives m3 before processing m2 due to network delay
6. All vector updates follow standard rules
Tasks:
1. Show vector timestamps at each step
2. Identify where message reordering leads to inconsistency
3. Propose a buffer-based solution to preserve causal delivery
4. Identify any causality violations if messages are processed as received
