On the message complexity of distributed problems

DOI10.1007/BF00979869zbMath0552.68026MaRDI QIDQ3345763

Nicola Santoro

Publication date: 1984

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

zbMATH Keywords

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

Mathematics Subject Classification ID

Theory of operating systems (68N25)

Related Items (5)

On the impact of sense of direction on message complexity ⋮ Towards optimal distributed election on chordal rings ⋮ Deterministic leader election takes \(\Theta (D + \log n)\) bit rounds ⋮ Optimal lower bounds for some distributed algorithms for a complete network of processors ⋮ Sense of direction in distributed computing

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On describing the behavior and implementation of distributed systems
• 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
• Decentralized extrema-finding in circular configurations of processors
• Algorithms for Scheduling Tasks on Unrelated Processors
• An O ( n log n ) Unidirectional Algorithm for the Circular Extrema Problem
• A Distributed Graph Algorithm: Knot Detection
• An O(n log n) unidirectional distributed algorithm for extrema finding in a circle
• A Distributed Algorithm for Minimum-Weight Spanning Trees
• An improved algorithm for decentralized extrema-finding in circular configurations of processes

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