𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A time-optimal distributed sorting algorithm on a line network

✍ Scribed by Atsushi Sasaki

Publisher
Elsevier Science
Year
2002
Tongue
English
Weight
87 KB
Volume
83
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

✦ Synopsis

We have achieved a strict lower time bound of n -1 for distributed sorting on a line network, where n is the number of processes. The lower time bound has traditionally been considered to be n because it is proved based on the number of disjoint comparison-exchange operations in parallel sorting on a linear array. Our result has overthrown the traditional common belief.

πŸ“œ SIMILAR VOLUMES

A time–cost optimization of the national
A time–cost optimization of the national postal distribution network
✍ Josef JablonskΓ½; Josef Lauber πŸ“‚ Article πŸ“… 1999 πŸ› John Wiley and Sons 🌐 English βš– 84 KB πŸ‘ 1 views

The postal distribution network in the Czech Republic consists actually of 69 local transit centres (according to the administrative division of the Czech Republic). Each of them operates the post offices in the given region. Some of the important local transit centres can be selected as sorting cen

Performance modelling of three parallel
Performance modelling of three parallel sorting algorithms on a pipelined transputer network
✍ Narasimhan, V. Lakshmi; Armstrong, J. πŸ“‚ Article πŸ“… 1996 πŸ› John Wiley and Sons 🌐 English βš– 961 KB

The implementation of three parallel sorting algorithms, namely binary sort, odd-even transposition sort and bitonic sort, on a network of transputers is analysedin the paper. The variation in the performance of these algorithms as the number of processors and sort size are changed is investigated.

Parallel Sorting Algorithm Using Multiwa
Parallel Sorting Algorithm Using Multiway Merge and Its Implementation on a Multi-Mesh Network
✍ Bhabani P. Sinha; Amar Mukherjee πŸ“‚ Article πŸ“… 2000 πŸ› Elsevier Science 🌐 English βš– 288 KB

In this paper, we present a parallel sorting algorithm using the technique of multi-way merge. This algorithm, when implemented on a t dimensional mesh having n t nodes (t>2), sorts n t elements in O((t 2 &3t+2) n) time, thus offering a better order of time complexity than the [((t 2 &t) n log n)Γ‚2+