## The Notion of Veto Number and the Respective Power of <>P and <>S to Solve One-Shot Agreement Problems

### Authors

- Roy Friedman, Technion
- Achour Mostefaoui, IRISA
- Michel Raynal, IRISA

### Abstract

Unreliable failure detectors are abstract devices that, when added
to asynchronous distributed systems, Enable solving distributed
computing problems (e.g., Consensus) that otherwise would be
impossible to solve in these systems. This paper focuses on two
classes of failure detectors defined by Chandra and Toueg,
namely, the classes denoted <>P (*eventually
perfect*) and <>S (*eventually strong*). Both
classes include failure detectors that eventually detect
permanently all process crashes, but while the failure detectors
of <>P eventually make no erroneous suspicions,
the failure detectors of <>S are only required to
eventually not suspect a single correct process.
This paper addresses the following question related
to the comparative power of these classes, namely:
``Are there one-shot agreement problems that can be solved
in asynchronous distributed systems with reliable links but prone
to process crash failures augmented with <>P,
but cannot be solved when those systems are augmented with
<>S?'' Surprisingly, the paper shows that the
answer to this question is ``no''. An important consequence of
this result is that <>P cannot be the weakest
class of failure detectors that enables solving one-shot agreement
problems in unreliable asynchronous distributed systems. These
results are then extended to the case of more severe failure
modes.