MULTIDIMENSIONAL VOTING

We introduce a new concept, multidimensional voting, in which the vote and quorum assignments are k-dimensional vectors of nonnegative integers and each dimension is independent of the others. Multidimensional voting is more powerful than traditional weighted voting because it is equivalent to the general method for achieving synchronization in distributed systems which is based on sets of groups of nodes (quorum sets). We describe an efficient algorithm for finding a multidimensional vote assignment for any given quorum set and show examples of its use. We demonstrate the versatility of multidimensional voting by using it to implement mutual exclusion in fault-tolerant distributed systems and protocols for synchronizing access to fully and partially replicated data. These protocols cannot be implemented by traditional weighted voting. Also, the protocols based on multidimensional voting are easier to implement and/or provide greater flexibility than existing protocols for the same purpose. Finally, we present a generalization of the multidimensional voting scheme, called nested multidimensional voting, that can facilitate implementation of replica control protocols that use structured quorum sets.