Computability and complexity results for agreement problems in shared-memory distributed systems
Faith Ellen Fich, E. Schenk · 1996
Agreement problems are central to the study of wait-free protocols for shared memory distributed systems. We examine two specific issues arising out of this study. We consider the complexity of the wait-free approximate agreement problem in an asynchronous shared memory comprised of only single-bit multi-writer multi-reader registers. For real-valued inputs of magnitude at most s and a real-valued accuracy requirement $\varepsilon>0$ we show matching upper and lower bounds of $\Theta(\log(s/\varepsilon))$ steps and shared registers. For inputs drawn from any fixed finite range this is significantly better than the best possible algorithm for single-writer multi-reader registers, which, for n processes, requires $\Omega(\log n)$ steps. These results are used to show a separation between the wait-free single-writer multi-reader and wait-free multi-writer multi-reader models of computation. The consensus hierarchy characterizes the strength of a shared object by its ability to solve the consensus problem in a wait-free manner. One important application of a hierarchy classifying the power of objects is to compare the power of systems offering different collections of objects. Ideally, a hierarchy should reduce the task of determining the strength of an architecture supporting shared memory distributed systems to the problem of determining the strength of each type of shared object supported by the architecture. Informally, a hierarchy that allows this is robust. Several variations of the consensus hierarchy have appeared in the literature, and it has been shown that all but one of them are not robust. The remaining hierarchy, named $h\sbsp{m}{r},$ has been the subject of considerable research. We show that, in a natural setting, the consensus hierarchy $h\sbsp{m}{r}$ is not robust.