MUTUAL EXCLUSION IN PARTITIONED DISTRIBUTED SYSTEMS

A network partition can break a distributed computing system into groups of isolated nodes. When this occurs, a mutual exclusion mechanism may be required to ensure that isolated groups do not concurrently perform conflicting operations. The authors study and formalize these mechanisms in three basic scenarios: when there is a single conflicting type of action; when there are two conflicting types, but operations of the same type do not conflict; and when there are two conflicting types, but operations of one type do not conflict among themselves. For each scenario, applications that require mutual exclusion are presented (e. g. , name servers, termination protocols, concurrency control). In each case, also presented are mutual exclusion mechanisms that are more general and that may provide higher reliability than the voting mechanisms that have been proposed as solutions to this problem.