Clairvoyant state machine replication

We consider the state machine replication problem in semi-synchronous systems subject to Byzantine server failures. We propose a new solution to the problem in the form of a protocol for the generalized consensus problem. The protocol solves the consensus problem in a setting in which information about conflicts between transactions is available (such information can be in the form of transaction read and write sets). Unlike most prior proposals (for generalized or classical consensus), which use a leader to order transactions, this protocol is leaderless, and relies on non-skipping timestamps for transaction ordering. Being leaderless, the protocol does not need to pause for leader elections. The use of non-skipping timestamps permits servers to commit transactions as soon as they know that no conflicting transaction can be ordered earlier. For n servers of which f may be faulty, this protocol requires n>4f.