Ver Post

Inesc - ID - Talk by Michel Raynal

13 Novembro 2014, 12:54 - Maria Lucília Gonçalves Abreu

Appeared in PODC 2014
This talk presents a new round-based asynchronous consensus algorithm that copes with  up to t<n/3 Byzantine processes, where  n is the total number  of processes. In addition of  being signature-free and optimal with respect to the value of  t, this algorithm  has several noteworthy properties:  the expected number of rounds to decide is four, each round  is composed of two or three communication steps and involves $O(n²) messages, and a message is composed of a round number plus a single bit.  To  attain this  goal, the  consensus algorithm  relies on  a common coin as defined by Rabin, and a new extremely simple and powerful broadcast abstraction suited to binary values. The main  target when  designing this algorithm was to obtain a cheap and simple algorithm.   This was motivated by the fact that, among the  first-class properties, simplicity –albeit sometimes under-estimated or even  ignored-- is a major  one.
Keywords: Abstraction, Asynchronous message-passing system,  Broadcast abstraction, Byzantine process, Common coin, Consensus, Distributed algorithm, Optimal resilience, Randomized algorithm, Signature-free algorithm, Simplicity.
The information are available here