(Almost) All Objects Are Universal in Message Passing Systems

摘要

This paper shows that all shared atomic object types that can solve consensus among k > 1 processes have the same weakest failure detector in a message passing system with process crash failures. In such a system, object types such as test-and-set, fetch-and-add, and queue, known to have weak synchronization power in a shared memory system are thus, in a precise sense, equivalent to universal types like compare-and-swap, known to have the strongest synchronization power. In the particular case of a message passing system of two processes, we show that, interestingly, even a register is in that sense universal.