### Automata on Distributed Alphabets

Madhavan Mukund

*Modern Applications of Automata Theory*,
Deepak D'Souza and Priti Shankar (eds),
World Scientific (2012), 257–289.

### Abstract

Traditional automata theory is an extremely useful
abstraction for reasoning about sequential computing devices.
For distributed systems, however, there is no clear consensus
on how best to incorporate various features such as spatial
independence, concurrency and communication into a formal
computational model. One appealing and elegant approach is
to have a network of automata operating on a distributed
alphabet of local actions. Components are assumed to
synchronize on overlapping actions and move independently on
disjoint actions. We describe two formulations of automata
on distributed alphabets, synchronous products and
asynchronous automata, that differ in the degree to which
distributed choices can be coordinated. We compare the
expressiveness of the two models and provide a proof of
Zielonka's fundamental theorem connecting regular trace
languages to asynchronous automata. Along the way, we
describe a distributed time-stamping algorithm that is basic
to many interesting constructions involving these automata.