An Efficient Replication Protocol Exploiting Logical Tree Structures

In this paper we present an efficient approach for managing replicated data and services. The approach is based on the fact that the replicas are organized in a logical tree structure. An algorithm exploiting this structure is developed, leading to a strategy in which at best only a single replica for performing read operations and only O[log n] replicas for executing write operations have to be accessed. We analyze cost and availability of the operations and compare the new strategy with other replication strategies in order to show the cases in which the new strategy is superior. Finally, we use the new strategy to extend it to a hybrid approach which provides low cost operations and at the same time high operation availabilities. 1 Introduction In large distributed systems node and communication failures are likely to occur and thus prevent operations from being successfully executed by making remote data or services which are needed by the caller unavailable. This raises the nee..