Loading...
Please wait, while we are loading the content...
Similar Documents
Linear Space Boostrap Communication Scheme
| Content Provider | Hyper Articles en Ligne (HAL) |
|---|---|
| Author | Delporte-Gallet, Carole Fauconnier, Hugues Gafni, Eli Rajsbaum, Sergio |
| Abstract | 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. |
| File Format | |
| Language | English |
| Access Restriction | Open |
| Subject Keyword | renaming shared memory read write registers distributed algorithms wait-free space complexity renaming. scco Cognitive science Computer science |
| Content Type | Text |
| Resource Type | Article |
