Societies of randomly interacting finite-state automata

Most work in distributed algorithms assumes that the agents in a system can store nontrivial amounts of data and perform complex calculations. But in systems consisting of massive amounts of bulk-produced hardware or of small mobile agents tightly constrained by the systems they run on, the amount of storage available at each agent may be severely limited. Such limitations are not crippling if the system designer has fine control over the interactions between agents, as even finite-state agents can be regimented into cellular automata as powerful as Turing machines. But if the system designer cannot control these interactions, it is not clear what, if anything, the system can compute. The present work seeks to answer this question by studying societies of randomly interacting finite-state automata.;First, we consider an illustrative example: an artificial society of agents, each required to make decisions while operating in an environment of incomplete information about each other. We show that the natural algorithms one would provide for the cooperation of agents fail: they produce uncooperative societies of agents refusing to interact with anybody. While we can tweak the algorithms so as not to collapse, these would only be ad hoc solutions.;We take a systematic approach. Scenarios such as that of our example can be viewed as instances of a statistics problem called the bandit problem. We show how automata used to solve the simplest version of the problem can be used to solve more complex ones. We go a step further and ask how a society of automata can be extended into a more sophisticated system of distributed computation. How powerful would it be? We introduce urn automata, a new class of automata consisting of an input tape, a finite-state controller, and an urn containing colored tokens. The controller can sample and replace tokens in the urn but cannot control which tokens it receives. A special class of urn automata models societies of finite-state automata that interact through random, pairwise encounters. We show that an urn automaton with O (f(n)) tokens can, with high probability, simulate a probabilistic Turing machine using O(log f(n)) space and vice versa.