ABSTRACT
In this paper we study distributed algorithms on massive graphs where links represent a particular relationship between nodes (for instance, nodes may represent phone numbers and links may indicate telephone calls). Since such graphs are massive they need to be processed in a distributed and streaming way. When computing graph theoretic properties, nodes become natural units for distributed computation. Links do not necessarily represent communication channels between the computing units and therefore do not restrict the communication flow. Our goal is to model and analyze the computational power of such distributed systems where one computing unit is assigned to each node. Communication takes place on a whiteboard where each node is allowed to write at most one message. Every node can read the contents of the whiteboard and, when activated, can write one small message based on its local knowledge. When the protocol terminates its output is computed from the final contents of the whiteboard. We describe four synchronization models for accessing the whiteboard. We show that message size and synchronization power constitute two orthogonal hierarchies for these systems. We exhibit problems that {\it separate} these models, i.e., that can be solved in one model but not in a weaker one, even with increased message size. These problems are related to maximal independent set and connectivity. We also exhibit problems that require a given message size independently of the synchronization model.
- Florent Becker, Martin Matamala, Nicolas Nisse, Ivan Rapaport, Karol Suchan, and Ioan Todinca. Adding a Referee to an Interconnection Network: What Can(not) Be Computed in One Round?. International Parallel and Distributed Processing Symposium. IPDPS '11. 2011. 508--514. IEEE Computer Society. Google ScholarDigital Library
- Chandra, Ashok K., Furst, Merrick L., and Lipton, Richard J. Multi-party protocols. Proceedings of the 15th Annual ACM Symposium on Theory of Computing. STOC '83. 1983. pages 94--99. ACM. Google ScholarDigital Library
- Feldman, Jon, Muthukrishnan, S., Sidiropoulos, Anastasios, Stein, Cliff, and Svitkina, Zoya. On distributing symmetric streaming computations. ACM Trans. Algorithms. 6. 4. 2010. pages 66:1--66:19. 66. ACM. New York, NY, USA. Google ScholarDigital Library
- Babai, Laszlo, Gal, Anna, Kimmel, Peter G., and Lokam, Satyanarayana V. Communication Complexity of Simultaneous Messages. SIAM J. Comput. 33. 1. 2004. pages 137--166. Google ScholarDigital Library
- Nathan Linial. Locality in Distributed Graph Algorithms. SIAM J. Comput. 21. 1. 1992. pages 193--201. Google ScholarDigital Library
- David Peleg. Distributed computing: a locality-sensitive approach. SIAM Monographs on Discrete Mathematics and Applications. 0--89871--464--8. 2000. Google ScholarDigital Library
- Stephane Grumbach and Zhilin Wu. Logical Locality Entails Frugal Distributed Computation over Graphs. Proceedings of 35th International Workshop on Graph-Theoretic Concepts in Computer Science (WG). 2009. pages 154--165. Lecture Notes in Computer Science. 5911. Google ScholarDigital Library
- Fabian Kuhn, Thomas Moscibroda, and Roger Wattenhofer. What cannot be computed locally!. Proceedings of the 23rd Annual ACM Symposium on Principles of Distributed Computing (PODC). 2004. pages 300--309. ACM. Google ScholarDigital Library
Index Terms
- Allowing each node to communicate only once in a distributed system: shared whiteboard models
Recommendations
Allowing each node to communicate only once in a distributed system: shared whiteboard models
In this paper we study distributed algorithms on massive graphs where links represent a particular relationship between nodes (for instance, nodes may represent phone numbers and links may indicate telephone calls). Since such graphs are massive they ...
Priority Networks of Communicating Finite State Machines
Consider a network of two communicating finite state machines which exchange messages over two one-directional, unbounded channels, and assume that each machine receives the messages from its input channel based on some fixed (partial) priority relation. ...
Distributed Hybrid Gröbner Bases Computation
CISIS '10: Proceedings of the 2010 International Conference on Complex, Intelligent and Software Intensive SystemsThis paper considers parallel Grö bner bases algorithms on distributed memory parallel computers with multi-core compute nodes. We improve the pure distributed algorithm by an hybrid approach where on the compute nodes parallel threads for each ...
Comments