ON A UNIFIED FRAMEWORK FOR THE EVALUATION OF DISTRIBUTED QUORUM ATTAINMENT PROTOCOLS

Quorum attainment protocols are an important part of many mutual exclu sion algorithms. Assessing the performance of such protocols in terms of number of messages, as is usually done, may be less significant tha n being able to compute the delay in attaining the quorum. Some protoc ols achieve higher reliability at the expense of increased message cos t or delay. A unified analytical model which takes into account the ne twork delay and its effect on the time needed to obtain a quorum is pr esented. A combined performability metric, which takes into account bo th availability and delay, is defined in this paper, and expressions t o calculate its value are derived for two different reliable quorum at tainment protocols: Agrawal and El Abbadi's and Majority Consensus alg orithms. Expressions for the Primary Site approach are also given as u pper bound on performability and lower bound on delay. A parallel vers ion 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 r esults derived from the model are discussed.