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