Concepedia

The Tree Quorum Protocol: An Efficient Approach for Managing Replicated Data

Very Large Data Bases · 1990 · 134 citations · 18 references

TL;DR

Fault‑tolerant distributed systems should avoid unnecessary costs during normal operation. The paper proposes an efficient algorithm for managing replicated data. The algorithm imposes a logical tree structure on object copies, enabling read operations to access a single copy while ensuring fault‑tolerant writes. The protocol achieves fault‑tolerant writes with single‑copy reads in failure‑free settings and gracefully degrades communication costs as failures arise.

Abstract

In this paper, we present an efficient algorithm for managing replicated data. We impose a logical tree structure on the set of copies of an object. In a failurefree environment the protocol executes read operations by reading one copy of an object while guaranteeing fault-tolerance of write operations. It also exhibits the property of graceful degradation, i.e., communication costs are minimal in a failure-free environment but may increase as failures occur. This approach in designing distributed systems is desirable since it provides faulttolerance without imposing unnecessary costs on the failure-free mode of operations.