the adaptive M-renaming problem consists of providing processes with a new name taken from a name space whose size M depends only oil the number p of processes that participate in the renaming (and not oil the total n...
详细信息
the adaptive M-renaming problem consists of providing processes with a new name taken from a name space whose size M depends only oil the number p of processes that participate in the renaming (and not oil 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 bestthat 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 oil 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 < n). the first contribution is a t-resilient algorithmthat solves the k-set agreement problem from any adaptive (p + k - 1)-renaming algorithm. the second contribution considers the case k < t. It shows thatthere is no such wait-free algorithm when k < n/2 (wait-free means t = n - 1). So, while a solution to the adaptive (,p + k - 1)renaming problem allows t-resiliently solving the k-set agreement problem despite t = k failures, when k < t such an additional power becomes useless for the values of n > 2k (i.e. adaptive (p + k - 1)-renaming allows progressing from k > tto k = t, but does not allow bypassing the "k = t" frontier when n > 2k). (C) 2008 Elsevier B.V. All rights reserved.
暂无评论