The Generalized Loneliness Detector and Weak System Models for k-Set Agreement

This paper presents two weak partially synchronous system models ${\cal M}^{{\rm anti}(n-k)}$ and ${\cal M}^{{\rm sink}(n-k)}$, which are just strong enough for solving $k$-set agreement: We introduce the generalized $(n-k)$-loneliness failure detector ${\cal L}(k)$, which we first prove to be sufficient for solving $k$-set agreement, and show that ${\cal L}(k)$ but not ${\cal L}(k-1)$ can be implemented in both models. ${\cal M}^{{\rm anti}(n-k)}$ and ${\cal M}^{{\rm sink}(n-k)}$ are hence the first message passing models that lie between models where $\Omega$ (and therefore consensus) can be implemented and the purely asynchronous model. We also address $k$-set agreement in anonymous systems, that is, in systems where (unique) process identifiers are not available. Since our novel $k$ -set agreement algorithm using ${\cal L}(k)$ also works in anonymous systems, it turns out that the loneliness failure detector ${\cal L}={\cal L}(n-1)$ introduced by Delporte et al. is also the weakest failure detector for set agreement in anonymous systems. Finally, we analyze the relationship between ${\cal L}(k)$ and other failure detectors suitable for solving $k$-set agreement.