Distributed algorithms for selection in sets

DOI10.1016/0022-0000(88)90012-8MaRDI QIDQ1112607zbMATH OpenOpenAlexFDO

Authors Greg N. Frederickson

Publication date 1988

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://docs.lib.purdue.edu/cgi/viewcontent.cgi?article=1390&context=cstech

zbMATH Keywords

complete binary treedistributed algorithmslinear-time selection algorithmmeshmessage complexityNetwork topologiesring

Mathematics Subject Classification ID

Searching and sorting (68P10) Analysis of algorithms and problem complexity (68Q25)

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.

Recommendations

• Unifying themes for selection on any network
• scientific article; zbMATH DE number 4050993
• Selection on k-Dimensional Meshes with Multiple Broadcasting
• A distributed selection algorithm and its expected communication complexity
• Fast deterministic selection on mesh-connected processor arrays

Cites work

• A parallel median algorithm
• An O(n log n) unidirectional distributed algorithm for extrema finding in a circle
• Finding the median
• scientific article; zbMATH DE number 3763288 (Why is no real title available?)
• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• Selection and sorting with limited storage
• The complexity of selection and ranking in X+Y and matrices with sorted columns
• Time bounds for selection

Cited in

(11)

• An improved algorithm for finding the median distributively
• A distributed selection algorithm and its expected communication complexity
• Unifying themes for selection on any network
• Message lower bounds via efficient network synchronization
• Optimal Distributed Algorithms for Sorting and Ranking
• New algorithms for selection
• scientific article; zbMATH DE number 3911705 (Why is no real title available?)
• Shout echo selection in distributed files
• scientific article; zbMATH DE number 4050993 (Why is no real title available?)
• scientific article; zbMATH DE number 4068275 (Why is no real title available?)
• Efficient selection and sorting schemes using coteries for processing large distributed files

This page was built for publication: Distributed algorithms for selection in sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1112607)