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

DOI10.1145/2933575.2934567zbMATH Open1401.68230OpenAlexW2531598787MaRDI QIDQ4635891FDOQ4635891

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)

Cited In (1)

• An inherent bottleneck in distributed counting

   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 👍 👎
• Title not available (Why is that?) 👍 👎
• 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 👍 👎

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)