Technical Report CS0506

Title: Impossibility Results for Decision Protocols (Revised Version of TR 1445)
Authors: Gadi Taubenfeld
Abstract: Fischer, Lynch and Paterson have shown that in completely asunchronous systems there cannot exist a (nontrivial) cosensus protocol that tolerates a single process failure. Based on this result Moran and Wolfstahl proved the nonexistence of fault tolerant protocols for other interesting problems. In this paper we extend these results by using a new proof technique presented by Chandy and Misra. We show that a wide class of asynchronous decision protocols (i.e., protocols where each process is to "decide" on a certain value) cannot tolerate even a single process failure. This class is characterized by the property that as soon as all processes except one have made their decisions, the eventual decision value of the remaining process is uniquely determined. Many protocols such as consensus, choosing a leader, ranklng, matching, constructing a spanning tree as well as sorting and rotating belong to that class. The impossibility proof exhibits the following features: It is not required that the processes be detenninistic, it is not based on previous results and the arguments are non-operational.
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 1988
To the main CS technical reports page

Computer science department, Technion