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.

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.)

do we need this link?
1356 created > 2013-09-16 12:07:32 +0200
1357 creator (registered) > jfw
1359 urn:about:/hoist#seeAlso > http://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-593.html

14 comment