Consensus numbers of multi-objects
Eric Ruppert · 1998
This paper studies the ability of shared memory distributed systems to solve the wait-free consensus problem if processes are permitted to access more than one shared data object in a single atomic action. Suppose T is any deterministic object type that can be used, with read/write registers, to solve consensus among n processes, with n ? 2. A multiobject of type T m consists of a collection of objects of type T , any m of which can be accessed in a single atomic action. It will be shown that a multi-object of type T m can be used, with registers, to solve consensus among\\Omega\\Gamma n p m) processes. Furthermore, if the type T is equipped with operations that allow processes to read its state without altering the state, then the multi-object can be used with registers to solve consensus among \\Omega\\Gamma nm) processes. Neither of these lower bounds can be improved. 1 Introduction In a shared memory distributed system, processes communicate by accessing shared data objects...