Linear Space Bootstrap Communication Schemes - Archive ouverte HAL Access content directly
Conference Papers Year : 2013

Linear Space Bootstrap Communication Schemes


We consider a system of n processes with ids not a priori known, that are drawn from a large space, potentially unbounded. How can these n processes communicate to solve a task? We show that n a priori allocated Multi-Writer Multi-Reader (MWMR) registers are both needed and sufficient to solve any read-write wait free solvable task. This contrasts with the existing possible solution borrowed from adaptive algorithms that require Θ(n 2) MWMR registers. To obtain these results, the paper shows how the processes can non blocking emulate a system of n Single-Writer Multi-Reader (SWMR) registers on top of n MWMR registers. It is impossible to do such an emulation with n − 1 MWMR registers. Furthermore, we want to solve a sequence of tasks (potentially infinite) that are sequentially dependent (processes need the previous task's outputs in order to proceed to the next task). A non blocking emulation might starve a process forever. By doubling the space complexity, using 2n − 1 rather than just n registers, the computation is wait free rather than non blocking.

Dates and versions

hal-00922420 , version 1 (26-12-2013)



Carole Delporte-Gallet, Hugues Fauconnier, Eli Gafni, Sergio Rajsbaum. Linear Space Bootstrap Communication Schemes. ICDCN 2013 - 14th International Conference Distributed Computing and Networking, Jan 2013, Mumbi, India. pp.363-377, ⟨10.1007/978-3-642-35668-1_25⟩. ⟨hal-00922420⟩
111 View
0 Download



Gmail Facebook Twitter LinkedIn More