Safely overwriting decided slots

Abstract

Techniques are described for safely overwriting decided slots and in-order fault tolerant consensus logs for replicated services. Using techniques described herein, a broad class of already-existing consensus log protocols may be enhanced/extended to safely overwrite decided slots and provide in-order fault tolerant consensus logs. When changing to a different epoch of a consensus log, slots determined to be unreachable may be changed/deleted even if slots after the gap were decided. A sequencer protocol establishes distributed consensus among a group of services. The sequencer protocol provides in-order execution of messages from multiple clients, and flow control from within the sequencer protocol, without offloading de-duplicate and reorder (DDRO) logic to the application layer. Fault tolerance is provided by egress cursors and ingress cursors, which provide awareness of which specific messages from each client sender should be executed next, even if those messages are not presently in the consensus log.