An efficient replication protocol exploiting logical tree structures

An efficient approach for managing replicated data and services is presented. 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. The author analyzes cost and availability of the operations and compares the new strategy with other replication strategies in order to show the cases in which the new strategy is superior. Finally, the author presents a hybrid approach which is obtained by combining the new strategy and other replication protocols. The obtained hybrid strategies provide low cost operations and at the same time high operation availabilities.