Bit complexity of order statistics on a distributed star network

DOI10.1016/0020-0190(89)90130-0MaRDI QIDQ1116337zbMATH OpenOpenAlexFDO

Authors Ornan Gerstel, Yishay Mansour, Shmuel Zaks

Publication date 1989

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(89)90130-0

zbMATH Keywords

asynchronous distributed star networkbit complexitylower boundorder statisticsrankingselectionsorting

Mathematics Subject Classification ID

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

Review text

We study the bit complexity of order statistics problem on an asynchronous distributed star network. We prove a lower bound of \(\Omega\) (N log(LN)) bits for the k-selection problem, and lower bounds of \(\Omega\) (N log(L-N)) bits for the problems of sorting and ranking. For each of the problems we introduce an algorithm that achieves that bound, thus showing all bounds to be optimal.

Recommendations

• The bit complexity of distributed sorting
• Order preserving communication on a star network
• Two absolute bounds for distributed bit complexity
• Structural Information and Communication Complexity
• scientific article; zbMATH DE number 962463
• Distributed computation of exact average degree and network size in finite time under quantized communication
• On randomized broadcasting in star graphs
• Graph-Theoretic Concepts in Computer Science
• Lower bounds on communication complexity in distributed computer networks
• An optimal bit complexity randomized distributed MIS algorithm

Cites work

• Distributed Sorting
• scientific article; zbMATH DE number 3800917 (Why is no real title available?)
• Optimal Distributed Algorithms for Sorting and Ranking
• The bit complexity of distributed sorting
• The complexity of sorting on distributed systems

Cited in

(4)

• The bit complexity of distributed sorting
• scientific article; zbMATH DE number 4068275 (Why is no real title available?)
• scientific article; zbMATH DE number 962463 (Why is no real title available?)
• Order preserving communication on a star network

This page was built for publication: Bit complexity of order statistics on a distributed star network

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