1.1 What is the Paxos Algorithm?

Paxos is a distributed consensus algorithm designed to help a group of processes agree on a single value, even in the presence of failures. It is widely used in distributed systems to coordinate tasks like leader election, database replication, and maintaining consistent states across multiple nodes. Paxos ensures:

• Safety: No two processes decide on different values.
• Eventual Liveness: A value will eventually be decided if the system stabilizes (no more failures or delays).

2.1 Roles in Paxos

• Proposer: Proposes a value for consensus. A leader is usually elected to act as the main proposer.
• Acceptor: Votes on proposed values. An acceptor may accept multiple proposals, but only one value will ultimately be chosen.
• Learner: Learns the decided value after consensus is reached. Learners do not actively participate in the consensus but receive notifications of the decision.

2.2 Core Properties

• Quorums: A quorum is a majority of acceptors. Any two quorums overlap, ensuring consistency.
• Ballot Numbers: Unique identifiers for proposals, used to ensure proposal order. Ballot numbers must be strictly increasing.
• Logs: Processes persist decisions and ballot numbers to ensure recovery from crashes.

2.3 Safety Guarantees

Paxos guarantees that once a value is accepted by a quorum, it will remain the only value that can be decided.

3.1 Phase 1: Prepare (Election Phase)

The goal of this phase is to elect a leader and prevent conflicting proposals.

1. A proposer selects a unique, higher ballot ID and sends a prepare request to a quorum of acceptors.
2. Each acceptor compares the received ballot ID with the highest one it has seen:
• If the received ballot ID is higher, the acceptor promises not to accept proposals with lower ballot IDs and responds with the highest proposal it has already accepted (if any).
• If the received ballot ID is lower, the acceptor ignores the request.

3.2 Phase 2: Propose (Bill Phase)

The proposer uses the responses from acceptors to determine the proposal value.

1. If any acceptor has already accepted a proposal, the proposer uses the value of the highest-numbered accepted proposal.
2. If no prior proposal exists, the proposer can use its own value.
3. The proposer sends an accept request with the chosen value and the current ballot ID to the quorum of acceptors.
4. Acceptors compare the ballot ID of the accept request with their current promise:
• If it matches or is higher, they accept the proposal and update their state.
• If it is lower, they reject the request.

3.3 Phase 3: Decide (Law Phase)

Once the proposer gathers acknowledgments from a quorum of acceptors, it declares the value decided.

1. The proposer sends a decision message to all learners, informing them of the agreed value.
2. Learners log and apply the decided value.

4.1 Process Failures

• If a proposer or acceptor crashes, other proposers can take over by starting a new round with a higher ballot ID.
• Persistent logs ensure acceptors can recover their state after a crash.

4.2 Leader Failures

If the leader crashes, another proposer can initiate a new round with a higher ballot ID.

4.3 Message Loss

If messages are lost, timeouts trigger retries or new rounds.

4.4 Network Partitioning

Paxos cannot progress if the quorum cannot be formed. It waits until network connectivity is restored.

5.1 Multi-Paxos

Multi-Paxos optimizes Paxos for repeated decisions by reducing the need for leader elections. Once a leader is elected, it proposes values directly, skipping Phase 1.

5.2 Fast Paxos

Fast Paxos reduces latency by allowing proposers to bypass some phases under specific conditions.

5.3 Practical Byzantine Fault Tolerance (PBFT)

PBFT extends Paxos to handle Byzantine faults, where processes can behave maliciously.

5.4 Raft

Raft simplifies Paxos for better understandability and implementation while maintaining similar guarantees.

6.1 Advantages

• Proven correctness with rigorous safety guarantees.
• Widely applicable to distributed systems, ensuring consistency under failures.
• Efficient in stable systems with minimal failures.

6.2 Limitations

• High complexity in understanding and implementation.
• Performance degradation during frequent leader changes or failures.
• Network partitioning can stall progress.

8.1 What is the Consensus Problem?

Consensus is a fundamental problem in distributed systems, where multiple processes (often distributed across different machines) must agree on a single value. Despite potential failures or delays, they must collectively make a consistent and irrevocable decision.

