On FTSS-Solvable Distributed Problems
Joffroy Beauquier, Synnöve Kekkonen–Moneta · McGill-Queen's University Press eBooks · 1997
We investigate which distributed problems can be solved with so-called k-ftss protocols. K-ftss protocols combine two types of failure resilience, k-fault-tolerance (k-ft), i.e., resilience to up to k process failures, and self-stabilization (ss), i.e., resilience to arbitrary memory and message corruption. We show that if a problem is k-fault-sensitive on a (j, k)-restrictable process network, then there exists no k-ftss protocol for solving the problem on that network. Instead, when either condition does not hold, then there can be a k-ftss solution. We present several 1-ftss protocols for rings. We first propose a randomized solution to 2-COL on anonymous rings of even size. We then present a generic deterministic I-ftss protocol that can be used to produce 1-ftss solutions to 2-COL, orientation and non-trivial eventual consensus on rings where processes have identifiers.