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

rankingdistributed algorithmssortingmessage complexitynetwork of processors

Mathematics Subject Classification ID

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

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

(15)

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

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)