Linear Space Bootstrap Communication Schemes

Abstract : 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.
Document type :
Conference papers
Liste complète des métadonnées
Contributor : Carole Delporte-Gallet <>
Submitted on : Thursday, December 26, 2013 - 3:47:50 PM
Last modification on : Friday, January 4, 2019 - 5:33:21 PM

Links full text




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⟩



Record views