Randomized speed-ups in parallel computation

ABSTRACT

The following problem is considered: given a linked list of length n, compute the distance of each element of the linked list from the end of the list. The problem has two standard deterministic algorithms: a linear time serial algorithm, and an O((nlog n)/p + log n) time parallel algorithm using p processors. A known conjecture states that it is impossible to design an O(log n) time deterministic parallel algorithm that uses only n/log n processors. We present three randomized parallel algorithms for the problem. One of these algorithms runs almost-surely in time of O(n/p + log nlog*n) using p processors on an exclusive-read exclusive-write parallel RAM.

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 2: M. Ajtai , J. Komlós , E. Szemerédi, Sorting in c log n parallel steps, Combinatorica, v.3 n.1, p.1-19, Jan. 1983 [doi>10.1007/BF02579338]
• 3: D. Angluin and L.G. Valiant, "Fast probabilistic algorithms for Hamiltonian circuits and matching", JCSS 18 (1979), 155-193.
• 4: I. Bar-On and U. Vishkin, "Optimal parallel generation of a computation tree form", TR 90, Dept. of Computer Science, Courant Institute, NYU, 1983.
• 5: F.Y . Chin, J. Lam and I. Chen, "Optimal parallel algorithms for the connected component problems," Proc. 1981 International Conf. on Parallel Processing (1981), 170-175.
• 6: A.K. Chandra, L.J. Stockmeyer and U. Vishkin, "A complexity theory for unbounded fan-in parallelism", Proc. 23rd Annual IEEE Symposium on Foundations of Computer Science, 1982, 1-13.
• 7: W. Feller, An Introduction to Probability Theory and its Applications, V. 1, Wiley, New York, 1950.
• 8: N.J. Johnson and S. Kotz, Discrete Distributions, Houghton Mifflin Company, Boston, MA, 1969.
• 9: N. Megiddo, "Parallel algorithms for finding the maximum and the median almost surely in constant-time", preprint, 1982.
• 10: K. Mehlhorn and U. Vishkin, "Granularity of parallel memories", TR 89, Dept of Computer Science, Courant Institute, NYU, 1983. For an abstract see Proc. of the 9th Workshop on Graphtheoretic Concepts in Computer Science (WG-83), Fachbereich Mathematik, Universitat Osnabruck, June 1983.
• 11: Wolfgang J. Paul , Uzi Vishkin , Hubert Wagener, Parallel Dictionaries in 2-3 Trees, Proceedings of the 10th Colloquium on Automata, Languages and Programming, p.597-609, July 18-22, 1983
• 12: M.O. Rabin, "Probabilistic algorithms", Algorithms and Complexity, J.F. Traub, Editor, Academic Press (1976), 21-39.
• 13: M.O. Rabin , "Randomized Byzantine Generals", Proc. 24th Annual IEEE Symposium on Foundations of Computer Science (1983), 403-409.
• 14: R. Reischuk, "A fast probabilistic parallel sorting algorithm", Proc. 22nd Annual IEEE Symposium on Foundations of Computer Science (1981), 212-219.
• 15: John H. Reif , Leslie G. Valiant, A logarithmic time sort for linear size networks, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.10-16, December 1983 [doi>10.1145/800061.808727]
• 16: Y. Shiloach and U. Vishkin, "Finding the maximum merging, and sorting in a parallel computation model," J. Algorithms 2 (1981), 88-102.
• 17: Y. Shiloach and U. Vishkin, "An O(log n) parallel connectivity algorithm", J. Algorithms 3 (1982), 57-67.
• 18: Y.H. Tsin and F.Y. Chin, "Efficient parallel algorithms for a class of graph theoretic problems," Dept. of Computing Science, University of Alberta, Edmonton, Alberta, Canada, 1982.
• 19: R.E. Tarjan and U. Vishkin, "An efficient parallel biconnectivity algorithm", TR 69, Dept. of Computer Science, Courant Institute, NYU, 1983.
• 20: L.G. Valiant, "Parallelism in comparison problems", SIAM J. Comp. 4(1975), 348-355.
• 21: U. Vishkin, "An optimal parallel connectivity algorithm," Technical Report RC 9149, IBM Thomas J. Watson Research Center, Yorktown Heights, New York 1981. To appear in Discrete Applied Mathematics.
• 22: U. Vishkin, "Synchronous parallel computation - a survey", TR 71, Dept of Computer Science, Courant Institute, NYU, 1983.
• 23: U. Vishkin, "An optimal parallel algorithm for selection", TR 106, Dept of Computer Science, Courant Institute, NYU, 1983.
• 24: U. Vishkin, "Efficient parallel strong orientation", in preparation.
• 25: James C. Wyllie, The Complexity of Parallel Computations, Cornell University, Ithaca, NY, 1979

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Bounded-action devices (e.g., Turing machines, random access machines)

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Parallel algorithms
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

General Terms:
Algorithms, Theory