Empirical Evaluation of Mutual Exclusion Algorithms for Distributed Systems

✍ Scribed by Shiwa S. Fu; Nian-Feng Tzeng; Jen-Yao Chung

• Publisher: Elsevier Science
• Year: 2000
• Tongue: English
• Weight: 270 KB
• Volume: 60
• Category: Article
• ISSN: 0743-7315
• DOI: 10.1006/jpdc.2000.1635

✦ Synopsis

Mutual exclusion in distributed memory systems is realized by passing messages among sites to establish a sequence for the waiting sites to enter the critical section. We have evaluated various distributed mutual exclusion algorithms on the IBM SP2 machine and the Intel iPSCÂ860 system, with their empirical results compared in terms of such criteria as the number of message exchanges and response time. The results take into account the effects of critical section request rate, critical section duration, and system size. Our results indicate that the Star algorithm (1991, M. L. Neilsen and M. Mizuno, in ``Proc. 11th Int. Conf. Distributed Computing Systems,'' pp. 354 360) achieves the shortest response time in most cases among all the algorithms on a small to medium-sized system, when sites request the critical section many times before involving any barrier synchronization. This is because (1) it requires the exchange of no more than three messages per critical section entry, and (2) contention can quickly be alleviated after several entries into