Mutual inclusion in asynchronous message-passing distributed systems

• The mutual inclusion problem is a problem such that at least one process is in critical section.
• This paper proposes two distributed solutions in the asynchronous message passing model.
• We discuss the relation between mutual inclusion and mutual exclusion.

In the mutual inclusion problem, at least one process is in the critical section. However, only a solution for two processes with semaphores has been reported previously. In this study, a generalized problem setting is formalized and two distributed solutions are proposed based on an asynchronous message-passing model. In the local problem setting (the local mutual inclusion problem), for each process PP, at least one of PP and its neighbors must be in the critical section. For the local problem setting, a solution is proposed with O(Δ)O(Δ) message complexity, where ΔΔ is the maximum degree (number of neighboring processes) of a network. In a global setting (the global mutual inclusion problem), at least one of the processes must be in the critical section. For the global problem setting, a solution is proposed with O(|Q|)O(|Q|) message complexity, where |Q||Q| is the maximum size for the quorum of a coterie used by the algorithm, which is typically |Q|=n, where nn is the number of processes in a network.