A fault-tolerant algorithm for replicated data management
Authors:
- S. RangarajanSRS. Rangarajan
- S. SetiaSSS. Setia
- S.K. TripathiSTS.K. Tripathi
- 1 January 1995
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Parallel and Distributed Systems
- Vol. 6 (12) , 1271-1282
Abstract
In this paper, we examine the tradeoff between message overhead and data availability that arises in the design of fault-tolerant algorithms for replicated data management in distributed systems. We propose a property called asymptotically high resiliency which is useful for evaluating the fault-tolerance of replica control algorithms and distributed mutual exclusion algorithms. We present a new algorithm for replica control that can be tailored (through a design parameter) to achieve the desired balance between low message overhead and high data availability. Further, we show that for a message overhead of ${\bf O}(\sqrt{N{\rm log}N})$, our algorithm can achieve asymptotically high resiliency.
Keywords
This publication has 19 references indexed in Scilit:
- Multidimensional votingACM Transactions on Computer Systems, 1991
- Exploiting logical structures in replicated databasesInformation Processing Letters, 1990
- Performance characterization of quorum-consensus algorithms for replicated dataIEEE Transactions on Software Engineering, 1989
- Dynamic voting1987
- A quorum-consensus replication method for abstract data typesACM Transactions on Computer Systems, 1986
- How to assign votes in a distributed systemJournal of the ACM, 1985
- An efficient, fault-tolerant protocol for replicated data management1985
- Optimism and consistency in partitioned distributed database systemsACM Transactions on Database Systems, 1984
- Weighted voting for replicated data1979
- A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of ObservationsThe Annals of Mathematical Statistics, 1952