Assignment: Classical Problems in
Distributed Systems
Based on the lecture slides: Lect_6, Topic_7, Topic_8, Topic_9
Student Name: ___Silla Ibrahim____
Instructions
1) Answer all questions. Show full working for numerical questions.
2) For algorithm traces, clearly list messages/events in order.
3) Where a slide gives a formula or rule, use that rule exactly.
Section 1: Time ordering and clock synchronization (Lect_6)
Q1. Numerical (clock drift): Two computers with drift rate ρ = 10⁻⁶ start synchronized.
How much can they drift apart in 1 hour?
• State the drift bound used (maximum relative drift between two clocks).
➢ The drift bound used is 2ρ as one computer can run fast +ρ and another can
run slow -ρ; therefore, maximum relative drift = ρ + ρ = 2ρ.
• Compute the maximum possible difference after 1 hour (show steps).
➢ T=60*60 = 3600 seconds
➢ Max drift = 2ρ×T
➢ Max drift = 2×10⁻⁶×3600 = 0.0072 s = 7.2 ms
Q2. Numerical (resynchronization interval): In a system with drift rate ρ = 2×10⁻⁶,
timestamps must be accurate within δ = 100 ms. Using the slide rule “resynchronize
every δ/(2ρ) seconds”, compute the maximum resynchronization interval.
• Give the interval in seconds and in hours.
➢ Interval = δ/(2ρ)
➢ Interval (second) = 0.1/(2×2×10⁻⁶) = 25000 s
➢ Interval (hour) = 25000/3600 = 6.94 hours
• Explain briefly why the formula uses 2ρ (not just ρ).
➢ The formula uses 2ρ because we are calculating the interval between two clocks.
Q3. Cristian’s algorithm (explain + small calculation): Explain why the estimate uses half
of the round-trip time. Then compute the time set by process P when the server time is t =
15:10:20.400 and the measured round-trip time is 80 ms.
• Explain the assumption behind using RTT/2.
➢ The reason why the estimate uses half of the round-trip time is that we need to
only consider the time that elapsed when the server time is set to be added the
server time to catch up to the approximate current server time.
• Write the final adjusted time (show arithmetic).
➢ Server time t = 15:10:20.400
➢ RTT = 80ms ➔ RTT/2 = 40 ms
➢ Process time t = server time + RTT/2 = 15:10:20.440.
• Suggest one simple strategy to improve accuracy using multiple measurements (as
noted in the slide).
➢ One strategy to improve accuracy is to make multiple measurement of the
RTT/2 and take their average.
Q4. Numerical (NTP 4-timestamp problem): Given T1=1100, T2=800, T3=850,
T4=1200, compute: (i) round-trip delay δ = (T4−T1) − (T3−T2), and (ii) offset θ =
((T2−T1) + (T3−T4))/2.
• Compute δ and θ.
➢ δ = (T4−T1) − (T3−T2) ➔ δ = (1200-1100) – (850-800) = 50
➢ θ = ((T2−T1) + (T4−T3))/2 ➔ θ = ((800−1100) + (1200−850))/2 = 325
• The slide states “clock cannot go backward.” Explain what the client should do if the
correction would move its clock backward.
➢ The client should reduce the clock rate till the real time catches up.
Q5. Happened-before (HB) + Lamport logical clocks: Consider P1 has events a (local), b
(send m to P2), c (local). P2 has events d (local), e (receive m), f (local).
• List all HB relations you can conclude.
➢ a (local) -> b (send m to P2), b (send m to P2) -> c(local)
➢ b (send m to P2) -> e (receive m)
➢ d (local) -> e (receive m), e (receive m) -> f(local)
• Identify at least one pair of concurrent events (if any) and justify using the HB
definition.
➢ a and d events are concurrent as a vector clock and d vector clock are not
strictly less than the other.
• Assign Lamport timestamps assuming both clocks start at 0 and follow the slide rules
(increment on local/send; on receive set to max (local, received) +1).
➢ P1: a (1,0) -> b (2,0) -> c (3,0)
➢ P2: d (0,1) -> e (2,2) -> f (2,3)
Q6. Vector clocks (concurrency detection): Three processes P1, P2, P3 start with vector
clocks [0,0,0]. Message pattern: (1) P1→P2 sends m1, (2) after receiving m1, P2→P3
sends m2, (3) after receiving m2, P3→P1 sends m3.
• Compute the vector timestamp attached to each message m1, m2, m3.
• Give the final vector clock at each process after all receives.
• Using vector-clock comparison, state whether the send of m1 and the receive of m3
are causally related or concurrent (justify).
➢ The send of m1 and the receive of m3 are causally related as [2,0,0]<[3,3,3]. All
the vector clock elements of the send of m1 are less than that of the receive of m3.
Section 2: Leader election and mutual exclusion (Topic_7)
Q7. Leader election trace (Bully vs Ring): Processes have IDs {1,2,3,4,5,6}. Process 6
was coordinator and crashes. Process 2 detects the failure and initiates an election.
• (Bully) Write a consistent message sequence (Election / OK / Coordinator
announcement) and count the number of messages.
➢ Total number of messages: 19
• (Ring) Assume logical ring 1→2→3→4→5→6→1. Show how IDs circulate and how
the coordinator is announced. Count messages.
➢ Total number of messages:10
Q8. Centralized mutual exclusion (describe + numerical): Based on the slides, describe
how the coordinator grants access to the critical section and how it handles a queue.
➢ On receiving request, the coordinator checks the availability of the critical section
and the emptiness of the queue; if both are true, then the coordinator grant access
to the critical section. If not true in either case, the coordinator’s queue the
request; upon receiving a release, the coordinator remove the next request in the
queue and sends grant message to the concerned process.
• If each critical-section entry costs 3 messages (request, grant, release), how many
messages are needed for 12 entries total?
➢ For 12 entries in critical-section, 36 messages are needed in total.
• State two drawbacks/limitations of centralized mutual exclusion mentioned or
implied by the slides.
➢ One of the main drawbacks of centralized mutual exclusion is that it constitutes a
single point of failure in the system. In addition, there is no way to know whether
the coordinator is dead or the lock is in use as in either case there is no response
from the coordinator.
Q9. Token ring mutual exclusion (explain): Explain how a token is used to arbitrate
access to the critical section in a logical ring.
➢ Token ring is used to arbitrate access to the critical section by passing a token in a
logical ring; any process that hold the token can access the critical section. If the
process has finished using the token or does not need it, it passes the token to the
next process in the ring.
• Why is detecting token loss described as “non-trivial” in the slides? Give one
concrete reason.
➢ Detecting token loss is described as “non-trivial” owing to several reasons; one of
these reasons is that the current position of the token and its state is not known.
• Explain one advantage and one disadvantage of token ring compared with centralized
mutual exclusion.
➢ One advantage of token ring compared with centralized mutual exclusion is that it
is fair in terms of number of entries in critical section per process.
➢ One disadvantage of token ring compared with centralized mutual exclusion
resides in the fact that process can immediately get access to the critical section
when it is available instead of waiting for the token to traverse the ring.
Section 3: Replication and consistency (Topic_8)
Q10. Object replication (compare approaches): The slides show two approaches: (1)
application is responsible for replication and (2) the system/middleware handles
replication.
• Compare the two approaches in terms of: (i) who handles consistency issues, and (ii)
impact on application development.
➢ In application-level replication, the application is responsible for handling
replication and the consistency issues; this way of doing make the application
development harder. On the other hand, in middleware-level replication, the
system/middleware is responsible for handling replication and consistency issues
instead of the application; this way makes the application development easier, yet
the object-specific solutions harder.
• Give one scenario where approach (1) is preferable and one where approach (2) is
preferable (based on slide reasoning).
➢ Approach one is preferable in real time systems such as real-time multiplayer
video games where replication need to be customized and fast.
➢ Approach two is preferable in web application where data access patterns are well
defined.
Q11. Data-centric consistency models (explain differences): Using the slide summary
table, explain the differences between: Strict consistency, Linearizability, Sequential
consistency, Causal consistency, and FIFO consistency.
• For each pair below, state one key difference: (i) strict vs sequential, (ii)
linearizability vs sequential, (iii) causal vs FIFO.
(i): Strict consistency relies on absolute time ordering of all shared accesses; while in
sequential, accesses are not ordered in time.
(ii): In linearizability, accesses are further ordered according to a (nonunique) global
timestamp; while in sequential, accesses are not ordered in time.
(iii): In causal consistency, all processes see causally-related shared accesses in the
same order; while in FIFO consistency, writes from different processes may not
always be seen in that order even if they are causally-related.
• Give a short example (2–3 operations) that violates causal consistency but still
satisfies FIFO consistency (or explain why your example works).
In this example, causal consistency is violated as the causally related writes w(x)a
and w(x)b are not read in the same order they occurred; however, it does not
violate FIFO consistency as writes done by different processes may not always be
seen in same order.
Q12. Client-driven consistency + eventual consistency + epidemic protocols: Using the
slides, answer the following.
• Define the four client-driven semantics: monotonic reads, monotonic writes, read-
your-writes, and writes-follow-reads.
➢ Monotonic reads: a data store is said to provide monotonic-read consistency if a
process reads the value of a data item X, any successive read operation on X by
that process will always return that same value or a more recent value.
➢ Monotonic writes: a data store is said to provide monotonic-read consistency if a
process write must be propagated to all replicas before a successive write by the
same process.
➢ Read-your-writes: data store is said to provide read-your-writes consistency if the
effect of a write operation by a process on data item X will always be seen by a
successive read operation on X by the same process.
➢ Writes-follow-reads: a write operation by a process on a data item X following a
previous read operation on X by the same process is guaranteed to take place on
the same or a more recent value of X that was read.
• Explain what “eventual consistency” means and name two example systems from the
slides.
➢ Eventual consistency is a type of consistency model that ensures that an update
should eventually propagate to all replicas. For instance, in distributed database
system where there are few writers and more readers processes.
• Epidemic protocols: explain the idea of ‘infective’ vs ‘susceptible’ stores, and why
pair-wise exchange is useful in weak connectivity.
➢ Infective store is a store with an update that it is willing to spread; however,
susceptible store is a store that is not yet updated.
➢ Pair-wise exchange is useful in weak connectivity because it tolerates
disconnections and has low coordination overhead.
Section 4: Fault tolerance (Topic_9)
Q13. Failure models (classification): Using the slide table, classify each situation as
crash, omission (send/receive), timing, response (value/state transition), or arbitrary
failure.
• A server halts and stops responding forever ➔ crash
• A server fails to receive some incoming messages ➔ receive omission
• A server responds but outside the specified time interval ➔ timing failure
• A server responds quickly but returns incorrect values ➔ value failure
Q14. Numerical (probability of failure): The slides state: Prob(failure) = Prob(any one
component fails) = 1 − P(no failure). Assume a system has N independent components,
each with probability p of failing during a day.
• Derive P(no failure) in terms of N and p ➔ P(no failure) = (1-p)^N
• Compute Prob(failure) for N=10 and p=0.02 (show steps).
➢ P(failure) = (p)^N ➔ P(failure) = (0.02)^10
• Explain why distributed systems are more exposed to partial failures than single-
machine systems (1–2 lines).
➢ Systems are more exposed to partial failures than single machine systems as the
probability of failure increases with the number of machine.
Q15. Byzantine generals (numerical/trace + threshold): Using the Byzantine generals
slides:
• From the 4-general example (3 loyal, 1 traitor): describe what the vectors ‘Got(…)’
represent and how inconsistent values can appear.
➢
• Use the threshold statement on the slide: with m faulty processes, agreement is
possible only if 2m+1 processes function correctly out of 3m+1 total. Compute the
minimum total processes needed for m=1 and m=2.
For detection:
M=1 => 2m+1 => 2+1 = 3
M=2 => 2m+1 => 4+1 = 5
For agreement:
M=1 => 3m+1 => 3+1 = 4
M=2 => 3m+1 => 6+1 = 7
• In 2–3 lines, explain why 2 loyal generals and 1 traitor is insufficient to guarantee
agreement (based on the example slide).
2 loyal generals and 1 traitor is insufficient to guarantee agreement as we need more
than two-thirds processes to function correctly.