Back to results
US 11,899,654 B2Granted
Linear byzantine agreement
AssigneeVMware, Inc.
InventorAlexander Spiegelman
Life of this patent
Estimating the term…
Abstract
An optimistic byzantine agreement protocol (the protocol) first tries to reach agreement via an efficient deterministic algorithm (synchronous protocol) that relies on synchrony for termination. If an agreement is not reached (e.g., due to asynchrony), the protocol uses a randomized asynchronous algorithm (asynchronous protocol) for fallback. Although randomized asynchronous algorithms are considered to be costly, the rationale here is to bound communication in non-synchronous runs after an equivalent cost has already paid.
Claims20
A non-transitory computer-readable storage medium having stored thereon computer executable instructions executable by each party pi among n parties for reaching agreement on a proposed value via an instance of a Byzantine agreement protocol, the computer executable instructions causing party pi to:
- run a synchronous agreement sequence of the instance of the Byzantine agreement protocol on the proposed value by instantiating, in sequential order, one or more view instances using a different party among the n parties as leader for each view instance, wherein the leader in a view instance sends a sequence of messages to all n parties to commit to the proposed value;
- send a help message to all n parties when party pi has not committed to the proposed value in a previous view instance in the one or more view instances, the help message being a request to each of the n parties to return a help reply message that includes a commit certificate indicating that said each party committed to the proposed value in the previous view instance;
- upon receiving help reply messages from at least a predetermined number of the n parties, commit to the proposed value and halt the instance of the Byzantine agreement protocol;
- and
- upon receiving help messages from at least the predetermined number of the n parties, transition from running the synchronous agreement sequence to running an asynchronous agreement sequence of the instance of the Byzantine agreement protocol on the proposed value, the running of the asynchronous agreement sequence comprising:
- instantiating a wave comprising a plurality of concurrently executing views with a different leader for each view;
- and
- when a predetermined number of executing views have completed:
- electing a new leader from among the n parties;
- and
- exchanging a commit state of the new leader among the n parties.
8 more elements
An apparatus (party pi) comprising:
- one or more computer processors;
- and
- a computer-readable storage medium comprising instructions for controlling party pi to reach agreement among n parties to a proposed value via an instance of a Byzantine agreement protocol, wherein the instructions control party pi to:
- run a synchronous agreement sequence of the instance of the Byzantine agreement protocol on the proposed value by instantiating, in sequential order, one or more view instances using a different party among the n parties as leader for each view instance, wherein the leader in a view instance sends a sequence of messages to all n parties to commit to the proposed value;
- send a help message to all n parties when party pi has not committed to the proposed value in a previous view instance in the one or more view instances, the help message being a request to each of the n parties to return a help reply message that includes a commit certificate indicating that said each party committed to the proposed value in the previous view instance;
- upon receiving help reply messages from at least a predetermined number of the n parties, commit to the proposed value and halt the instance of the Byzantine agreement protocol;
- and
- upon receiving help messages from at least the predetermined number of the n parties, transition from running the synchronous agreement sequence to running an asynchronous agreement sequence of the instance of the Byzantine agreement protocol on the proposed value, the running of the asynchronous agreement sequence comprising:
- instantiating a wave comprising a plurality of concurrently executing views with a different leader for each view;
- and
- when a predetermined number of executing views have completed:
- electing a new leader from among the n parties;
- and
- exchanging a commit state of the new leader among the n parties.
11 more elements
A method for achieving agreement among a plurality of computing systems to a proposed value via an instance of a Byzantine agreement protocol, the method comprising, by a first computing system among the plurality of computing systems:
- running a synchronous agreement sequence of the instance of the Byzantine agreement protocol on the proposed value by instantiating, in sequential order, one or more view instances using a different computing system among the plurality of computing systems as a leader for each view instance, wherein the leader in a view instance sends a sequence of messages to each computing system among the plurality of computing systems to commit to the proposed value;
- sending a help message to each computing system among the plurality of computing systems when the first computing system has not committed to the proposed value in a previous view instance in the one or more view instances, the help message being a request to each of the plurality of computing systems to return a help reply message that includes a commit certificate indicating that said each computing system committed to the proposed value in the previous view instance;
- upon receiving help reply messages from at least a predetermined number of the plurality of computing systems, committing to the proposed value and halting the instance of the Byzantine agreement protocol;
- and
- upon receiving help messages from at least the predetermined number of the plurality of computing systems, transitioning from running the synchronous agreement sequence to running an asynchronous agreement sequence of the instance of the Byzantine agreement protocol on the proposed value, the running of the asynchronous agreement sequence comprising:
- instantiating a wave comprising a plurality of concurrently executing views with a different leader for each view;
- and
- when a predetermined number of executing views have completed:
- electing a new leader from among the plurality of computing systems;
- and
- exchanging a commit state of the new leader among the plurality of computing systems.
8 more elements
Dependencies are inferred from the claim text.