A fault-tolerant algorithm for replicated data management

Authors:
  • SRS. Rangarajan
    S. Rangarajan
  • SSS. Setia
    S. Setia
  • STS.K. Tripathi
    S.K. Tripathi

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.

This publication has 19 references indexed in Scilit: