How to Achieve High Throughput with Dynamic Tree-Structured Coterie

Abstract

Data replication permits a better network bandwidth utilization and
minimizes the effect of latency in large-scale systems such as
computing grids. However, the cost of maintaining the data
consistent between replicas may become difficult if the read/write
system has to ensure sequential consistency.
In this paper, we limit the overhead due to the data consistency
protocols by introducing a new dynamic quorum protocol called the
elementary permutation protocol.This protocol permits the
dynamic reconfiguration of a tree-structured coterie
\cite{Agrawal91Efficient} in function of the load of the machines
that possess the data replicas. It applies a tree transformation in
order to obtain a new less loaded coterie.This permutation is based
on the load information of a small group of machines possessing the
copies.
The implementation and the evaluation of our algorithm have been
based on the existing atomic read/write service of
\cite{Lynch97Robust}.
We demonstrate that the elementary permutation ameliorates the
system's throughput upto 50\% in the best case.
The results of our simulation show that the tree reconfiguration
based on the elementary permutation is more efficient for a
relatively small number of copies.