Michel Raynal,

Institut Universitaire de France –

Abstract:

This talk presents a new round-based asynchronous consensus algorithm that copes with up to 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.

*(this is a joint work with Achour Mostéfaoui, and Hamouma Moumen)

 

Date: 2014-Nov-14     Time: 16:00:00     Room: 020

For more information: