Ordering Requests: Part II

In previous request ordering protocols, the unique identifier for a request is proposed by the client making the request. Now we will look at a protocol where our state machine replicas decide on a unique identifier for a request.

Method 3: Replica-generated identifiers

This protocol has two phases:

1. In the first phase, state machine replicas present candidate unique identifiers for a request.

2. In the second phase, the replicas select one of the proposed unique identifiers to identify the request.

In our previous approaches, we needed significant communication between servers for assigning unique identifiers. With logical clocks, communication is required for stable requests. And with synced real-time clocks, communication is required to keep clocks synchronized. With replica-generated identifiers, we only require communication between servers that run clients and replicas.

To explain this protocol for ordering requests, let’s establish some definitions first. A state machine replica has seen a request if it has received the request and proposed a candidate unique identifier for the request. A state machine replica has accepted a request if it knows the ultimate choice of the unique identifier for the request. We will use $cuid(sm_i, r)$ to refer to the candidate unique identifier for request $r$ proposed by state machine replica $sm_i$ and $uid(r)$ as the unique identifier chosen by replicas.

Now, we will set some rules for $cuid(sm_i, r)$:

1. [$UID1$] $cuid(sm_i, r)$ is always less than or equal to $uid(r)$. This ensures that the chosen unique identifier for a request is always the largest of the proposed unique identifiers by state machine replicas.

2. [$UID2$] If $sm_i$ has seen a request $r'$ after it has accepted another request $r$, then $uid(r)$ will be less than the proposed $cuid(sm_i, r')$. This ensures that a state machine replica always proposes a unique identifier larger than any chosen identifier.

To enforce the order requirement, we need to ensure that every request's agreed identifier is unique. In other words, if two requests are not the same, their unique identifiers are also different. Another thing we need to ensure is that every request seen is eventually accepted. The order requirement will be satisfied if we can ensure these two requirements and the rules for $cuid(sm_i, r)$.

Let's look at a simple protocol that satisfies our requirements in nodes where fail-stop failures can occur:

A simple implementation

For a distributed system of $N$ clients, each state machine replica $sm_i$ maintains the following variables:

1. $SEEN_i$: The largest $cuid(sm_i, r)$ assigned to any request seen by $sm_i$ so far.

2. $ACCEPT_i$: The largest $uid(r)$ assigned to any request accepted by $sm_i$ so far.

On receiving a request, $sm_i$ computes $cuid(sm_i, r)$ as follows: