Average probe complexity in quorum systems

摘要

This paper discusses the probe complexity of randomized algorithms and the deterministic average case probe complexity for some classes of nondominated 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.