Structured derivations of consensus algorithms for failure detectors
Jiong Yang, Gil Neiger, Eli M. Gafni · 1998
In a seminal paper, Chandra and Toueg showed how unreliable failure detectors could allows processors to achieve consensus in asynchronous message passing systems. Since then, other researchers have developed consensus algorithms for other systems or based on different failure detectors. Each algorithm was developed and proven independently. This paper shows how a consensus algorithm for any of the standard models can be automatically converted to run in any other. These results show more clearly how the different system models and failure detectors can be related. In addition, they may permit the development of new results for new models also through transformations. 1 Introduction The problem of achieving consensus among processors in a distributed system is fundamental in distributed computing. Unfortunately, consensus cannot be achieved in the presence of failures in completely asynchronous systems, either those with message passing [8,9] or those with shared memory [7,8,12]. Thi...