Distributed Systems
CS3.401Subjective Questions
Short, long, derivation, numerical, proof, compare, architecture.
State Tanenbaum's definition of a distributed system and list its five required features.
State CAP and explain why CA is impossible in real distributed systems.
Two-Generals problem and its implication for distributed systems.
Define Lamport's happened-before relation and the clock consistency condition. Why is scalar Lamport clock only weakly consistent?
State the vector clock rules and how to compare two vector timestamps.
Compare scalar, vector, and matrix clocks on storage, consistency, and main use case.
Compare Cristian's and Berkeley algorithms for physical clock synchronisation.
Explain Chandy-Lamport snapshot algorithm. Why does it require FIFO channels?
State the C1 and C2 cut conditions.
Compare Chandy-Lamport, Lai-Yang, and Acharya-Badrinath.
State the BSS algorithm's two delivery conditions and explain each.
Distinguish FIFO, causal, and total order delivery.
Compare Lamport, Ricart-Agrawala, Maekawa (V2), Suzuki-Kasami, and Raymond DME algorithms.
State Lamport's L1 and L2 entry conditions and explain why both are required.
Why does Maekawa V1 deadlock? How do FAILED / INQUIRE / YIELD in V2 fix it?
Suzuki-Kasami — why does the token-send condition require RN[i] = LN[i] + 1?
Distinguish cycle vs knot in WFG. Which model needs which?
Trace Chandy-Misra-Haas probe algorithm on a 4-process cycle. State the detection rule.
Why is detection the preferred deadlock-handling strategy in DS?
State the three impossibility results for Byzantine Agreement.
Why is N = 3, f = 1 Byzantine impossible? Use the indistinguishability argument.
Compare OM(m) and Phase King on bounds, rounds, messages, and simplicity.
Describe the two phases of 2PC and state the point of no return.
When does 2PC block? How does 3PC's PRE-COMMIT phase fix this?
Why is 3PC not used in practice?
State Raft's three sub-problems and one-line each.
Why is randomised election timeout critical in Raft?
State Raft's election restriction and why it ensures safety.
State GHS combining rules A, B, C with conditions and actions.
Prove max level in GHS is log₂ N.
Test/Accept/Reject — state the three reply rules at node q.
State GFS's three-component architecture and a one-line role for each.
Walk through GFS's write flow with leases. Why are data and control flow separated?
GFS consistency states: define defined / consistent / undefined / inconsistent and give one scenario for each.
Why doesn't GFS master persistently log chunk locations?