Ability to Count Messages Is Worth Θ(Δ) Rounds in Distributed Computing

DOI10.1145/2933575.2934567MaRDI QIDQ4635891zbMATH OpenOpenAlexFDO

Authors Tuomo Lempiäinen

Publication date 23 April 2018

Published in Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/2933575.2934567

zbMATH Keywords

distributed computinglower boundsbisimulationlocal algorithmsport-numbering model

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Modal logic (including the logic of norms) (03B45) Logic in computer science (03B70) Distributed systems (68M14) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Recommendations

• Accuracy of message counting abstraction in fault-tolerant distributed algorithms
• On the message complexity of distributed problems
• An inherent bottleneck in distributed counting
• Distributed counting along lossy paths without feedback
• Trading bit, message, and time complexity of distributed algorithms
• Time-message trade-offs in distributed algorithms
• On the scalability and message count of trickle-based broadcasting schemes
• Average number of messages for distributed leader-fitting in rings of processors
• Average number of messages for distributed leader finding in rings of processors

Cited in

(2)

• Weak models of distributed computing, with connections to modal logic
• An inherent bottleneck in distributed counting

This page was built for publication: Ability to Count Messages Is Worth Θ(Δ) Rounds in Distributed Computing

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