Skip to main content
Open Access Publications from the University of California

Process interconnection structures in dynamically changing topologies


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.

Main Content
For improved accessibility of PDF content, download the file to your device.
Current View