Average Probe Complexity of Non-dominated Coteries
Tiko Kameda, Feng Xiao, Malika Guerni-Mahoui
To appear at Nineteenth Annual
ACM SIGACT-SIGOPS Symposium on PRINCIPLES OF DISTRIBUTED COMPUTING (PODC
2000), Portland, Oregon, 16-19 July 2000
Abstract
Consider a coterie over a finite set U, which represents the nodes in a
distributed system. To achieve mutual exclusion, it is required to collect
votes from a quorum of nodes by probing them. When nodes may fail, the
number of probes required to find a quorum of operational nodes may vary.
We intdoduce the ``probe tree" to represent an adaptive probing strategy
based on a given "non-dominated" coterie, and investigate the problem of
finding an optimal probe tree, which minimizes the expected number of probes.
Since this problem appears intractable, we present heuristics and evaluate
their performance. We also discuss the special case of practical importance,
where the probability of the failure is very small.