Distributed algorithms for selection in sets

摘要

Algorithms are presented for selecting an element of given rank from a set of elements distributed among the nodes of a network. Network topologies considered are a ring, a mesh, and a complete binary tree. For the ring and the mesh, algortihms are presented whose performance exhibits a trade-off between the number of messages transmitted and the total delay due to message transmission. For the mesh and the tree, algorithms are presented that use an asymptotically optimal number of messages. The algorithms are based on a sampling approach that also gives rise to a new linear-time selection algorithm for a single processor.