Advertisement
Published in:
2006 | OriginalPaper | Chapter
Flat Holonomies on Automata Networks
(a more recent version available at: http://arXiv.org/abs/cs.DC/0512077)
Authors : Gene Itkis, Leonid A. Levin
Published in: STACS 2006
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
We consider asynchronous dynamic networks of identical finite (independent of the network size) automata. A useful data structure on such networks is a partial
orientation
of its edges. It needs to be
straight
, i.e. have null holonomy (the difference between the number of up and down edges in each cycle). It also needs to be
centered
, i.e., have a unique node with no down edges. Using such orientation, any feasible computational task can be efficiently implemented with self-stabilization and synchronization. There are (interdependent) self-stabilizing asynchronous finite automata protocols that straighten and centralize any orientation. Such protocols may vary in assorted efficiency parameters and it is desirable to have each replaceable with any alternative responsible for a simple limited task. We describe an efficient reduction of any computational task to any set of such protocols compliant with our interface conditions.