On a Unified Framework for the Evaluation of Distributed Quorum Attainment Protocols

ABSTRACT

Quorum attainment protocols are an important part of many mutual exclusion algorithms. Assessing the performance of such protocols in terms of number of messages, as is usually done, may be less significant than being able to compute the delay in attaining the quorum. Some protocols achieve higher reliability at the expense of increased message cost or delay. A unified analytical model which takes into account the network delay and its effect on the time needed to obtain a quorum is presented. A combined performability metric, which takes into account both availability and delay, is defined, and expressions to calculate its value are derived for two different reliable quorum attainment protocols: D. Agrawal and A. El Abbadi's (1991) and Majority Consensus algorithms (R.H. Thomas, 1979). Expressions for the primary site approach are also given as upper bound on performability and lower bound on delay. A parallel version of the Agrawal and El Abbadi protocol is introduced and evaluated. This new algorithm is shown to exhibit lower delay at the expense of a negligible increase in the number of messages exchanged. Numerical results derived from the model are discussed.

REFERENCES

• 1: Divyakant Agrawal , Amr El Abbadi, An efficient and fault-tolerant solution for distributed mutual exclusion, ACM Transactions on Computer Systems (TOCS), v.9 n.1, p.1-20, Feb. 1991 [doi>10.1145/103727.103728]
• 2: Peter A. Alsberg , John D. Day, A principle for resilient sharing of distributed resources, Proceedings of the 2nd international conference on Software engineering, p.562-570, October 13-15, 1976, San Francisco, California, United States
• 3: José M. Bernabéu-Aubán , Mustaque Ahamad, Applying a Path-Compression technique to Obtain an Efficient Distributed Mutual Exclusion Algorithm, Proceedings of the 3rd International Workshop on Distributed Algorithms, p.33-44, September 26-28, 1989
• 4: 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]
• 5: David K. Gifford, Weighted voting for replicated data, Proceedings of the seventh ACM symposium on Operating systems principles, p.150-162, December 10-12, 1979, Pacific Grove, California, United States [doi>10.1145/800215.806583]
• 6: Joseph L. Hammond , Peter P. O'Reilly, Performance analysis of local computer networks, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 7: Leonard Kleinrock, Theory, Volume 1, Queueing Systems, Wiley-Interscience, 1975
• 8: {8} L. Kleinrock, <i>Queueing Systems, Volume II: Computer Applications</i>. New York: Wiley, 1976.
• 9: M. H. MacDougall, Simulating computer systems: techniques and tools, MIT Press, Cambridge, MA, 1987
• 10: Mamoru Maekawa, A N algorithm for mutual exclusion in decentralized systems, ACM Transactions on Computer Systems (TOCS), v.3 n.2, p.145-159, May 1985 [doi>10.1145/214438.214445]
• 11: Sampath Rangarajan , Sanjeev Setia , Satish K. Tripathi, A Fault-Tolerant Algorithm for Replicated Data Management, Proceedings of the Eighth International Conference on Data Engineering, p.230-237, February 03-07, 1992
• 12: Kerry Raymond, A tree-based algorithm for distributed mutual exclusion, ACM Transactions on Computer Systems (TOCS), v.7 n.1, p.61-77, Feb. 1989 [doi>10.1145/58564.59295]
• 13: Glenn Ricart , Ashok K. Agrawala, An optimal algorithm for mutual exclusion in computer networks, Communications of the ACM, v.24 n.1, p.9-17, Jan. 1981 [doi>10.1145/358527.358537]
• 14: {14} S. Ross, <i>Introduction to Probability Models</i>, 4th ed. New York: Academic Press, 1989.
• 15: Beverly A. Sanders, The information structure of distributed mutual exclusion algorithms, ACM Transactions on Computer Systems (TOCS), v.5 n.3, p.284-299, Aug. 1987 [doi>10.1145/24068.28052]
• 16: Mukesh Singhal, A Heuristically-Aided Algorithm for Mutual Exclusion in Distributed Systems, IEEE Transactions on Computers, v.38 n.5, p.651-662, May 1989 [doi>10.1109/12.24268]
• 17: M. Singhal, A Dynamic Information-Structure Mutual Exclusion Algorithm for Distributed Systems, IEEE Transactions on Parallel and Distributed Systems, v.3 n.1, p.121-125, January 1992 [doi>10.1109/71.113087]
• 18: R. M. Smith , Kishor S. Trivedi , A. V. Ramesh, Performability Analysis: Measures, an Algorithm, and a Case Study, IEEE Transactions on Computers, v.37 n.4, p.406-417, April 1988 [doi>10.1109/12.2184]
• 19: Ichiro Suzuki , Tadao Kasami, A distributed mutual exclusion algorithm, ACM Transactions on Computer Systems (TOCS), v.3 n.4, p.344-349, Nov. 1985 [doi>10.1145/6110.214406]
• 20: Robert H. Thomas, A Majority consensus approach to concurrency control for multiple copy databases, ACM Transactions on Database Systems (TODS), v.4 n.2, p.180-209, June 1979 [doi>10.1145/320071.320076]

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Mutual exclusion

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.5 Reliability
          Subjects: Fault-tolerance
      D.4.7 Organization and Design
          Subjects: Distributed systems

General Terms:
Algorithms, Performance, Reliability

Keywords:
Majority Consensus algorithms, delay analysis, distributed algorithms, distributed quorum attainment protocols, distributed systems, fault tolerance, mutual exclusion algorithms, network delay, parallel version, performability, performability metric, performance analysis, primary site approach, protocol performance, protocols, software fault tolerance, software performance evaluation, tree-based mutual exclusion protocols, unified analytical model, unified framework