Mutual exclusion in distributed systems (databases, voting, partitions)
Daniel Barbará · 1985
This thesis studies the use of voting mechanisms as a tool to achieve mutual exclusion in Distributed Systems. As an example, consider a system that manages replicated data. In the event of a network partition, the system is divided into isolated groups of nodes. If we do not want these copies to diverge, we should prevent more than one group from performing updates. The decision as to which group can update must be reached without communication among the groups. One well known solution is to assign a-priori a number of votes, and let the group whose members have a majority perform the updating. However, it is possible that at a given time no group has the majority. In this work, we also look at a second strategy, which consists of a-priori defining a set of groups that intersects each other. Any group of nodes that finds itself in this set can perform the restricted operation. Although the two strategies appear to be similar, we show that they are not equivalent in general. The set strategy proves also useful in enumerating the assignment choices and for proving some interesting properties. These properties can be applied to optimize the assignment selection for a given system. We look at the optimization problem under a set of different metrics. We also look at other mutual exclusion scenarios like the termination of a transaction under faulty environments. We prove some interesting properties related to those scenarios.