Finding an extremum in a network

ABSTRACT

We propose a method for implementing “the election process” - finding an extrema of values computed in a multiprocessor network. It operates in an average time less than Log2(N), for a network of size N. It requires a single register, memory cell, or global buss into which all the processors can attempt to write, with the success of one guaranteed; and from which they may all read, in parallel. A second method is given which guarantees termination in O(Log2(MAX)) steps.

REFERENCES

• 1: El-Dessouki, O.I. and Huen, W.H., "Distributed Enumeration on Network Computers", Proc. of 1979 International Conference on Parallel Processing, IEEE Computer Society, Long Beach, California, 1979, p.137-146.
• 2: Chang, E.J., "Decentralized Algorithms in Distributed Systems", TR CSRG-103, Department of Computer Science, University of Toronto, October 1979.
• 3: Dalal, Y. K., "Broadcast Protocals in Packet Switched Computer Networks", TR-128, Stanford Digitial Systems Laboratory, Stanford, California, April, 1977.
• 4: D. S. Hirschberg , J. B. Sinclair, Decentralized extrema-finding in circular configurations of processors, Communications of the ACM, v.23 n.11, p.627-628, Nov. 1980 [doi>10.1145/359024.359029]
• 5: Ernest Chang , Rosemary Roberts, An improved algorithm for decentralized extrema-finding in circular configurations of processes, Communications of the ACM, v.22 n.5, p.281-283, May 1979 [doi>10.1145/359104.359108]
• 6: Kung, H.T.; "The Structure of Parallel Algorithms" CMU-CS-143, Department of Computer Science, Carnegie-Mellon University, Pittsburgh, Pennsylvania, August, 1979.
• 7: Dubitzki, T., Wu, A. and Rosenfeld, A. "Local Reconfiguration of Networks of Processors: Arrays, Trees and Graphs", TR-790 (AFOSR-77-3271), Computer Vision Laboratory, Computer Science Center, University of Maryland, College Park, MD 20742.
• 8: Caxton C. Foster, Content Addressable Parallel Processors, John Wiley & Sons, Inc., New York, NY, 1976
• 9: Hall, J. Storrs, "A General-Purpose Cam-Based System", VLSI Systems and Computations, H. T. Kung, Bob Sproul, and Guy Steel, editors, Computer Science Press, Rockville, Maryland, 1981.
• 10: Chang, S.S.L., "Multiple-Read Single Write Memory and Its Applications", IEEE Transactions on Computers, Vol. C-29, No.8, August, 1980.
• 11: Bokhari, Shahid H., "MAX: An Algorithm for Finding Maximum", Proc. of the 1981 International Conference on Parallel Processing, IEEE Computer Society, 1981, p.302-303.
• 12: Robert M. Metcalfe , David R. Boggs, Ethernet: distributed packet switching for local computer networks, Communications of the ACM, v.19 n.7, p.395-404, July 1976 [doi>10.1145/360248.360253]
• 13: Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
• 14: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.0 General

Additional Classification:
  B. Hardware
  B.8 Performance and Reliability
      B.8.2 Performance Analysis and Design Aids

General Terms:
Performance