Tradeoffs for selection in distributed networks (Preliminary Version)

ABSTRACT

Algorithms are presented for selecting an element of given rank from a set of elements distributed among the nodes of a network. Network topologies considered are a ring, a mesh, and a complete binary tree. For the ring and the mesh, upper bound tradeoffs are identified between the number of messages transmitted and the total delay due to message transmission. For the tree, an algorithm is presented that uses an asymptotically optimal number of messages.

REFERENCES

• 1: M. Blum, R. W. Floyd, V. R. Pratt, R. L. Rivest and R. E. Tarjan, Time bounds for selection, J. Comput. Sys. Sci. 7, 4 (1972) 448-461.
• 2: D. Dolev, M. Klawe and M. Rodeh, An O(n log n) unidirectional distributed algorithm for extreme finding in a circle, J. Algorithms 3, 3 (Sept. 1982) 245-260.
• 3: G. N. Frederickson, Upper bounds for time-space tradeoffs in sorting and selection, Purdue University CSD TR 429 (January 1983).
• 4: J. I. Munro and M. S. Paterson, Selection and sorting with limited storage, Theor. Comput. Sci. 12 (1980) 315-323.
• 5: M. Rodeh, Finding the median distributively, J. Comput. Sys. Sci. 24 (1982) 162-166.
• 6: N. Santoro and J. B. Sidney, Order statistics on distributed sets, Proc. 20th Allerton Conf. on Communication, Control and Computing, University of Illinois (October 1982) 251-256.
• 7: A. Schönhage, M. Paterson and N. Pippenger, Finding the median, J. Comput. Sys. Sci. 13 (1976) 184-199.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network topology

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

General Terms:
Algorithms