Dynamic networks of finite state machines

DOI10.1016/j.tcs.2017.05.025zbMath1437.68020arXiv1706.03721OpenAlexW2964018776MaRDI QIDQ2292917

Yuval Emek, Jara Uitto

Publication date: 6 February 2020

Published in: Theoretical Computer Science, Structural Information and Communication Complexity (Search for Journal in Brave)

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

zbMATH Keywords

dynamic networksnetworked finite automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Graph theory (including graph drawing) in computer science (68R10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Distributed systems (68M14) Distributed algorithms (68W15) Biologically inspired models of computation (DNA computing, membrane computing, etc.) (68Q07)

Related Items (2)

Unnamed Item ⋮ The Synergy of Finite State Machines

Cites Work

• Unnamed Item
• Unnamed Item
• Mediated population protocols
• Outer-totalistic cellular automata on graphs
• An optimal maximal independent set algorithm for bounded-independence graphs
• Computation in networks of passively mobile finite-state sensors
• Beeping a maximal independent set
• A log-star distributed maximal independent set algorithm for growth-bounded graphs
• Improved compact routing schemes for dynamic trees
• Fault-containing self-stabilizing algorithms
• A Biological Solution to a Fundamental Distributed Computing Problem
• Local Computation
• The Locality of Distributed Symmetry Breaking
• Bounded Asynchrony: Concurrency for Modeling Cell-Cell Interactions
• Deploying Wireless Networks with Beeps
• On Broadcasting in Radio Networks--Problem Analysis and Protocol Design
• Deterministic coin tossing with applications to optimal parallel list ranking
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• A fast and simple randomized parallel algorithm for the maximal independent set problem
• A Scheme for Fast Parallel Communication
• Locality in Distributed Graph Algorithms
• Fault-Local Distributed Mending
• Tight Fault Locality
• Distributed Computing: A Locality-Sensitive Approach
• An Improved Distributed Algorithm for Maximal Independent Set
• On the Complexity of Distributed Network Decomposition
• The forgiving graph
• Stone age distributed computing
• Feedback from nature
• Maximal independent sets in multichannel radio networks
• Active and Concurrent Topology Maintenance
• What cannot be computed locally!
• A mutual exclusion algorithm for ad hoc mobile networks

This page was built for publication: Dynamic networks of finite state machines