For example, in a distributed database, consensus ensures all replicas agree on updates to maintain data consistency.

8.2 Why is Consensus Important?

Many key operations in distributed systems rely on consensus:

• Reliable Multicast: Ensures all nodes receive the same messages in the same order.
• Leader Election: Selects a unique leader among distributed processes for coordination.
• Mutual Exclusion: Prevents concurrent access to shared resources.
• Fault Detection: Updates system state in response to process failures.

Without consensus, these operations cannot guarantee correctness in the face of failures or network delays.

8.3 How is Consensus Achieved?

Consensus protocols are designed under specific system models. They involve processes exchanging messages to agree on a value. For consensus to be achieved, protocols must satisfy:

• Agreement: All non-faulty processes must decide on the same value.
• Validity: If all processes propose the same value, they must decide on that value.
• Integrity: The decided value must be proposed by some process.
• Non-triviality: Different outcomes (e.g., 0 or 1) must be possible.

However, achieving consensus depends heavily on the system model, such as synchronous or asynchronous networks.

9.1 What is a Synchronous System?

A synchronous system assumes:

• Messages have a bounded delivery time.
• Processes execute steps within known time bounds.
• Clocks have bounded drift rates.

Examples include multiprocessor systems or supercomputers, where hardware-enforced timing ensures predictable behavior.

9.2 Why is Consensus Solvable in Synchronous Systems?

The predictability of message delivery and process execution allows protocols to coordinate effectively. Even if some processes crash (up to a certain limit), the bounded nature of the system ensures all processes eventually synchronize their decisions.

10.1 What is Paxos?

Paxos is a consensus algorithm designed for asynchronous systems, where there are no guarantees on message delivery times or process speeds. Developed by Leslie Lamport, Paxos is widely used in distributed systems like Google's Chubby and Apache Zookeeper.

10.2 Why is Paxos Important?

Asynchronous systems dominate real-world distributed environments (e.g., the internet). Paxos provides:

• Safety: Ensures no two processes decide on different values.
• Eventual Liveness: Guarantees progress under favorable conditions (e.g., stable network).

While consensus is theoretically impossible in asynchronous systems (FLP impossibility), Paxos achieves practical reliability by balancing safety and liveness.

10.3 How Does Paxos Work?

Paxos operates in three asynchronous phases, repeated until consensus is reached:

1. Election Phase: A leader is elected by gathering votes (ballots) from a majority of processes. The leader proposes a unique value.
2. Proposal Phase: The leader proposes the value to all processes. Processes acknowledge if the value respects prior commitments.
3. Decision Phase: Once the leader receives acknowledgments from a majority, it announces the value as decided.

Key features of Paxos include:

• Use of unique ballot IDs to avoid conflicting proposals.
• Quorum-based voting to ensure overlapping majorities.
• Durability through disk logging for recovery from failures.

1.1 What is the FLP Proof?

The FLP (Fischer, Lynch, and Patterson) proof demonstrates that achieving consensus in asynchronous systems is impossible if even one process can fail. This is due to the inability to distinguish between a failed process and one that is simply slow.

11.2 Why is the FLP Proof Significant?

The FLP result highlights the inherent limitations of asynchronous systems:

• Consensus cannot be guaranteed within a bounded time.
• Systems must accept trade-offs (e.g., safety vs. liveness).

It has profoundly influenced the design of distributed systems, leading to algorithms like Paxos that provide practical guarantees.

11.3 How Does the FLP Proof Work?

The proof is based on two key concepts:

• Bivalency: A system configuration is bivalent if it can lead to multiple possible decisions (e.g., 0 or 1).
• Indistinguishability: Delays make it impossible to determine if a process has failed or is merely slow.

The proof constructs scenarios where a system is kept in a bivalent state indefinitely, preventing consensus.

11.4 Implications for Distributed Systems

The FLP result underscores the need for eventual consistency in real-world systems. Algorithms like Paxos achieve this by sacrificing time-bounded guarantees in exchange for practical reliability under typical conditions.