Simple and efficient local codes for distributed stable network construction

DOI10.1145/2611462.2611466zbMath1321.68029arXiv1309.6978OpenAlexW1994387210MaRDI QIDQ5892129

Paul G. Spirakis, Othon Michail

Publication date: 3 September 2015

Published in: Distributed Computing, Proceedings of the 2014 ACM symposium on Principles of distributed computing (Search for Journal in Brave)

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

zbMATH Keywords

populationfairnessstabilizationself-organizationstructure formationdistributed protocolnetwork constructionhomogeneous populationdistributed network constructioninteracting automatarandom schedule

Mathematics Subject Classification ID

Communication networks in operations research (90B18) Network design and communication in computer systems (68M10) Formal languages and automata (68Q45) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Distributed systems (68M14) Network protocols (68M12) Distributed algorithms (68W15)

Related Items

Distributed computation and reconfiguration in actively dynamic networks, Traveling salesman problems in temporal graphs, Simple and fast approximate counting and leader election in populations, Information Spreading by Mobile Particles on a Line, A Glimpse at Paul G. Spirakis, An Introduction to Temporal Graphs: An Algorithmic Perspective, Terminating distributed construction of shapes and patterns in a fair solution of automata, Pushing lines helps: efficient universal centralised transformations for programmable matter, Fault tolerant network constructors, The canonical amoebot model: algorithms and concurrency control, On geometric shape construction via growth operations, Centralised connectivity-preserving transformations by rotation: 3 musketeers for all orthogonal convex shapes, On geometric shape construction via growth operations, Network Constructors: A Model for Programmable Matter, CADbots: algorithmic aspects of manipulating programmable matter with finite automata, Shape recognition by a finite automaton robot, On the transformation capability of feasible mechanisms for programmable matter, Connectivity preserving network transformers, Universal coating for programmable matter, Forming tile shapes with simple robots, Connectivity Preserving Network Transformers, Simple and efficient local codes for distributed stable network construction, On efficient connectivity-preserving transformations in a grid, Centralised connectivity-preserving transformations for programmable matter: a minimal seed approach, Centralised connectivity-preserving transformations for programmable matter: a minimal seed approach, Distributed transformations of Hamiltonian shapes based on line moves, Distributed transformations of Hamiltonian shapes based on line moves, Threshold-based network structural dynamics, Threshold-based network structural dynamics, How Many Cooks Spoil the Soup?, On the Runtime of Universal Coating for Programmable Matter, How many cooks spoil the soup?, An Introduction to Temporal Graphs: An Algorithmic Perspective^*

Uses Software

• AmoebotSim

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Mediated population protocols
• Passively mobile communicating machines that use restricted space
• Speed faults in computation by chemical reaction networks
• The computational power of population protocols
• Forming sequences of geometric patterns with oblivious mobile robots
• Computation in networks of passively mobile finite-state sensors
• Terminating Distributed Construction of Shapes and Patterns in a Fair Solution of Automata
• Active self-assembly of algorithmic shapes and patterns in polylogarithmic time
• Emergence of Scaling in Random Networks
• The program-size complexity of self-assembled squares (extended abstract)
• Distributed Anonymous Mobile Robots: Formation of Geometric Patterns
• On utilizing speed in networks of mobile agents
• Names Trump Malice: Tiny Mobile Agents Can Tolerate Byzantine Failures
• Timing in chemical reaction networks
• Simple and efficient local codes for distributed stable network construction