Stone age distributed computing

DOI10.1145/2484239.2484244zbMath1323.68270arXiv1202.1186OpenAlexW2052474723MaRDI QIDQ5176089

Roger Wattenhofer, Yuval Emek

Publication date: 2 March 2015

Published in: Proceedings of the 2013 ACM symposium on Principles of distributed computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1202.1186

zbMATH Keywords

cellular automatamessage passingefficient algorithmsfinite state machines

Mathematics Subject Classification ID

Related Items (18)

Design patterns in beeping algorithms: examples, emulation, and analysis ⋮ Randomised distributed MIS and colouring algorithms for rings with oriented edges in \(O(\sqrt{\log n})\) bit rounds ⋮ The ANTS problem ⋮ Searching without communicating: tradeoffs between performance and selection complexity ⋮ Constant space and non-constant time in distributed computing ⋮ Counting in one-hop beeping networks ⋮ Breathe before speaking: efficient information dissemination despite noisy, limited and anonymous communication ⋮ Communication complexity meets cellular automata: necessary conditions for intrinsic universality ⋮ How many ants does it take to find the food? ⋮ Distributed Self-Stabilizing MIS with Few States and Weak Communication ⋮ Feedback from nature: simple randomised distributed algorithms for maximal independent set selection and greedy colouring ⋮ Minimizing message size in stochastic communication patterns: fast self-stabilizing protocols with 3 bits ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Weak models of distributed computing, with connections to modal logic ⋮ Dynamic networks of finite state machines ⋮ Distributed Dominating Set Approximations beyond Planar Graphs ⋮ The Synergy of Finite State Machines

This page was built for publication: Stone age distributed computing