Distributed Systems: Consensus, Concurrency, and Recovery

01. Election Algorithms and Requirements

An election algorithm is a method used in distributed systems to designate a single process as the coordinator or leader. The primary requirements include ensuring that only one leader is elected at a time and that all processes agree on the outcome.

02. Two-Phase Commit Protocol

The Two-Phase Commit (2PC) protocol ensures atomicity and consistency across distributed transactions. It coordinates multiple nodes to ensure they either all commit or all abort.

Phases of 2PC

• Phase 1: The Prepare Phase (Voting): The coordinator asks participants if they can commit.
• Phase 2: The Commit Phase (Decision): The coordinator instructs participants to finalize the transaction based on the votes.

Roles and Steps

• Coordinator: Orchestrates the process.
• Participant: Executes the transaction and votes.
• Step 2: Participant votes "Prepared to Commit."
• Step 3: Coordinator decides based on votes.
• Step 4: Participants commit and acknowledge.
• Final State: Coordinator marks the transaction as "Done."

03. Concurrency Control Methods

Managing concurrent access is vital for data integrity in distributed systems.

Key Concurrency Control Techniques

• Lock-Based Methods: Includes Two-Phase Locking (2PL), Centralized Lock Managers, and Distributed Lock Managers.
• Timestamp-Based Methods: Uses unique timestamps to order transactions (e.g., Basic Timestamp Ordering, MVTO).
• Optimistic Concurrency Control (OCC): Validates transactions at commit time; ideal for low-contention environments.
• Multiversion Concurrency Control (MVCC): Allows readers and writers to operate on different versions of data simultaneously.
• Quorum-Based Methods: Uses voting among replicas (R+W > N) to ensure consistency.
• Graph-Based Methods: Prevents cycles in dependency graphs to avoid deadlocks.
• Hybrid Methods: Combines techniques like locking and OCC for optimized performance.

04. Deadlock Detection in Distributed Systems

Phantom Deadlocks

A phantom deadlock occurs when a system falsely detects a deadlock due to delays in propagating wait-for information. This happens when outdated wait-for graphs (WFG) are analyzed after a transaction has already released its resources.

Edge Chasing

Edge chasing is a distributed detection technique that forwards "probe messages" along dependency paths to identify cycles without needing a global WFG.

• Local WFGs: Each server tracks its own dependencies.
• Probe Messages: Sent when a transaction waits for a remote resource.
• Cycle Detection: If a probe returns to the initiator, a deadlock is confirmed.

05. File Recovery Approaches

(a) Logging

Logging records changes in a persistent file before applying them to the actual data.

• Write-Ahead Log (WAL): Ensures changes are recorded before execution.
• Redo/Undo Logs: Used to re-apply committed changes or revert uncommitted ones after a crash.

(b) Shadow Versions

Shadow versions involve creating a backup copy of a file before modification.

• Process: Updates are made to the shadow copy. Upon success, the shadow replaces the original.
• Recovery: If a failure occurs, the shadow is discarded, leaving the original file intact.