Sense of direction, topological awareness and communication complexity
- 1 July 1984
- journal article
- Published by Association for Computing Machinery (ACM) in ACM SIGACT News
- Vol. 16 (2) , 50-56
- https://doi.org/10.1145/1008959.1008961
Abstract
Based on some recent results, it is here argued that the communication complexity of distributed problems can be greatly affected by two factors hereby identified as 'sense of direction' and 'topological awareness'. It is also suggested that 'insensitivity' to either or both factors is an indicator of the inherent difficulty of a distributed problem. A bibliography of recent results is included.Keywords
This publication has 13 references indexed in Scilit:
- Distributed algorithms for finding centers and medians in networksACM Transactions on Programming Languages and Systems, 1984
- Tradeoffs for selection in distributed networks (Preliminary Version)Published by Association for Computing Machinery (ACM) ,1983
- A Distributed Algorithm for Minimum-Weight Spanning TreesACM Transactions on Programming Languages and Systems, 1983
- Distributed computation on graphsCommunications of the ACM, 1982
- A Distributed Algorithm for Shortest PathsIEEE Transactions on Computers, 1982
- On an improved algorithm for decentralized extrema finding in circular configurations of processorsCommunications of the ACM, 1982
- Distributed multi-destination routingPublished by Association for Computing Machinery (ACM) ,1982
- Decentralized extrema-finding in circular configurations of processorsCommunications of the ACM, 1980
- Local and global properties in networks of processors (Extended Abstract)Published by Association for Computing Machinery (ACM) ,1980
- An improved algorithm for decentralized extrema-finding in circular configurations of processesCommunications of the ACM, 1979