Message lower bounds via efficient network synchronization
Authors:
- Gopal PanduranganGPGopal Pandurangan
- David PelegDPDavid Peleg
- Michele ScquizzatoMSMichele Scquizzato
- 1 March 2020
- journal article
- research article
- Published by Elsevier in Theoretical Computer Science
- Vol. 810, 82-95
Abstract
No abstract availableKeywords
Funding Information
- National Science Foundation (CCF-1527867, CCF-1540512, CCF-BSF-1717075, IIS-1633720)
- United States-Israel Binational Science Foundation (2016419, 2016732)
This publication has 27 references indexed in Scilit:
- Tight Bounds for Distributed Minimum-Weight Spanning Tree VerificationTheory of Computing Systems, 2013
- On the distributional complexity of disjointnessTheoretical Computer Science, 1992
- Determinism vs. Nondeterminism in Multiparty Communication ComplexitySIAM Journal on Computing, 1992
- A trade-off between information and communication in broadcast protocolsJournal of the ACM, 1990
- Optimal lower bounds for some distributed algorithms for a complete network of processorsTheoretical Computer Science, 1989
- Distributed algorithms for selection in setsJournal of Computer and System Sciences, 1988
- Lower bounds on communication complexity in distributed computer networksJournal of the ACM, 1987
- Electing a leader in a synchronous ringJournal of the ACM, 1987
- Complexity of network synchronizationJournal of the ACM, 1985
- The complexity of sorting on distributed systemsInformation and Control, 1984