Abstract
In this paper, we propose an O(1) fault-tolerant mutual exclusion algorithm in dynamic distributed systems. We achieve low message cost and high fault tolerant ability in the basic scheme of our algorithm by adoptng a partially centralized policy. Then the basic scheme is reinforced with a dynamic coterie protocol that dynamically changes the coterie. It change its coterie to remain high performance under system failures or to balance the system load among the nodes. After that, we introduce the global state object. By maintaining proper global state objects, most distributed problems such as the k mutual exclusion, the k-out of-M mutual exclusion, and the termination detection can be easily solved with only O(1) message cost.