randomized k-set agreement
The k-Set Agreement problem generalizes the consensus problem (which corresponds to the case k = 1). The processes propose values and each correct process has to decide a value such that (1) a decided value is a proposed value, and (2) no more than k distinct values are decided. Let f be the maximum number of processes that can crash. It has first been shown that the consensus problem cannot be solved in asynchronous distributed systems when f > 0 (this is the well-known FLP's impossibility result). It has then been shown that this impossibility still holds for the k -set agreement problem when f &gne; k . In the case of the consensus problem, two main approaches have been investigated to circumvent this impossibility: randomization and unreliable failure detectors. For the more general case of the k -set agreement problem, the failure detector approach has recently been investigated. This paper presents a randomization approach to solve the k -set agreement problem in asynchronous distributed systems in which f &gne; k . It requires that at least a majority of processes be correct. The proposed protocol does not require the a priori knowledge of the set of values proposed by processes. It relies on a relatively simple combination of reliable broadcast with randomization. Interestingly, the proposed protocol shows that more choices allow more faults or more efficient runs.
k-set agreement consensus fault-tolerance randomized protocol asynchronous system