Accession Number:

ADA142415

Title:

The Complexity of Sorting on Distributed Systems.

Descriptive Note:

Technical rept.,

Corporate Author:

ILLINOIS UNIV AT URBANA APPLIED COMPUTATION THEORY GROUP

Personal Author(s):

Report Date:

1983-09-01

Pagination or Media Count:

28.0

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 lgLNlg N messages on a bidirectional ring with N processors. Every sorting algorithm requires omega N 32 lgLNlg N messages on a square mesh with N processors. A novel sorting algorithm for unidirectional rings achieves the first lower bound. Author

Subject Categories:

  • Computer Hardware
  • Computer Systems
  • Non-Radio Communications

Distribution Statement:

APPROVED FOR PUBLIC RELEASE