Patent ID: 7849223

Claim:
A method for updating a fault tolerant state machine comprising a plurality of computing devices using a fault tolerant, quorum-based consensus protocol, comprising: a leader of the plurality of computing devices generating a first data state update for the state machine resulting from a first request from a first client operating on the state machine, where the first data state update comprises a first ballot number; the leader proposing the first data state update to the plurality of computing devices; the leader generating a second data state updates for the state machine resulting from a second requests from a second client operating on the state machine, the second data state update comprising a second ballot number; the leader proposing the second data state update to the plurality of computing devices prior to receiving a quorum of acknowledgements from the plurality of computing devices for the first data state update; the state machine implementing the first data state update, if the quorum of acknowledgements is received for the first data state update; and the state machine implementing the second data state update, if a quorum of acknowledgements is received from the plurality of computing devices for the second data state update.