Distributed Systems

Which is NOT one of Tanenbaum's five required features?

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

Under CAP, which option is NOT achievable in a real distributed system?

• CP
• AP
• CA
• All three are achievable equally

Scalar Lamport clocks are:

• Strongly consistent
• Only consistent (forward direction)
• Neither
• Strong only on receive events

Singhal-Kshemkalyani vector-clock optimisation requires:

• Causal channels
• FIFO channels
• Authenticated messages
• No assumptions

Berkeley algorithm differs from Cristian's because:

• Berkeley uses UTC, Cristian doesn't
• Cristian uses UTC, Berkeley doesn't
• Both use UTC equally
• Neither uses UTC

Chandy-Lamport requires which channel property?

• FIFO
• Causal
• Non-FIFO
• None

Acharya-Badrinath snapshot uses how many messages?

• O(E)
• O(N)
• 2N
• N²

BSS condition (a) is:

• $V_m[j] = V_i[j]$
• $V_m[j] = V_i[j] + 1$
• $V_m[k] \le V_i[k]\ \forall k$
• $V_m[k] = V_i[k]\ \forall k$

Lamport's DME requires how many messages per CS?

• N
• 2(N-1)
• 3(N-1)
• $\sqrt{N}$

Maekawa's quorum optimum $K$ equals:

• $N$
• $N/2$
• $\sqrt{N}$
• $\log N$

Which Maekawa V2 message is sent when a higher-priority request arrives at a site already replied?

• FAILED
• INQUIRE
• YIELD
• RELEASE

Suzuki-Kasami sends the token when:

• RN[i] > LN[i]
• RN[i] = LN[i] + 1
• RN[i] = LN[i]
• Always on every request

OR-model deadlock criterion is:

• Cycle in WFG
• Knot in WFG (SCC with no outgoing edges)
• Any blocked process
• Two-cycle

CMH probe format (i, j, k) means:

• (initiator, sender, receiver)
• (sender, receiver, initiator)
• (receiver, initiator, sender)
• (initiator, target, receiver)

Mitchell-Merritt probes travel:

• Along WFG edges
• Opposite to WFG edges
• On both sides
• Randomly

Minimum number of processes for Byzantine Agreement tolerating $f$ failures:

• $n \ge 2f+1$
• $n \ge 3f+1$
• $n \ge 4f+1$
• $n \ge f+1$

FLP impossibility states:

• Synchronous Byzantine is impossible
• Async deterministic consensus impossible with ≥1 crash
• Consensus impossible with any failures
• Byzantine impossible in any system

Phase King requires:

• $n \ge 3f+1$
• $n \ge 4f+1$
• $n \ge 2f+1$
• $n \ge f+1$

2PC blocks when:

• Some participants voted NO
• All <ready T> and coord crashed
• Network is partitioned only
• Any participant crashed

On recovery, a participant with <ready T> only:

• redo(T)
• undo(T)
• Ask coordinator (in-doubt)
• Ignore the transaction

Raft's failure model is:

• Byzantine
• Fail-stop only
• Both equally
• Network only

Raft's election restriction requires:

• Highest term wins
• Most up-to-date log wins
• Lowest server ID wins
• Random selection

Why does Raft randomise election timeouts?

• Security
• Prevent split-vote livelock
• Privacy
• Performance

GHS Rule B (merger) condition:

• L < L'
• L = L' AND mutual MWOE
• L > L'
• Any time

GHS max level is:

• N - 1
• log N
• $\sqrt{N}$
• Constant

GFS chunk size is:

• 4 KB
• 64 KB
• 64 MB
• 1 GB

Which is NOT logged by the GFS master?

• File namespace
• File→chunk mapping
• Chunk replica locations
• Chunk version numbers

Atomic record append in GFS gives what consistency outcome?

• Defined
• Consistent but undefined
• Defined interspersed with inconsistent
• Always inconsistent

GFS deleted files are retained for:

• 1 day
• 3 days
• 30 days
• Permanently