Technical Report CS0924

Title: The Combinatorial Structure of Wait-free Solvable Tasks
Authors: Hagit Attiya and Sergio Rajsbaum
Abstract: This paper presents a self-contained study of wait-free solvable tasks. A new necessary and sufficient condition for wait-free solvability is proved, providing a characterization of the wait-free solvable tasks. The condition is based on a restricted set of executions, which induce a very simple to understand structure. The necessary condition is used to prove tight bounds for renaming and $k$-set consensus. The framework is based on topology, but uses only elementary combinatorics, and, in contrast to previous works, does not rely on algebraic or geometric arguments.
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 or PS files directly. The latter URLs may change without notice.

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

Computer science department, Technion