BALL

This page has three main sections. (Note that the listings could be empty.) more… Tip: Remember the back-button! And don't click the number on the left.

  1. The first item displays a term, URL, text or picture.
  2. Followed by a (still unordered) listing of statements about this subject. (for details follow ">"-link)
  3. Separated by a horizontal rule a "reverse" listing of statements referring to this item in object position.
14
1354 comment >

The optimistic latency of Byzantine Paxos can be reduced from three communication steps to two, without using public-key cryptography. This is done by making a decision when more than (n+3f)/2 acceptors report to have received the same proposal from the leader, with n being the total number of acceptors and f the number of the faulty ones. No further improvement in latency is possible, because every Consensus algorithm must take at least two steps even in benign settings. Moreover, if the leader is correct, our protocol achieves the latency of at most three steps, even if some other processes fail. These two properties make this the fastest Byzantine agreement protocol proposed so far.

By running many instances of this algorithm in parallel, we can implement Vector Consensus and Byzantine Atomic Broadcast in two and three steps, respectively, which is two steps faster than any other known algorithm.


It should be easy follow this modified counting in [SACSP)(?v=search&id=1251) too.

(The second paragraph – running the algorithm in parallel is commonplace with BALL since several years and will not require any modifications.)

1347 is a > issue
1350 title > Paxos at war
1352 state > accepted

ball.askemos.org/FeatureRequests comment
issue container member