Average probe complexity of non-dominated coteries (brief announcement)

ABSTRACT

When nodes may fail, it is desirable to minimize the expected number of probes required to find a quorum. We show some properties of “probe trees”, propose several heuristics for finding an optimal probe strategy, and compare their performance.

REFERENCES

• 1: Hector Garcia-Molina , Daniel Barbara, How to assign votes in a distributed system, Journal of the ACM (JACM), v.32 n.4, p.841-860, Oct. 1985 [doi>10.1145/4221.4223]
• 2: T. Ibaraki , T. Kameda, A Theory of Coteries: Mutual Exclusion in Distributed Systems, IEEE Transactions on Parallel and Distributed Systems, v.4 n.7, p.779-794, July 1993 [doi>10.1109/71.238300 ]
• 3: Mitchell L. Neilsen, A Dynamic Probe Strategy for Quorum Systems, Proceedings of the 17th International Conference on Distributed Computing Systems (ICDCS '97), p.95, May 27-30, 1997
• 4: David Peleg , Avishai Wool, How to be an efficient snoop, or the probe complexity of quorum systems (extended abstract), Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing, p.290-299, May 23-26, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/248052.248112]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.8 Performance
          Subjects: Modeling and prediction

  H. Information Systems
  H.2 DATABASE MANAGEMENT

General Terms:
Performance, Reliability, Theory