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.
Recommendations
Cited in
(25)- Design patterns in beeping algorithms: examples, emulation, and analysis
- Breathe before speaking: efficient information dissemination despite noisy, limited and anonymous communication
- Minimizing message size in stochastic communication patterns: fast self-stabilizing protocols with 3 bits
- The ANTS problem
- Searching without communicating: tradeoffs between performance and selection complexity
- Counting in one-hop beeping networks
- Constant space and non-constant time in distributed computing
- Randomised distributed MIS and colouring algorithms for rings with oriented edges in \(O(\sqrt{\log n})\) bit rounds
- Computing by Swarm Networks
- Distributed execution of automata networks on a computing medium: introducing IfAny machines
- Distributed Dominating Set Approximations beyond Planar Graphs
- scientific article; zbMATH DE number 7559466 (Why is no real title available?)
- scientific article; zbMATH DE number 7561256 (Why is no real title available?)
- The Synergy of Finite State Machines
- Feedback from nature: simple randomised distributed algorithms for maximal independent set selection and greedy colouring
- Weak models of distributed computing, with connections to modal logic
- Communication complexity meets cellular automata: necessary conditions for intrinsic universality
- Distributed Self-Stabilizing MIS with Few States and Weak Communication
- The hardness of local certification of finite-state dynamics
- Undecidability of the emptiness problem for weak models of distributed computing
- On the limits of information spread by memory-less agents
- Self-stabilizing MIS computation in the beeping model
- Asynchronous self-stabilization made fast, simple, and energy-efficient
- Brief announcement: Self-stabilizing MIS computation in the beeping model
- How many ants does it take to find the food?
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)
