Distributed selectsort sorting algorithms on broadcast communication networks |
| |
Authors: | Jau-Hsiung Huang Leonard Kleinrock |
| |
Affiliation: | a Department of Computer Science and Information Engineering, National Taiwan University, Taipei, Taiwan R.O.C. b Computer Science Department, University of California, Los Angeles, California, USA |
| |
Abstract: | In this paper, a distributed selectsort algorithm and a parameterized selectsort algorithm are presented to be applied on distributed systems for cases when N P where N is the number of elements to be sorted and P is the number of processors in the system. The distributed system considered in this paper uses a broadcasting channel for communication between processors. We show that the number of messages required for the parameterized selectsort algorithm is independent of N and is of complexity O(P), which is optimal in a distributed system with P processors. Furthermore, the amount of communication required in terms of elements is N + O(P3) and the computation time complexity is O((N/P)lgN + P2lg(N/P)). Hence, when N P3, the computation time complexity is O((N/P)lgN), which is optimal using P processors. In addition, this parameterized algorithm provides us with a parameter K such that by choosing the value of K allows us to trade among processing requirement, memory requirement, and communication requirement. It is shown that this parameterized algorithm can reduce the communication requirements significantly while only slightly increasing the computation requirements. |
| |
Keywords: | Broadcast Communication bit complexity Communication element complexity Communication message complexity Computation time complexity Delimiter |
本文献已被 ScienceDirect 等数据库收录! |
|