| TR#: | CS0924 |
| Class: | CS |
| Title: | The Combinatorial Structure of Wait-free Solvable Tasks |
| Authors: | Hagit Attiya and Sergio Rajsbaum |
| CS0924.pdf | |
| 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. |
| Copyright | The 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 (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/1997/CS/CS0924), 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