Group communication permits a single sender to communicate with multiple receivers. A nested group permits one or more of the receivers to be itself a group. Nested groups are particularly useful for reducing communication traffic on internetwork links and supporting subnetwork autonomy. A name graph model is used to characterize nested groups and formalize the problems of loops and duplications. The authors design and analyze a spanning shadow tree algorithm that detects potential loops and duplication. The algorithm is considered static because loops and duplicates are detected at the time of group membership modification rather than at the time a message is sent. The algorithm changes the system-level representation of the name graph in a transparent manner to avoid infinite loops and to suppress duplicated messages. The worst-case message complexity of name graph update operations is on the order of O( mod N mod /sup 2/), where mod N mod is the number of groups in the system. The complexity of updates can be justified, since run-time overhead for actual message communication is reduced.>

This paper generalizes group communications into nested groups for the internet environment. By using a name graph model, two problems in nested group name resolution are identified — resolution loops and resolution duplications. Existing approaches of solving these problems are surveyed and their shortcomings analyzed. The research contribution of this paper is the design and analysis of an algorithm which uses statically saved topology information of the name graph to detect and handle resolution and duplication loops at the time when group membership and/or group structure change. While preserving some necessary properties of loops, the algorithm transforms the name graph into one which avoids resolution loops and controls duplications. The communication complexity of the algorithm has an upper bound of Ο(|A|) in the worst case, where |A| is the number of arcs in the name graph.