Donald Bren School of Information and Computer Sciences

Coordination protocols are an essential part of every distributed system. In general, centralized 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. This solves the scalability problem of the algorithms relying on centralized coordinations, since the performance of hierarchical coordination 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 addition and removal of processes in the system. The proposed scheme is simple and general, and can concurrently support multiple logical structures, such as a ring, a hypercube, or a mesh.