Stone age distributed computing

DOI10.1145/2484239.2484244zbMATH Open1323.68270arXiv1202.1186OpenAlexW2052474723WikidataQ130970688 ScholiaQ130970688MaRDI QIDQ5176089FDOQ5176089

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)

Abstract: The traditional models of distributed computing focus mainly on networks of computer-like devices that can exchange large messages with their neighbors and perform arbitrary local computations. Recently, there is a trend to apply distributed computing methods to networks of sub-microprocessor devices, e.g., biological cellular networks or networks of nano-devices. However, the suitability of the traditional distributed computing models to these types of networks is questionable: do tiny bio/nano nodes "compute" and/or "communicate" essentially the same as a computer? In this paper, we introduce a new model that depicts a network of randomized finite state machines operating in an asynchronous environment. Although the computation and communication capabilities of each individual device in the new model are, by design, much weaker than those of a computer, we show that some of the most important and extensively studied distributed computing problems can still be solved efficiently.

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

Recommendations

• A Model of an Amorphous Computer and Its Communication Protocol
• Computation in networks of passively mobile finite-state sensors
• Computation in networks of passively mobile finite-state sensors
• Computing by Swarm Networks
• scientific article

zbMATH Keywords

cellular automataefficient algorithmsfinite state machinesmessage passing

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Cellular automata (computational aspects) (68Q80) Distributed algorithms (68W15) Distributed systems (68M14)

Cited In (19)

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

This page was built for publication: Stone age distributed computing

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