The triangular lattice protocol: a highly fault tolerant and highly efficient protocol for replicated data

Author

Wu, Chienwen ; Belford, Geneva G.

Author_Institution

Dept. of Comput. Sci., Illinois Univ., Urbana, IL, USA

fYear

1992

fDate

5-7 Oct 1992

Firstpage

66

Lastpage

73

Abstract

A protocol for managing replicated data in which data copies are organized as a triangular lattice is introduced. The smallest quorum size is O(√N), where N is the number of data copies, which is currently considered optimal for a fully distributed environment. The protocol has the property of graceful degradation. The quorum sizes increase gradually as data copy failures increase. The protocol also has the property of asymptotically high availability, i.e., the availability approaches 1 as the number of data copies goes to ∞ if the probability that a data copy available is greater than 0.5

Keywords

distributed databases; fault tolerant computing; protocols; asymptotically high availability; data copies; data copy failures; fully distributed environment; graceful degradation; highly fault tolerant; quorum size; quorum sizes; replicated data; triangular lattice protocol; Access protocols; Availability; Computer science; Costs; Database systems; Degradation; Distributed algorithms; Fault tolerance; Lattices; Voting;

fLanguage

English

Publisher

ieee

Conference_Titel

Reliable Distributed Systems, 1992. Proceedings., 11th Symposium on

Conference_Location

Houston, TX

Print_ISBN

0-8186-2890-1

Type

conf

DOI

10.1109/RELDIS.1992.235141

Filename

235141