The Complexity of Sorting on Distributed Systems.

Abstract

The sorting problem is no arrange N values in a distributed system of N processors into sorted order. Let the values be in (0,...,L). Every sorting algorithm requires omega (N 2 lg(L/N)/lg N) messages on a bidirectional ring with N processors. Every sorting algorithm requires omega (N 3/2 lg(L/N)/lg N) messages on a square mesh with N processors. A novel sorting algorithm for unidirectional rings achieves the first lower bound. (Author)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Sep 01, 1983
Accession Number
ADA142415

Entities

People

  • M. C. Loui

Organizations

  • University of Illinois Urbana–Champaign

Tags

Communities of Interest

  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Air Force
  • Algorithms
  • Artificial Intelligence
  • Automata
  • Automata Theory
  • Classification
  • Coding
  • Computational Complexity
  • Computational Science
  • Computations
  • Computer Programming
  • Computers
  • Distributed Computing
  • Illinois
  • New York
  • Security
  • Unidirectional

Fields of Study

  • Computer science

Readers

  • Approximation Theory.
  • Computer Science/Computer Engineering/Data Science/Digital Signal Processing.
  • Phased Array Antenna Design.