Tradeoffs for selection in distributed networks (Preliminary Version)

1 January 1983

proceedings article
Published by Association for Computing Machinery (ACM)

p. 154-160
https://doi.org/10.1145/800221.806718

Abstract

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, upper bound tradeoffs are identified between the number of messages transmitted and the total delay due to message transmission. For the tree, an algorithm is presented that uses an asymptotically optimal number of messages.

Keywords

MESSAGE TRANSMISSION
UPPER BOUND TRADEOFFS
TOTAL DELAY
COMPLETE BINARY TREE
ASYMPTOTICALLY OPTIMAL NUMBER
PRELIMINARY VERSION
NETWORK TOPOLOGY
AVAILABILITY
BINARY TREE
UPPER BOUND

This publication has 0 references indexed in Scilit: