Lost in self-stabilization
From MaRDI portal
Publication:2946359
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].
Recommendations
Cites work
- A constrained Potts antiferromagnet model with an interface representation
- 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
- Stochastic flips on dimer tilings
- Stochastic flips on two-letter words
- Sturmian and Episturmian Words
Cited in
(2)
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)
