VMware, Inc.
FLEXIBLE BYZANTINE FAULT TOLERANT PROTOCOL USING MESSAGE DELAY UPPER BOUND FOR CLIENT COMMIT DECISION

Abstract:

A replicated service comprises N replicas deployed on compute nodes of a computer network, wherein upon receiving qr*N first votes from other replicas on a proposed transaction by a leader of the N replicas, each of the N replicas certifies the proposed transaction to a client of the replicated service, where qr is a fractional value between 0 and 1 that represents a quorum required for certification. A method of approving a transaction in the replicated service includes receiving the certifications from the N replicas, determining whether or not the certifications are received from at least qc*N replicas, where qc is a fractional value between 0 and 1 that represents a quorum required for transaction approval and qc>qr, and transmitting an approval of the transaction to the replicas for recording by the replicas upon determining that the certifications have been received from at least qc*N replicas.