Average probe complexity in quorum systems
Yehuda Hassin, David Peleg · 2001
This paper discusses the probe complexity of randomized algorithms and the deterministic average case probe complexity for some classes of non-dominated coteries, including majority, crumbling walls, tree, wheel and hierarchical quorum systems, and presents upper and lower bounds for the probe complexity of quorum systems in these classes.