Gap Theorems for Distributed Computation

DOI10.1137/0222028zbMath0768.68026OpenAlexW2079860440MaRDI QIDQ4032945

Shlomo Moran, Manfred K. Warmuth

Publication date: 17 May 1993

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0222028

zbMATH Keywords

gapcommunicationnetworksdistributed algorithmsdeterministic algorithmgap theorembit complexityprocessorsmessage complexitymessagesring of processors

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Network design and communication in computer systems (68M10) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Distributed algorithms (68W15)

Related Items (4)

Computing on anonymous networks with sense of direction ⋮ Computing functions on asynchronous anonymous networks ⋮ Hundreds of impossibility results for distributed computing ⋮ Weak models of distributed computing, with connections to modal logic

This page was built for publication: Gap Theorems for Distributed Computation