Donald Bren School of Information and Computer Sciences

Centralized coordination protocols are simpler and more efficient than distributed ones. However, as a distributed system gets large, the bottleneck of the central coordinator renders protocols relying on centralized coordination inefficient. To solve this problem, hierarchical coordination can be used, where performance degrades logarithmically with the number of participating processes.

In this paper we present a mechanism that automatically organizes processes in a hierarchy and maintains the hierarchy in the presence of node failures, and incremental addition and removal of processes in the system. The new topology resulting from a change is computed by each process locally, without having to broadcast the entire topology to all processes. The proposed scheme can concurrently support multiple logical structures, such as a ring, a hypercube, a mesh, or a tree. It supports total order of broadcasts and does not rely on any specific system features or special hardware.