PI-1556: Simple and Efficient Oracle-Based Consensus Protocols for
Asynchronous Byzantine Systems
Roy Friedman, Achour Mostefaoui, Michel Raynal
http://www.irisa.fr/bibli/publi/pi/2003/1556/1556.html
26 pages - septembre 2003

Abstract
This paper is on the Consensus problem in asynchronous distributed
systems where (up to f) processes (among n) can exhibit a Byzantine
behavior, i.e., can deviate arbitrarily from their specification. A way
to solve the consensus problem in such a context consists of enriching
the system with additional oracles that are powerful enough to cope with
the uncertainty and unpredictability created by the combined effect of
Byzantine behavior and asynchrony. Considering two types of such
oracles, namely, an oracle that provides processes with random values,
and a failure detector oracle, the paper presents two families of
Byzantine asynchronous consensus protocols. Two of these protocols are
particularly noteworthy: they allow the processes to decide in one
communication step in favorable circumstances. The first is a randomized
protocol that assumes n>5f. The second one is a failure detector-based
protocol that assumes n>6f. These protocols are designed to be
particularly simple and efficient in terms of communication steps, the
number of messages they generate in each step, and the size of messages.
So, although they are not optimal in the number of Byzantine processes
that can be tolerated, they are particularly efficient when we consider
the number of communication steps they require to decide, and the size
of the messages they use. In that sense, they are practically appealing.

Résumé
Cet article adresse le problème du consensus dans les systèmes répartis
où un certain nombre de processus du système peuvent exhiber un
comportement byzantin. Un comportement byzantin est un comportement qui
dévie de la spécification du processus. Un moyen de résoudre le problème
du consensus dans un tel contexte consiste à enrichir le système d'un
oracle assez puissant pour permettre de limiter le ``bruit'' créé par
l'effet combiné des processus byzantins et de l'asynchronie. Nous avons
étudié deux tels oracles, en l'occurrence, un générateur de nombres
aléatoires et un détecteur de défaillances. Nous avons ainsi proposé
deux familles de protocoles simples et efficaces en termes de nombre
d'étapes de calcul, du nombre de messages échangés et de l'usage de
signatures au niveau applicatif.

Keywords: Asynchronous distributed system, Byzantine process,
Distributed algorithm, Fault tolerance, Random oracle, Randomized
protocol, Unreliable failure detector

Mots clefs: Algorithme probabiliste, algorithme réparti, consensus,
détecteur de défaillances non fiable, processus byzantin, système
asynchrone, tolérance aux fautes