Avoiding name resolution loops and duplications in group communications

ABSTRACT

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 &Ogr;(|A|) in the worst case, where |A| is the number of arcs in the name graph.

REFERENCES

• 1: Kenneth P. Birman , Thomas A. Joseph, Reliable communication in the presence of failures, ACM Transactions on Computer Systems (TOCS), v.5 n.1, p.47-76, Feb. 1987 [doi>10.1145/7351.7478]
• 2: S. Benford and J. Onions, "Pilot distribution lists -agents and directories", Proc. of IFIP WG6.5 International working conference on message handling systems, Technical University Munich, Institute for Informaties, FRG, April, 1987, pp 3.4.1- 3.4.24.
• 3: David R. Cheriton , Stephen E. Deering, Host groups: a multicast extension for datagram internetworks, Proceedings of the ninth symposium on Data communications, p.172-179, September 1985, Whistler Moutain, British Columbia, Canada
• 4: David R. Cheriton , Willy Zwaenepoel, Distributed process groups in the V Kernel, ACM Transactions on Computer Systems (TOCS), v.3 n.2, p.77-107, May 1985 [doi>10.1145/214438.214439]
• 5: Debra P. Deutsch, Implementing distribution lists in computer-based message systems, Proc. of the IFIP WG 6.5 working conference on Computer-based message services, p.3-13, November 1984, Nottingham, United Kingdom
• 6: A. J. Frank, L. D. Wittie and A. J. Bernstein, "Multicast communication on network computers", IEEE Software, Vol. 2, 3, May 1985, pp 49-61.
• 7: Luping Liang , Samuel T. Chanson , Gerald W. Neufeld, Process Groups and Group Communications: Classifications and Requirements, Computer, v.23 n.2, p.56-66, February 1990 [doi>10.1109/2.44904]
• 8: L. Liang, "Group communications in di#tributed systems", Ph.D Thesis# Distributed Systems Research Group, Department of Computer Science, the University of British Columbia, in preparation.
• 9: A. Gillian Waters , Christopher J. Adams , Ian M. Leslie , Roger M. Needham, The use of broadcast techniques on the universe network, Proceedings of the ACM SIGCOMM symposium on Communications architectures and protocols: tutorials & symposium, p.52-57, June 06-08, 1984, Montréal, Quebec, Canada, United States

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Path and circuit problems

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Distributed networks

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Routing and layout; Computations on discrete structures

General Terms:
Algorithms, Design