Linear Space Boostrap Communication Scheme

We consider a system of $n$ processes with ids not a priori known, that are drown 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 $\Theta(n^2)$ MWMR registers. To obtain these results, the paper shows how the processes can \emph{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 processor forever. By doubling the space complexity, using $2n-1$ rather than just $n$ registers, processes can erase each other's write operation, just a bounded number of times, and consequently the computation is wait-free rather than non-blocking.

Data and Resources

Additional Info

Field Value
Source https://hal.science/hal-00717235
Author Delporte-Gallet, Carole, Fauconnier, Hugues, Gafni, Eli, Rajsbaum, Sergio
Maintainer CCSD
Last Updated November 4, 2026, 04:03 (UTC)
Created November 4, 2026, 04:03 (UTC)
Identifier hal-00717235
Language en
Rights https://about.hal.science/hal-authorisation-v1/
contributor Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA) ; Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS)
creator Delporte-Gallet, Carole
date 2012-05-21T00:00:00
harvest_object_id fff52b82-7e26-4908-8d9f-ec6004fd8d72
harvest_source_id 3374d638-d20b-4672-ba96-a23232d55657
harvest_source_title test moissonnage SELUNE
metadata_modified 2026-10-28T00:00:00
set_spec type:UNDEFINED