Lost in self-stabilization

DOI10.1007/978-3-662-48057-1_34zbMATH Open1465.68090arXiv1410.7669OpenAlexW2261387088MaRDI QIDQ2946359FDOQ2946359

Authors: Damien Regnault, Eric Rémila 

Publication date: 16 September 2015

Published in: Mathematical Foundations of Computer Science 2015 (Search for Journal in Brave)

Abstract: One of the questions addressed here is How can a twisted thread correct itself?. We consider a theoretical model where the studied mathematical object represents a 2D twisted discrete thread linking two points. This thread is made of a chain of agents which are lost, i.e. they have no knowledge of the global setting and no sense of direction. Thus, the modifications made by the agents are local and all the decisions use only minimal information about the local neighborhood. We introduce a random process such that the thread reorganizes itself efficiently to become a discrete line between these two points. The second question addressed here is to reorder a word by local flips in order to scatter the letters to avoid long successions of the same letter. These two questions are equivalent. The work presented here is at the crossroad of many different domains such as modeling cooling process in crystallography [2, 3, 8], stochastic cellular automata [6, 7], organizing a line of robots in distributed algorithms (the robot chain problem [5, 11]), and Christoffel words in language theory [1].

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

Recommendations

• Lost in self-stabilization: a local process that aligns connected cells
• Probabilistic Pursuits on the Grid
• Coupling and Self-stabilization
• Self-stabilization
• Self-stabilization of circular arrays of automata

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Other nonclassical models of computation (68Q09) Cellular automata (computational aspects) (68Q80)

Cites Work

• Conway's Tiling Groups
• Fully asynchronous behavior of double-quiescent elementary cellular automata
• Stochastic Cellular Automata Solve the Density Classification Problem with an Arbitrary Precision
• Sturmian and Episturmian Words
• Stochastic flips on two-letter words
• A constrained Potts antiferromagnet model with an interface representation
• Stochastic flips on dimer tilings

Cited In (2)

• Self-organisation in cellular automata with coalescent particles: qualitative and quantitative approaches
• Lost in self-stabilization: a local process that aligns connected cells

This page was built for publication: Lost in self-stabilization

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