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


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.