Gap Theorems for Distributed Computation

DOI10.1137/0222028zbMATH Open0768.68026OpenAlexW2079860440MaRDI QIDQ4032945FDOQ4032945

Authors: 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

Recommendations

• The distributed bit complexity of the ring: From the anonymous to the non-anonymous case
• Computing functions on asynchronous anonymous networks
• Computing on an anonymous ring
• Better computing on the anonymous ring
• scientific article; zbMATH DE number 17531

zbMATH Keywords

gapnetworkscommunicationdistributed algorithmsdeterministic algorithmgap theorembit complexityprocessorsmessage complexitymessagesring of processors

Mathematics Subject Classification ID

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

Cited In (11)

• Language complexity on the synchronous anonymous ring
• Weak models of distributed computing, with connections to modal logic
• A coding theorem for distributed computation
• Computing on anonymous networks with sense of direction
• Hundreds of impossibility results for distributed computing
• Computing functions on asynchronous anonymous networks
• Toward computability of trace distance discord
• The communication complexity for decentralized evaluation of functions
• Computing on an anonymous ring
• Computing on a partially eponymous ring
• Title not available (Why is that?)

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4032945)