Skip to Main content Skip to Navigation
New interface
Journal articles

Linear space bootstrap communication schemes

Carole Delporte-Gallet 1 Hugues Fauconnier 1 Eli Gafni 2 Sergio Rajsbaum 3 
1 GANG - Networks, Graphs and Algorithms
LIAFA - Laboratoire d'informatique Algorithmique : Fondements et Applications, Inria Paris-Rocquencourt
Abstract : Consider a system of n processes with ids that are drawn from a large space. How can these n processes communicate to solve a problem? It is shown that linear number of Multi-Writer Multi-Reader (MWMR) registers are sufficient to solve any read-write wait-free solvable problem and needed to solve some read-write wait-free solvable problem. This contrasts with the existing possible solution borrowed from adaptive algorithms that require Θ(n3/2) MWMR registers. To obtain the sufficiency result, the paper shows how the processes can non-blocking emulate a system of n Single-Writer Multi-Reader (SWMR) registers on top of n Multi-Writer Multi-Reader (MWMR) registers. For the necessity result, it shows it is impossible to do such an emulation with n−1 MWMR registers. The paper also presents a wait-free emulation, using 2n−1 rather than just n registers. The emulation can be used to solve an infinite sequence of tasks that are sequentially dependent (processes need the previous task's outputs in order to proceed to the next task). A non-blocking emulation cannot be used in this case, because it might starve a process forever
Document type :
Journal articles
Complete list of metadata
Contributor : Carole Delporte-Gallet Connect in order to contact the contributor
Submitted on : Wednesday, January 6, 2016 - 1:44:38 PM
Last modification on : Tuesday, November 29, 2022 - 12:06:07 PM

Links full text




Carole Delporte-Gallet, Hugues Fauconnier, Eli Gafni, Sergio Rajsbaum. Linear space bootstrap communication schemes. Theoretical Computer Science, 2015, 561, pp.122-133. ⟨10.1016/j.tcs.2014.10.013⟩. ⟨hal-01251557⟩



Record views