Restricted failure detectors: Definition and reduction protocols

This paper investigates unreliable failure detectors with restricted properties, in the context of asynchronous distributed systems made up of n processes where at most f may crash. "Restricted" means that the completeness and the accuracy properties defining a failure detector class are not required to involve all the correct processes but only k and k' of them, respectively (k are involved in the completeness property, and k' in the accuracy property). These restricted properties define the classes R(k, k') and lozenge R(k, k') of unreliable failure detectors. A reduction protocol that transforms a restricted failure detector into its non-restricted counterpart is presented. It is shown that the reduction requires k + k' > n (to be safe) and max(k, k') less than or equal to n - f (to be live). So, when these two conditions are satisfied, R(k, k') and lozenge R(k, k') are equivalent to the Chandra-Toueg's failure detector classes S and lozenge S, respectively. This theoretical transformation is also interesting from a practical point of view because the restricted properties are usually easier to satisfy than their non-restricted counterparts in asynchronous distributed systems. (C) 1999 Elsevier Science B.V. All rights reserved.