An improved algorithm for finding the median distributively |
| |
| Authors: | Francis Chin and H F Ting |
| |
| Affiliation: | (1) Computer Studies, University of Hong Kong, Pokfulam Road, Hong Kong |
| |
| Abstract: | Given two processes, each having a total-ordered set ofn elements, we present a distributed algorithm for finding median of these 2n elements using no more than logn +O( logn) messages, but if the elements are distinct, only logn +O(1) messages will be required. The communication complexity of our algorithm is better than the previously known result which takes 2 logn messages. |
| |
| Keywords: | Distributed algorithms Message complexity Median selection |
| 本文献已被 SpringerLink 等数据库收录！ |
