Optimal Distributed Algorithms for Sorting and Ranking

DOI10.1109/TC.1985.5009390MaRDI QIDQ3219776zbMATH OpenOpenAlexFDO

Authors Shmuel Zaks

Publication date 1985

Published in IEEE Transactions on Computers (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1109/tc.1985.5009390

zbMATH Keywords

distributed algorithmsmessage complexitynetwork of processorsrankingsorting

Mathematics Subject Classification ID

Theory of operating systems (68N25) Searching and sorting (68P10) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• The complexity of sorting on distributed systems
• The bit complexity of distributed sorting
• Distributed Sorting
• Distributed algorithms for selection in sets
• Beyond the worst-case bisection bound: Fast sorting and ranking on meshes

Cited in

(17)

• Bit complexity of order statistics on a distributed star network
• A distributed selection algorithm and its expected communication complexity
• The bit complexity of distributed sorting
• A time-optimal distributed sorting algorithm on a line network.
• Sorting algorithms for broadcast communications: mathematical analysis.
• Circular motion of multiple nonholonomic robots under switching topology with ordinal ranking
• Message lower bounds via efficient network synchronization
• SELF-STABILIZING DISTRIBUTED SORTING IN TREE NETWORKS
• The round complexity of distributed sorting, extended abstract
• Distributed Sorting
• Sorting a distributed file in a network
• The complexity of sorting on distributed systems
• Linearization: locally self-stabilizing sorting in graphs
• EFFICIENT ALGORITHMS FOR SELECTION AND SORTING OF LARGE DISTRIBUTED FILES ON DE BRUIJN AND HYPERCUBE STRUCTURES
• Sorting Long Sequences in a Single Hop Radio Network
• Efficient selection and sorting schemes using coteries for processing large distributed files
• Self-stabilizing mutual exclusion in dynamic networks with bounded temporal diameter

This page was built for publication: Optimal Distributed Algorithms for Sorting and Ranking

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