Crossing - A Highly Available Quorum Protocol for Arbitrary Planar Topologies

摘要

Quorums are a powerful concept that can be used to implement highly available services. Quorum protocols use replicas of data to increase service availability. Unfortunately, applying quorum protocols in real-world networks often turns out to be difficult, since efficient quorum protocols depend on a particular topology imposed on the replicas managed by it. To effectuate these protocols, the topology of the real-world network must be identical to the particular topology required by the protocol. Clearly, this is a very strong constraint. In this paper, we present a novel quorum protocol that overcomes this difficulty and works directly on arbitrary planar network topologies. To use the new protocol even on non-planar graphs, we present a method to transform non-planar graphs into planar graphs.