Technical Report CS0408

Title: An Extended Impossibility Result for Asynchronous Complete Networks
Authors: S. Moran and Y. Wolfstahl
Abstract: It is proved that a large class of distributed tasks cannot be solved in presence of faulty processors. This class contains tasks whose unsolvability in presense of faults is known (the consensus task and its variants, cf. [FLP]) as well as some new tasks. In particular, we introduce the notion of desicion graph of a task, and show that every problem whose decision graph is disconnected cannot be solved in the presence of one faulty processor, by reducing the unsolvabllity of this problem to the unsolvability of the consensus problem. The notion of unsolyability used here is very weak: We say that a protocol solves a given problem if in any execution it satisfies (1) all non faulty processors eyentually halt, and (2) if no processor is faulty, it solves the probiem. Hence, the unsolvability of a problem in this model implies its unsolvability in other models appearing in the literature.
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 1986
To the main CS technical reports page

Computer science department, Technion