Efficient quorumcast routing algorithms

The authors study the quorumcasting problem which is a generalization of multicasting. While multicasting consists of sending a message to a select group of m nodes in a system of n nodes, quorumcasting sends a message to any q out of these m nodes. The need to communicate with an arbitrary q-subset of a predefined set arises in many distributed applications, such as distributed synchronization and updating a replicated resource. Two straightforward solutions are to send the message to individual members one at a time until q members have responded and to use multicasting to deliver the message to all members. The former solution will have excessive delay and the latter can cause congestion in nodes and/or in the network. The solutions proposed here use a minimum cost tree spanning a q-subset. By choosing an appropriate set of q nodes, the communications cost can be minimized. They present several heuristics to find low cost solutions for the quorumcast routing problem and evaluate the heuristics by comparing their solutions with exact solutions obtained from enumerating the solution space. The heuristic solutions are also compared with “random” solutions, where the q quorum sites are selected at random, and then the problem is treated like a multicast. The results of their tests show that the heuristics compare favorably with the optimal solutions, and that the random solutions perform rather poorly in comparison with the heuristics