The Part-Time Parliament

How to read the original

1. Read Requirements and Assumptions before the protocol.
2. Read The Single-Decree Synod and Mathematical Results; translate ballots into acceptor state.
3. Read The Multi-Decree Parliament only after distinguishing a chosen value from knowledge that it was chosen.

Safety must survive an unfinished round

Lamport’s parliamentary narrative develops agreement despite absent participants and unreliable messengers, while retaining durable records. The central safety question is whether different rounds can choose conflicting values. Intersecting quorums help, but intersection alone is insufficient: later proposals must preserve the evidence returned from earlier accepted proposals. This reconstruction uses modern proposer and acceptor terminology for a single decision, rather than pretending one instance already implements a complete replicated service.

Original reconstruction: a decision nobody has announced

Use five acceptors A, B, C, D, and E, with any three forming a quorum. Proposal numbers are unique and totally ordered. Each acceptor durably records its highest promise and its highest accepted proposal and value. Messages may be delayed, duplicated, or lost; participants are assumed to follow the protocol rather than behave maliciously.

A proposer completes preparation for proposal 7, then asks acceptors to accept value red. A, B, and C durably accept (7,red). The value is now chosen because a quorum accepted it, even if the proposer crashes before broadcasting a result. D and E may know nothing about that decision. Chosen is a property of the distributed history, not a requirement that every observer already knows it.

A new proposer starts proposal 9 and receives preparation replies from C, D, and E. C reports accepted proposal 7 with red; the others report none. The new proposer must propose red, taking the value of the highest-numbered accepted proposal reported by its preparation quorum. It cannot substitute blue just because two of its three replies contain no accepted value.

Why is C’s single report decisive? Any quorum of three intersects the earlier choosing quorum of three. The report carries evidence that red may already have been chosen. A protocol cannot safely infer that an earlier value was unchosen merely because the new proposer lacks a complete record of who accepted it. Promises constrain future acceptance of older proposals while this evidence is transferred into a later round.

Break one rule to expose its purpose

If the new proposer ignores C and proposes blue, C, D, and E could accept blue at 9 while A, B, and C had already chosen red at 7. Both sets are majorities. Their intersection did not prevent inconsistency because the value-preservation rule was broken. This counterexample explains why “take a majority vote” is not a complete consensus algorithm.

If an acceptor forgets its promise after a restart, it may later accept an obsolete request that its earlier promise was supposed to exclude. Stable storage is therefore part of the model. Testing only executions without restarts misses a core safety obligation.

Separate progress from consistency

Two competing proposers can keep issuing higher proposal numbers and disrupting each other. Safety may remain intact while no value is chosen. Progress requires an appropriate period of communication and sufficiently stable proposer behavior; it is not guaranteed merely by having implemented the safety rules.

For a simulator, record every promise, acceptance, durable write, restart, and delivered message. Compute chosen values from quorum acceptance histories rather than from leader announcements. Test that at most one value is chosen for the instance, then separately measure whether a stable communicating majority eventually completes.

Finally, a replicated log introduces ordering of multiple decisions, recovery, membership changes, and application execution. A client retry can also repeat an already chosen command unless the application identifies operations. The paper’s proof discipline is a foundation for these mechanisms, not permission to omit them from the system boundary.

Reconstruction exercise

Three acceptors A, B, and C form two-member quorums. A alone accepts red at proposal 3. A later proposer prepares proposal 4 with B and C; both report no accepted value and promise 4. May it choose blue? Explain why a delayed request for red at proposal 3 cannot subsequently make red chosen if promises are respected. Contrast this with A and B having already accepted red at 3.

Worked solution

In the first history, only A accepted red, so no two-member quorum chose it. The new proposer’s preparation quorum B,C reports no accepted value, allowing the proposer to select blue at 4. B and C’s durable promises prohibit accepting the later-arriving proposal 3 request, so A cannot recruit either into a quorum for red. If A and B had both already accepted red at 3, red would be chosen even if no learner knew it. Any two-member preparation quorum intersects {A,B}; at least one reply must carry the relevant accepted history, subject to the full protocol’s higher-proposal rules. The later proposer must preserve the required value rather than choose blue freely. The difference is not whether the old proposer announced success. It is the acceptance history and the constraints that carry that history across intersecting rounds.

Test the limits and transfer the idea

1. Protocol trace and proof · allow 40 minutes

Carry forward a partially accepted value

Use modern proposer/acceptor terminology for the paper's single-decree protocol. Five acceptors A–E use quorums of three; proposal numbers are unique and state is durable. Proposal 3 prepared successfully and only A accepted red. Proposal 4 subsequently prepared with B,C,D, all reporting no accepted value, then only B accepted blue. No other acceptance occurs.

