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