Gap Theorems for Distributed Computation

DOI10.1137/0222028MaRDI QIDQ4032945zbMATHOpenAlexFDO

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

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)

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

Cited in

(11)

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

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)