In the paper “PAXOS made moderately complex”, the authors introduce unfamiliar concepts not mentioned in the original PAXOS paper, concepts such as slots, slot in, slot out, and WINDOW. I found these concepts difficult to understand despite reading both the accompanying pseudo code as well as their Python implementation.
This post aims to shed light on these concepts and better understand how the following invariant holds:
R5: A replica proposes commands only for slots for which it knows the configuration: slot_in < slot_out + WINDOW
The rest of the post focuses on the replica only. We will not discuss the actual consensus algorithm, also known as the SYNOD; this topic will be covered in a separ
- Slots are to be occupied by decisions
- SLOT_IN points to the next “free” unoccupied slot
- SLOT_OUT points to the next decision to be executed
- SLOT_IN advances by 1 with every new decision received by leaders
- SLOT_OUT advances by 1 with every execution of a decision by the replica
- SLOT_IN + WINDOW is N number of slots allowed to be buffered
- SLOT_OUT trails behind the SLOT_IN as more decisions flow into the replica
- SLOT_OUT == SLOT_IN means replica has processed all it’s commands
Then, the replica, as it receives requests from clients, will send proposals to the leaders. The leaders will, as part of its consensus algorithm, will respond with decisions commands, each accept command tied to a particular slot position. We won’t discuss the consensus algorithm as part of this post (but perhaps another).
Then, as the replica receives decisions, it will fill the slot accordingly. Every time a slot fills, the slot in pointer advances by one.
Next is the perform phase. The replica will execute the decision — it’s associated command — and will advance the slot out index by 1.
After receiving a decision, the replica will fill in the slot associated with that particular decision.
Then, for illustrative purposes, imagine that the replica sends out another proposal (not shown in the figure below), advances the slot in by 1, then fills in the second slot.
Finally, during the perform phase, the replica will advance the slot out pointer.
Finally, in this example, the replica executes the next command, advancing SLOT OUT which now points to the same (unoccupied) slot as SLOT IN.
WORK IN PROGRESS