Implementing a Simplified Paxos Algorithm in Go

Paxos is a family of consensus algorithms used to achieve agreement on a single value in a distributed system, even in the presence of failures. This challenge asks you to implement a simplified version of Paxos in Go, focusing on the core concepts of proposal, acceptance, and learning. Successfully implementing this will give you a foundational understanding of distributed consensus.

Problem Description

You are tasked with creating a basic Paxos implementation in Go. The system consists of multiple "Proposer," "Acceptor," and "Learner" nodes. The goal is for the nodes to agree on a single proposed value. This implementation will focus on a single round of Paxos.

What needs to be achieved:

• Implement the roles of Proposer, Acceptor, and Learner.
• Allow a Proposer to propose a value.
• Enable Acceptors to vote on proposals.
• Facilitate Learners to learn the agreed-upon value.
• Handle basic failure scenarios (e.g., an Acceptor being unavailable).

Key Requirements:

• Proposer: Generates a proposal number and a value. Sends a "Prepare" request to all Acceptors. If a majority of Acceptors respond with a promise (and a previously accepted value, if any), the Proposer sends an "Accept" request to the Acceptors with its proposal number and value.
• Acceptor: Maintains a record of the highest proposal number it has seen and the value associated with that proposal. Upon receiving a "Prepare" request with a proposal number higher than its current highest proposal number, it promises not to accept any future proposals with lower numbers and responds with its current highest proposal number and value (if any). Upon receiving an "Accept" request with a proposal number equal to or higher than the proposal number it promised, it accepts the value and responds with an acknowledgement.
• Learner: Receives acceptances from a majority of Acceptors and learns the agreed-upon value.

Expected Behavior:

• Given a set of Acceptors, a Proposer should be able to successfully propose a value and have a majority of Acceptors accept it.
• If multiple Proposers are active, the system should eventually converge on a single value (though not necessarily immediately).
• The system should be able to tolerate the failure of some Acceptors without halting.

Important Edge Cases to Consider:

• Proposal Number Collisions: What happens if two Proposers start proposing values concurrently? (This simplified version doesn't need to handle this perfectly, but should at least acknowledge the possibility).
• Acceptor Failures: What happens if an Acceptor fails after promising but before accepting?
• Multiple Acceptances: What happens if an Acceptor accepts multiple values with the same proposal number? (The last acceptance should win).

Examples

Example 1:

Input: 3 Acceptors, 1 Proposer, Value = "A"
Output: All Learners learn the value "A"
Explanation: The Proposer sends Prepare requests to all 3 Acceptors. All Acceptors promise. The Proposer sends Accept requests with value "A".  A majority (2) of Acceptors accept "A". Learners learn "A".

Example 2:

Input: 5 Acceptors, 1 Proposer, Value = "B", Acceptor 1 fails after promising but before accepting.
Output: All Learners learn the value "B" (assuming the Proposer retries)
Explanation: The Proposer sends Prepare requests. Acceptors 2, 3, 4, and 5 promise. Acceptor 1 fails. The Proposer sends Accept requests. Acceptors 2, 3, 4, and 5 accept "B". Learners learn "B".

Example 3: (Edge Case - Proposal Number Collision)

Input: 3 Acceptors, 2 Proposers (Proposer 1 proposes "C", Proposer 2 proposes "D" concurrently)
Output:  The system converges on either "C" or "D" (depending on which proposal is accepted first by a majority).
Explanation:  Both Proposers send Prepare requests. Acceptors may promise to both.  The outcome depends on the order in which Accept requests are received and processed.  This example highlights the potential for non-determinism in a concurrent environment.

Constraints

• Number of Acceptors: Must be able to handle at least 3 Acceptors.
• Proposal Numbers: Proposal numbers should be monotonically increasing. A simple counter is sufficient.
• Communication: Simulate communication between nodes using channels (Go's concurrency primitives). No external network communication is required.
• Single Round: This implementation focuses on a single round of Paxos. No persistent storage or leader election is required.
• Error Handling: Basic error handling is expected (e.g., handling cases where a majority cannot be reached).

Notes

• Start by defining the roles (Proposer, Acceptor, Learner) as structs with appropriate methods.
• Use channels to simulate communication between the nodes.
• Consider using a mutex to protect shared state (e.g., the highest proposal number seen by an Acceptor).
• This is a simplified implementation. Real-world Paxos implementations are significantly more complex.
• Focus on understanding the core concepts of Paxos rather than creating a production-ready system.
• Think about how to handle the case where an Acceptor promises to one Proposer but receives a higher proposal number from another Proposer.