کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
437903 | 690205 | 2009 | 8 صفحه PDF | دانلود رایگان |
The adaptive M-renaming problem consists of providing processes with a new name taken from a name space whose size M depends only on the number p of processes that participate in the renaming (and not on the total number n of processes that could ask for a new name). The k-set agreement problem allows each process that proposes a value to decide a proposed value in such a way that at most k different values are decided. In an asynchronous system prone to up to t process crash failures, and where processes can cooperate by accessing atomic read/write registers only, the best that can be done is a renaming space of size M=p+t. In the same setting, the k-set agreement problem cannot be solved when t≥k.This paper focuses on the way a solution to the adaptive renaming problem can help in solving the k-set agreement problem when t≥k. It has two contributions. Considering the case k=t (1≤t
Journal: Theoretical Computer Science - Volume 410, Issue 14, 28 March 2009, Pages 1328-1335