Distributed algorithms for selection in sets (Q1112607)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Distributed algorithms for selection in sets |
scientific article |
Statements
Distributed algorithms for selection in sets (English)
0 references
1988
0 references
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, algorithms 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.
0 references
distributed algorithms
0 references
message complexity
0 references
Network topologies
0 references
ring
0 references
mesh
0 references
complete binary tree
0 references
linear-time selection algorithm
0 references