archives

Tree-based Algorithm to Find the k-th Value in Distributed Systems

Home 

About 

Browse 

Search 

Register 

Subscriptions 

Deposit Papers 

Help
    

Cheon, Yoonsik and Wong, Johnny (1994) Tree-based Algorithm to Find the k-th Value in Distributed Systems. Technical Report TR94-07, Department of Computer Science, Iowa State University.

Full text available as:Postscript
Adobe PDF

Abstract

A Tree-based Algorithm to Find the k-th Value in Distributed
Systems
by
Yoonsik Cheon and Johnny Wong
Department of Computer Science, 226 Atanasoff Hall
Iowa State University, Ames, Iowa 50011-1040 USA
cheon@cs.iastate.edu and wong@cs.iastate.edu
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.




Subjects:All uncategorized technical reports



ID code:00000073


Deposited by:Staff Account on 25 April 1994









Contact site administrator at: ssg@cs.iastate.edu