Matt Chung

PAXOS made moderately complex – slots

—

by

Matt Chung
in

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 Overview

  • 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
Replica Initial state
Figure 1 – Imagine a WINDOW=5. Initially, both slot_in and slot_out both point to slot 1

 

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).

Figure 2 – Replica sending a proposal for slot 1

 

Then, as the replica receives decisions, it will fill the slot accordingly. Every time a slot fills, the slot in pointer advances by one.

Figure 3 – As replica receives decisions, it inserts into its buffer, advancing slot in by 1

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.

Figure 4 – Replica receives decision and fill in the particular slot associated with the 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.

Figure 5 – Slot IN points to index 3 and Slot OUT still pointing to slot 1

Finally, during the perform phase, the replica will advance the slot out pointer.

Figure 6 – As the replica executes commands in the slot, the slot OUT index advances. The slot, previously yellow, is now green, symbolizing that the occupying command has been executed

 

Finally, in this example, the replica executes the next command, advancing SLOT OUT which now points to the same (unoccupied) slot as SLOT IN.

Figure 7 – Replica executes it second outstanding decision, advancing SLOT OUT by 1, which now points to the same (unoccupied) slot as SLOT IN

Summary

WORK IN PROGRESS