VMware, Inc.
SYNCHRONOUS STATE MACHINE REPLICATION FOR ACHIEVING CONSENSUS

Abstract:

A distributed service includes replicas that communicate with each other over a network to commit a block of client requests to a log of blocks of client requests. Each replica receives from one of the replicas, designated as the leader, a proposal for committing a new block to the log, and sends a vote on the proposed block to all of the other replicas via the network. Each replica then starts a timer set to twice the maximum network delay time to transmit messages over the network. If there is no equivocation when the timer lapses or stalling condition in proposing new blocks, then each replica commits the proposed block to the log. If there is equivocation or stalling condition, then a new leader is selected, and the process re-attempts to commit the proposed block.