Ordering Requests: Part I

Requirements for order

Replica coordination requires (alongside the agreement property) the order property, which states that every non-faulty state machine replica processes requests in the same relative order. One way to implement order is to assign unique identifiers to each request. This way, we can manage the order in which replicas process requests in the unique identifiers' total order.

With replicas processing requests according to the order of their unique identifiers, we define a request as stable at a state machine replica $sm_i$ if a non-faulty client cannot deliver a request with a lower unique identifier to $sm_i$. We can enforce the order requirement if every replica processes stable requests with the smallest unique identifier. This is called order implementation. The order implementation will require some request handling that enables replicas to maintain a list (or any data structure) of unprocessed stable requests and remove processed requests from that list.

Order implementation requires a method to assign unique identifiers to requests. This method also needs to be constrained by the assumptions that a client can make about the order in which state machines process requests:

1. [$O1$] A state machine processes requests by one of its clients in the order the client issued the requests. For example, a client $c$ issues requests to a state machine $sm$ in the following order: request $A$, then request $B$, and then request $C$. In this case, $sm$ will process $A$ first, then $B$, and then $C$.

2. [$O2$] If a client $c_0$​ makes a request $r_0$​ to state machine $sm$ that causes another client $c_1$​ to make a request $r_1$​ to $sm$, then $sm$ will process $r_0$​ before $r_1$​.

These two assumptions do not necessarily mean that $sm$ will process requests in the order they were made or received.

Let's discuss three ways in which we can implement order implementation. Replicas will need a test to classify a request as stable. We will have a stability test section for all our order implementations where we explain how replicas can check whether a request is stable.

Note: You can review how unique identifiers can be generated in the Sequencer chapter.

Order implementation

Method 1: Logical clocks

A logical clock is a function that maps events to integers. A logical clock $\hat{T}$ maps an event $e$ to a number $\hat{T}(e)$. It maps events such that for any two distinct events $e$ and $e'$, $\hat{T}(e)$ and $\hat{T}(e')$ cannot have the same value—either $\hat{T}(e)$ is greater than or lesser than $\hat{T}(e')$. Furthermore, if $e$ causes $e'$, $\hat{T}(e)$ is less than $\hat{T}(e')$.

Implementation

We can implement logical clocks in a distributed system by associating a counter $\hat{T}_p$ with each process $p$. When $p$ sends a message, it includes a timestamp, which is the value of $\hat{T}_p$ when $p$ sends the message. The value of $\hat{T}_p$ is updated as follows:

1. Process $p$ increases $\hat{T}_p$ after each event at $p$.

2. When $p$ receives a message with a timestamp $\tau$, $p$ resets $\hat{T}_p$ based on the following equation: