Distributed Systems

Required features of a distributed system (Tanenbaum):

• Many computers
• Concurrent execution
• Independent failures
• Shared memory
• No global clock

Which logical clocks satisfy strong consistency ($e \to e' \Leftrightarrow C(e) < C(e')$)?

• Scalar (Lamport)
• Vector
• Matrix
• Singhal-Kshemkalyani optimised vector

Conditions for a consistent global cut:

• No msg arrow future → past
• Total message count preserved
• C1: send recorded ⇒ msg present
• C2: send NOT recorded ⇒ msg absent
• Initiator sees own snapshot

Maekawa V2 adds which messages over V1?

• FAILED
• RELEASE
• INQUIRE
• YIELD
• VOTE

Which models use cycle as the deadlock criterion?

• Single resource
• AND
• OR
• AND-OR

True statements about Phase King:

• Needs n ≥ 4f+1
• Needs n ≥ 3f+1
• Polynomial messages
• Exponential messages
• f+1 phases × 2 rounds

Statements true for 2PC:

• Blocks on coord crash + all <ready>
• Handles network partition gracefully
• Forces stable log writes for <ready> and <commit>
• Used in production with Paxos/Raft for coordinator

Raft's three sub-problems:

• Leader Election
• Log Replication
• Safety
• Snapshot
• Byzantine Tolerance

GHS message types:

• connect
• initiate
• test
• accept/reject
• report
• changeroot
• commit

GFS fault-tolerance mechanisms:

• 3× replication across racks
• Master operation-log replication + shadow master
• Per-64KB checksums
• Atomic 2PC for writes
• Heartbeat-based stale replica detection