A Separation of n-consensus and (n + 1)-consensus Based on Process Scheduling
Résumé
A fundamental research theme in distributed computing is the comparison of systems in terms of their ability to solve basic problems such as consensus that cannot be solved in completely asynchronous systems. In particular, in a seminal work [12], Herlihy compares shared-memory systems in terms of the shared objects that they have: he proved that there are shared objects that are powerful enough to solve consensus for n processes, but are too weak to solve consensus for n + 1 processes; such objects are placed at level n of a wait-free hierarchy.
As in [12], we compare shared-memory systems with respect to their ability to solve consensus for n processes. But instead of comparing systems defined by the shared objects that they have, we compare read-write systems defined by the set of process schedules that can occur in these systems. Defining systems this way can capture many types of systems, e.g., systems whose synchrony ranges from fully synchronous to completely asynchronous, several systems with failure detectors, and “obstruction-free” systems. In this paper, we consider read-write systems defined in terms of sets of process schedules, and investigate the following fundamental question: Is there a system of n + 1 processes such that consensus can be solved for every subset of n processes in the system, but consensus cannot be solved for the n + 1 processes of the system? We show that the answer to the above question is “yes”, and so these systems can be classified into hierarchy akin to Herlihy’s hierarchy.