bit complexitycommunicationdeterministic algorithmdistributed algorithmsgapgap theoremmessage complexitymessagesnetworksprocessorsring of processors
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) Analysis of algorithms and problem complexity (68Q25) Distributed algorithms (68W15)
Recommendations
Cited in
(15)- Computing on a partially eponymous ring
- Language complexity on the synchronous anonymous ring
- The distributed bit complexity of the ring: From the anonymous to the non-anonymous case
- Computing on anonymous networks with sense of direction
- A coding theorem for distributed computation
- Better computing on the anonymous ring
- Toward computability of trace distance discord
- Computing on an anonymous ring
- scientific article; zbMATH DE number 17531 (Why is no real title available?)
- Computing functions on asynchronous anonymous networks
- Hundreds of impossibility results for distributed computing
- Weak models of distributed computing, with connections to modal logic
- Brief announcement: Know your audience. Communication model and computability in anonymous networks
- On the complexity of computation in the presence of link failures: The case of a ring
- The communication complexity for decentralized evaluation of functions
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)
