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.
Type de document :
Communication dans un congrès
Davide Frey and Michel Raynal and Saswati Sarkar and Rudrapatna K. Shyamasundar and Prasun Sinha. ICDCN 2013 - 14th International Conference Distributed Computing and Networking, Jan 2013, Mumbi, India. Springer, 7730, pp.363-377, 2013, Lecture Notes in Computer Science. 〈10.1007/978-3-642-35668-1_25〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00922420
Contributeur : Carole Delporte-Gallet <>
Soumis le : jeudi 26 décembre 2013 - 15:47:50
Dernière modification le : jeudi 15 novembre 2018 - 20:27:23

Identifiants

Collections

Citation

Carole Delporte-Gallet, Hugues Fauconnier, Eli Gafni, Sergio Rajsbaum. Linear Space Bootstrap Communication Schemes. Davide Frey and Michel Raynal and Saswati Sarkar and Rudrapatna K. Shyamasundar and Prasun Sinha. ICDCN 2013 - 14th International Conference Distributed Computing and Networking, Jan 2013, Mumbi, India. Springer, 7730, pp.363-377, 2013, Lecture Notes in Computer Science. 〈10.1007/978-3-642-35668-1_25〉. 〈hal-00922420〉

Partager

Métriques

Consultations de la notice

192