Distributed algorithms for selection in sets
type: Item
instance of: scholarly article
title: Distributed algorithms for selection in sets
zbMATH Open document ID: 0659.68066
DOI: 10.1016/0022-0000(88)90012-8
author: Greg N. Frederickson
published in: Journal of Computer and System Sciences
publication date: 1988-01-01T00:00:00Z
full work available at URL: https://docs.lib.purdue.edu/cgi/viewcontent.cgi
review text: 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.
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68P10
zbMATH DE Number: 4078805
zbMATH Keywords: distributed algorithms
zbMATH Keywords: message complexity
zbMATH Keywords: Network topologies
zbMATH Keywords: ring
zbMATH Keywords: mesh
zbMATH Keywords: complete binary tree
zbMATH Keywords: linear-time selection algorithm
MaRDI profile type: Publication
OpenAlex ID: W2061032584
cites work: Time bounds for selection
cites work: A parallel median algorithm
cites work: An O(n log n) unidirectional distributed algorithm for extrema finding in a circle
cites work: The complexity of selection and ranking in X+Y and matrices with sorted columns
cites work: Q4057549
cites work: Selection and sorting with limited storage
cites work: Q3945584
cites work: Finding the median
description: scientific article; zbMATH DE number 4078805