Skip to main content
Unpublished Paper
Tree-based Algorithm to Find the k-th Value in Distributed Systems
Computer Science Technical Reports
  • Yoonsik Cheon, Iowa State University
  • Johnny S. Wong, Iowa State University
Publication Date
4-24-1994
Technical Report Number
TR94-07
Disciplines
Abstract
In this paper, we study distributed algorithms for finding the k-th value in the decentralized systems. First we consider the case of circular configuration of processors where no processor knows the total number of participants. Later a network of arbitrary configuration is examined and a tree-based algorithm is proposed. The proposed algorithm requires O(N) messages and O(log N) rounds of message passing, where N is the number of nodes in the network.
Citation Information
Yoonsik Cheon and Johnny S. Wong. "Tree-based Algorithm to Find the k-th Value in Distributed Systems" (1994)
Available at: http://works.bepress.com/johnny-wong/15/