Symmetry in spite of hierarchy
Vijay K. Garg, Joydeep Ghosh · 2002
The authors present a revolving hierarchical scheme in which the logical position of a process in the hierarchy changes with time so that the reorganization of hierarchy is achieved concurrently with its use. The technique is useful for repeated computation of global functions that require information from all processes. It results in algorithms that are not only fair to all nodes, but also less expensive in terms of messages. The reduction in the number of messages is achieved by reusing messages for more than one computation of the global function. The technique is illustrated for hierarchical snapshot computation and distributed branch-and-bound problems.>