Tree-based Algorithm to Find the k-th Value in Distributed Systems
Date
1994-04-24
Authors
Major Professor
Advisor
Committee Member
Journal Title
Journal ISSN
Volume Title
Publisher
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.
Series Number
Journal Issue
Is Version Of
Versions
Series
Academic or Administrative Unit
Type
article