Providing Low Cost Read Access to Replicated Data with Multi-Level Voting
Bernd Freisleben, Hans-Henning Koch, Oliver Theel · 1992
In this paper we present and analyze multi--level voting algorithms for maintaining the mutual consistency of highly replicated data in a large distributed system. The underlying principle of the multi--level approach is to impose a logical hierarchical structure on the nodes of the network and apply well known voting algorithms for replicated data concurrency control in a layered fashion. Since research on multi--level voting algorithms has been confined to particular instances which were investigated empirically, the focus of our work is to provide a general model which allows us to assess the properties of multi--level voting strategies. We show how to calculate the message costs and the degree of availability associated with a subclass of strategies and present solutions to efficiently handle dynamic changes in the number of replicas. The analytical results obtained are illustrated by comparative performance measurements in a simulated network. Keyword Codes: C.2.4; D.4.5 Keywords:...