Technical Report CS0888

Title: On the Robustness of h^r_m
Authors: Shlomo Moran and Lihu Rappoport
Abstract: We introduce an $N$-process deterministic concurrent object for $N\geq 3$ processes. This object, denoted as \w, is hard-wired in the sense that each process $P$ can access it using a single fixed port (though $P$ can use different ports in different copies of \w). We prove that \w satisfies the following properties: - There is no consensus protocol for three processes which uses many shared registers and many copies of \w\ (and does not use any other object); but - There is a consensus protocol for $N$ processes which uses one copy of \w\ and $(N choose 3)$ copies of $\CO{3}$, where $\CO{3}$ is the standard consensus object for three processes. This implies that the hierarchy $h^r_m$ is not robust for deterministic hard-wired objects. Keywords: concurrent objects, consensus numbers, wait-free hierarchies, robustness.
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 1996
To the main CS technical reports page

Computer science department, Technion