Computer Science – Distributed – Parallel – and Cluster Computing
Scientific paper
2005-12-20
Computer Science
Distributed, Parallel, and Cluster Computing
20 pages, significant revision
Scientific paper
We consider asynchronous networks of identical finite (independent of network's size or topology) automata. Our automata drive any network from any initial configuration of states, to a coherent one in which it can carry efficiently any computations implementable on synchronous properly initialized networks of the same size. A useful data structure on such networks is a partial orientation of its edges. It needs to be flat, i.e. have null holonomy (no excess of up or down edges in any cycle). It also needs to be centered, i.e. have a unique node with no down edges. There are (interdependent) self-stabilizing asynchronous finite automata protocols assuring flat centered 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 such set of protocols compliant with our interface conditions.
Itkis Gene
Levin Leonid A.
No associations
LandOfFree
Flat Holonomies on Automata Networks does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Flat Holonomies on Automata Networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Flat Holonomies on Automata Networks will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-661946