Randomized k-set agreement
Achour Mostéfaoui, Michel Raynal · 2001
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 ⪈ k.