On the message complexity of distributed problems

DOI10.1007/BF00979869MaRDI QIDQ3345763zbMATH OpenFDO

Authors N. Santoro

Publication date 1984

Published in International Journal of Computer & Information Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF00979869

zbMATH Keywords

distributed computingdistributed algorithmsasynchronous message-passing systemsextrema-findinglocal topological informationminimum- weight spanning-tree construction

Mathematics Subject Classification ID

Theory of operating systems (68N25)

Recommendations

• Improving the Time Complexity of Message-Optimal Distributed Algorithms for Minimum-Weight Spanning Trees
• Distributed communication complexity of spanning tree construction
• Optimal lower bounds for some distributed algorithms for a complete network of processors
• A trade-off between information and communication in broadcast protocols

Cites work

• scientific article; zbMATH DE number 3850459 (Why is no real title available?)
• scientific article; zbMATH DE number 3706363 (Why is no real title available?)
• scientific article; zbMATH DE number 3763288 (Why is no real title available?)
• scientific article; zbMATH DE number 3800917 (Why is no real title available?)
• A Distributed Algorithm for Minimum-Weight Spanning Trees
• A Distributed Graph Algorithm: Knot Detection
• Algorithms for Scheduling Tasks on Unrelated Processors
• An O ( n log n ) Unidirectional Algorithm for the Circular Extrema Problem
• An O(n log n) unidirectional distributed algorithm for extrema finding in a circle
• An improved algorithm for decentralized extrema-finding in circular configurations of processes
• Decentralized extrema-finding in circular configurations of processors
• Distributed algorithms for finding centers and medians in networks
• Graph Traversal Techniques and the Maximum Flow Problem in Distributed Computation
• Lower Bounds for Distributed Maximum-Finding Algorithms
• Lower Bounds on Information Transfer in Distributed Computations
• On describing the behavior and implementation of distributed systems

Cited in

(22)

• Distributed Algorithms for Message-Passing Systems
• Ability to Count Messages Is Worth Θ(Δ) Rounds in Distributed Computing
• scientific article; zbMATH DE number 1202979 (Why is no real title available?)
• Distributed Maximal Independent Set using Small Messages
• Deterministic leader election takes \(\Theta (D + \log n)\) bit rounds
• On the impact of sense of direction on message complexity
• Lower bounds on communication complexity in distributed computer networks
• Some problems in distributed computational geometry
• Deducible and equivalent structural knowledges in distributed algorithms
• The lower bounds on distributed shortest paths
• Towards optimal distributed election on chordal rings
• Minimizing message complexity of partially replicated data on hypercubes
• A note on the message complexity of Cidon's distributed depth-first search algorithm
• scientific article; zbMATH DE number 4068275 (Why is no real title available?)
• On the average communication complexity of asynchronous distributed algorithms
• Combinatorial Message Sharing and a New Achievable Region for Multiple Descriptions
• Distributed communication complexity of spanning tree construction
• scientific article; zbMATH DE number 1769898 (Why is no real title available?)
• Amortized Communication Complexity of Distributions
• Sense of direction in distributed computing
• Optimal lower bounds for some distributed algorithms for a complete network of processors
• A Deterministic Worst-Case Message Complexity Optimal Solution for Resource Discovery

This page was built for publication: On the message complexity of distributed problems

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