Tree-based Algorithm to Find the k-th Value in Distributed Systems
Yoonsik Cheon, Johnny S.K. Wong · Iowa State University Digital Repository (Iowa State University) · 1994
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(logN ) rounds of message passing, where N is the number of nodes in the network. Keywords: searching k-th value, extrema finding, distributed algorithms, message passing, tree. 1 Introduction Given N processors or computer systems that communicate only with message passing, the distributed extrema-finding problem is to select the processor with the maximum (or minimum) value. Each processor is assumed to has a unique value in a set with a total order. The extrema-finding problem has been studied for quite some time now and several algorithms have appeared in the literature. We extend this problem to find the pro...