Affordable Access

Publisher Website

An algorithm with decentralized control for sorting files in a network

Authors
Journal
Journal of Parallel and Distributed Computing
0743-7315
Publisher
Elsevier
Publication Date
Volume
7
Issue
3
Identifiers
DOI: 10.1016/0743-7315(89)90031-2
Disciplines
  • Computer Science

Abstract

Abstract An iterative algorithm with decentralized control for sorting a file distributed over a network is presented. In each iteration, one station assembles a sorted subfile. Each station starts by requesting from the others a certain number of keys which are below an adaptive upper bound. The requests are repeated until the station has collected enough appropriate keys for its subfile. Control is then shifted to another station for the next iteration. Simple methods are provided for determining these numbers and bounds. For a file with N records distributed over d stations, the algorithm has worst-case total message and traffic complexities O( d 3) and O( d 2 N), respectively. In the average case, its total traffic complexity is O( N+ d 2 · log( N)). The main advantage of our decentralized algorithm is that traffic burden is dispersed among all stations instead of concentrating on one of them, as in Wegner's and Rotem's centralized algorithms.

There are no comments yet on this publication. Be the first to share your thoughts.