New Heuristics for the Multidimensional Vote Assignment Problem

摘要

Vote assignments are being used for the design of fauit tolerant systems. They work in such a way that every node in a computer netword gets assigned a certain number of votes. Furthermore,a quorum is defined. Atransaction can only take place if the number ofvotes collected is greater than or equal to the quorum. These single dimensional vote assignments provide a compact representation of certain antichains, namely those which consist of the minimal sets of nodes achieving the quorum. Multidimensional (MD) vote assignments are a generalization of single dimensional vote assignments. In contrast to single dimensional vote assignments, MD vote assignments have the important property that every antichain has a corresponding MD vote assignment and vice versa. For the efficient design of fauit tolerant systems, it is important that the dimension of a MD vote assignment is as small as possible. We introduce some new heuristics for calculating a MD vote assignment which perform better than the heuristics known so far.