(anti－Ω~x×∑_z)-Based k-Set Agreement Algorithms

摘要

This paper considers the k-set agreement problem in a crash-prone asynchronous message passing system enriched with failure detectors. Two classes of failure detectors have been previously identified as necessary to solve asynchronous k-set agreement: the class anti-leader anti－Ω~k and the weak-quorum class ∑k- The paper investigates the families of failure detector (anti－Ω~x)_(1≤x≤n) and (∑_z)_(1≤z≤n). It characterizes in an n processes system equipped with failure detectors anti－Ω~x and ∑_z for which values of k, x and z k-set-agreement can be solved. While doing so, the paper (1) disproves previous conjunctures about the weakest failure detector to solve k-set-agreement in the asynchronous message passing model and, (2) introduces the first indulgent algorithm that tolerates a majority of processes failures.