کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
433979 | 689665 | 2015 | 12 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Linear space bootstrap communication schemes Linear space bootstrap communication schemes](/preview/png/433979.png)
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)Θ(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−1n−1 MWMR registers.The paper also presents a wait-free emulation, using 2n−12n−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.
Journal: Theoretical Computer Science - Volume 561, Part B, 4 January 2015, Pages 122–133