Stale PrepareResponse May Lead to Two Different Values Being Decided for the Same Instance

[liang636600]

Hi @luohaha , I was experimenting with this project and noticed a potential safety issue in the Paxos implementation. Under certain conditions, stale PrepareResponse messages may be incorrectly counted toward a quorum, which can lead to two different values being decided for the same instance. I will now explain my findings in detail.

How to Trigger This Bug

Consider a 3-node cluster (N1, N2, N3), each running Proposer, Accepter, and Learner. All actions target instance 1. N1 proposes value A, N3 proposes value B. For simplicity, we assume that N1 and N3 have no direct network connection when describing this bug. Figure 1 below illustrates in detail the message interaction that triggers this bug. The blue annotations represent the state of the current instance (Instance current), while the purple annotations denote fields that do not actually exist in the implementation and are included solely for clarity.

Step 1: N1 broadcasts Prepare(ballot=1). N1's Proposer sends PreparePacket(ballot=1, instance=1) to all Accepters:

• N1's Accepter: No prior promise → promises ballot=1 → responds ok=true, ab=0, av=null.
• N2's Accepter: No prior promise → promises ballot=1 → responds ok=true, ab=0, av=null. This response is delayed.

N1.pSet = {N1} — only 1 response, below quorum (needs 2). N1 waits for timeout.

Step 2: N3 broadcasts Prepare(ballot=1). Concurrently, N3's Proposer sends PreparePacket(ballot=1, instance=1) to all Accepters:

• N3's Accepter: No prior promise → promises ballot=1 → responds ok=true, ab=0, av=null.
• N2's Accepter: Already promised ballot=1 to N1 → rejects: ok=false, ab=1.

N3.pSet = {N3} — only 1 response, below quorum. N3 waits for timeout.

Step 3: N3 retries with ballot=2, reaches quorum. N3's Proposer times out. ballot increments to 2. N3 broadcasts PreparePacket(ballot=2, instance=1):

• N2's Accepter: 2 > current.ballot(1) → promises ballot=2 → responds ok=true.
• N3's Accepter: 2 > current.ballot(1) → promises ballot=2 → responds ok=true.

N3.pSet = {N2, N3} — quorum reached. N3 enters Accept and broadcasts AcceptPacket(ballot=2, value=B).

Step 4: N1 retries with ballot=2 (the bug triggers here). N1's Proposer times out. ballot increments to 2, but pSet is NOT cleared — it still contains {N1} from round 1. N1 broadcasts PreparePacket(ballot=2, instance=1):

• N1's Accepter: 2 > current.ballot(1) → responds ok=true, ab=0, av=null..
• N2's Accepter: 2 == current.ballot(2) (already promised to N3) → rejects.

The delayed response from N2 (from Step 1, for ballot=1, ok=true) finally arrives at N1. N1's onPrepareResponse() processes it:
ok == true → adds N2 to pSet without validating the ballot number.
N1.pSet = {N1, N2} — quorum reached!
No previously accepted value found → uses N1's proposed value A.
N1 enters Accept and broadcasts AcceptPacket(ballot=2, value=A).

Step 5: Both N1 and N3 are now in Accept phase with ballot=2 but different values (A and B).

N2's Accepter receives both Accept requests:
Accept(ballot=2, value=B) from N3: ballot == current.ballot (2 == 2) → accepted.
Accept(ballot=2, value=A) from N1: ballot == current.ballot (2 == 2) → accepted (overwrites B).
N2 returns ok=true to both proposers. Both N1 and N3 believe their value was committed. This is a Paxos safety violation — two different values were chosen for the same instance.

Figure 1. An Example Triggering the Bug of Two Different Values Being Decided for the Same Instance.

Root Cause

This issue is caused by three problems in Proposer.java and PrepareResponsePacket.java:

• Missing ballot validation in onPrepareResponse(). The method does not validate the ballot number of incoming responses. It adds a responder to pSet as long as ok == true, without checking whether the response corresponds to the current ballot. As a result, a stale ok=true response from a previous round is treated the same as a valid response from the current round.
• pSet is not cleared when the ballot increases. When a timeout occurs, current.ballot++ is executed and a new prepare() is issued. However, current.pSet is not cleared and still contains entries from the previous round. Combined with the first issue, stale responses can incorrectly contribute to forming a quorum in the new round.
• Lack of ballot field in PrepareResponsePacket. The response message does not carry the responder’s ballot number, making it impossible for the proposer to distinguish between stale and current responses.

Suggested Fix

• Fix 1: Clear pSet when incrementing ballot. In the timeout handler within prepare(), clear pSet before retrying:

// Proposer.java, inside the TimerTask run() in prepare()
@Override
public void run() {
    Instance current = instanceState.get(instance);
    if (current.state == Proposer_State.PREPARE) {
        current.ballot++;
        current.pSet.clear();  // ← clear stale promises
        prepare(id, instance, current.ballot);
    }
}

• Fix 2: Add ballot field to PrepareResponsePacket.

public class PrepareResponsePacket implements Serializable {
    private int id;
    private int instance;
    private int ballot;  // ← the ballot being responded to
    private boolean ok;
    private int ab;
    private Value av;
}

When creating the response in Accepter.onPrepare(), set ballot to the prepare ballot that is being responded to.

• Fix 3: Validate ballot in onPrepareResponse(). Only count responses that match the current ballot:

public void onPrepareResponse(int peerId, int instance, boolean ok, int ab, Value av, int ballot) {
    Instance current = this.instanceState.get(instance);
    if (current.state != Proposer_State.PREPARE)
        return;
    if (ballot != current.ballot)  // ← ignore stale responses
        return;
    if (ok) {
        current.pSet.add(peerId);
        // ... rest unchanged
    }
}

A similar issue also exists in the onAcceptResponse(int peerId, int instance, boolean ok) handler, where the ballot value carried in the message should likewise be checked against the current ballot.

Thank you for taking the time to read this. I'm looking forward to your confirmation, and would be happy to help fix the issue if needed.