I. Introduction
State machine replication (SMR) is a classical technique to implement a fault-tolerant service, by creating several copies of the service and ordering the client commands across replicas. Some recent works [1], [2] observe that replicas need to order only non-commuting commands, and thus that commuting commands may execute in two message delays, sidestepping the time complexity lower bound on consensus [3]. Lamport [2] names the task of agreeing on this partial order, the Generalized Consensus problem.