Distributed Mutual Exclusion

N. Soundarajan and T.-H. Lai (USA)


Distributed mutual exclusion, Information structure,Correctness conditions


One way of characterizing non-token-based mutual exclu sion (m.e.) algorithms is in terms of the underlying infor mation structure. The information structure for a given m.e. algorithm specifies which particular processes inter act with which other processes before entering their critical sections, and which processes they interact with when leav ing their critical sections. By focusing on the information structure of an m.e. algorithm, we can compare different algorithms by comparing the respective information struc tures. Further, we can characterize the correctness of an m.e. algorithm in terms of conditions that its information structure must satisfy. In this paper, we propose a neces sary and sufficient condition for ensuring the correctness of the m.e. algorithm and show that this condition is supe rior to the currently accepted condition.

Important Links:

Go Back