Proposal 5 prepares with A,B,E. List the replies, choose the legal value, and explain why counting red and blue reports or voting among preferred values is wrong. Prove that red at proposal 3 cannot later become chosen after the successful preparation of proposal 4. Does the fact that neither earlier proposal was chosen allow proposal 5 to invent green?

Get a starting hint

The rule uses the highest accepted proposal number in the preparation quorum. Promises constrain events that have not occurred yet.

Compare your reasoning with the worked solution

A reports (3,red), B reports (4,blue), and E reports no acceptance. Preparation at 5 raises their durable promises to 5. The proposer must select blue because proposal 4 is the highest accepted number among these replies. There is no vote between the reported values and no preference ballot over new ones.

Proposal 4 was allowed to select blue: B,C,D reported no accepted values. Their promises to 4 also blocked all future acceptance of proposal 3 by those three acceptors. Only A and E could then accept proposal 3, giving at most two acceptors, below the quorum of three. A's isolated earlier acceptance was real but could no longer grow into a choosing quorum. A delayed proposal-3 message does not undo the promises.

Neither 3 nor 4 has been chosen in the stated history. Nevertheless, proposal 5 cannot choose green. The protocol follows a locally checkable preservation rule rather than requiring proposers to reconstruct omniscient global histories. In a different history, an accepted report could be the surviving evidence of a chosen value. Obeying the highest-number rule allows one safety argument to cover both cases. Blue may subsequently become chosen if a quorum accepts it at 5. The reasoning assumes non-Byzantine participants, durable state, unique proposal numbers, and correctly executed preparation; removing those assumptions requires a different argument.

Check your reasoning

• Chooses blue using proposal number, not report count.
• Uses the B,C,D promises to bound all future proposal-3 acceptances.
• Distinguishes global knowledge from the protocol rule and states assumptions.

2. Counterexample trace · allow 45 minutes

Show why a forgotten promise breaks safety

Three acceptors A,B,C use two-member quorums. Proposal 1 prepares with B,C, sees no previous acceptance, and selects red, but its accept requests are delayed. Proposal 2 prepares with A,B, also sees no previous acceptance, and selects blue; its accept requests are delayed too. B now restarts and loses only its promise to proposal 2. It has not accepted any value yet.

Deliver messages to make both red and blue chosen. Record each acceptance and the two choosing quorums. Explain why B accepting a later blue request after accepting red is not itself the faulty step. State the minimum durable ordering required before a promise reply is sent, and contrast this safety failure with two leaders repeatedly preempting each other.

Get a starting hint

First exploit B's forgotten promise with the older accept request. Then deliver the already prepared newer requests.

Compare your reasoning with the worked solution

After B loses its promise, deliver the proposal-1 red requests to B and C. B's incorrect recovered state permits acceptance at 1; C still permits 1. Both durably accept (1,red), so red is chosen by {B,C}. Now deliver the proposal-2 blue requests to A and B. A accepts at 2; B also accepts because 2 is above its current promise. Blue is chosen by {A,B}. The two majorities intersect at B, but intersection cannot help if its promise is forgotten.

The decisive violation occurred when B accepted proposal 1 after having replied to preparation 2. Its promise had guaranteed that this would not happen. Accepting a different value at a higher proposal is not generally forbidden by an acceptor's local rule: the proposer must have performed preparation correctly, and the proof depends on durable promises protecting that preparation's evidence. B does not rerun phase one whenever a phase-two message arrives.

An acceptor must durably record the new promise before sending the reply on which a proposer may rely, and recover that record before processing requests. Accepted proposal/value records likewise require durable ordering before acknowledgement. A crash between an in-memory update and persistence cannot be treated as a completed promise. By contrast, two compliant proposers may keep raising numbers and prevent completion without choosing conflicting values. That is a liveness problem. This trace demonstrates a safety violation even with eventual message delivery and only one crash.

Check your reasoning

• Constructs both choosing quorums in a legal order except for the specified forgotten promise.
• Locates the exact invariant violation instead of banning all higher-number value changes.
• Specifies durable-before-reply ordering and separates safety from liveness.

Check your understanding

A quorum accepted red, but the proposer crashed before announcing it. Is red chosen?

• No, until every process receives a broadcast.
• Yes, quorum acceptance establishes that property.
• Only if the client retries.
• Only if the value is accepted twice by each member.

Explanation

Learning a decision and the decision having been chosen are distinct events.

A later preparation quorum reports one accepted red value and two empty histories. May the proposer ignore red by majority vote?

• Yes, empty replies outvote it.
• Yes, if it changes its own ID.
• No, it must follow the highest-accepted-value rule.
• Only if it omits durable storage.

Explanation

A single report can carry evidence of a value already chosen by a different quorum.

Original paper and sources

Leslie Lamport. The Part-Time Parliament. ACM Transactions on Computer Systems, 1998; author copy includes later minor corrections.

Read the original paper →

Read the primary paper: Leslie Lamport

• The Part-Time Parliament: Leslie Lamport