Distributed Control for AI

This paper discusses a number of elementary problems in distributed computing and a couple of well-known algorithmic "building blocks", which are used as procedures in distributed applications. We shall not strive for completeness, as an enumeration of the many known distributed algorithms would be pointless and endless. We do not even try to touch all relevant sub-areas and problems studied in distributed computing, because they are not all relevant to Distributed AI. Rather than an algorithm catalogue, the paper aims to be an eye-opener for the possibilities of the distributed computing model, an introduction to designing and reasoning about the algorithms, and a pointer to some literature. The paper introduces the distributed model and illustrates the various possibilities and difficulties with algorithms to compute spanning trees in a network. We show how the communication and time complexities of the algorithms are evaluated. Then a more complicated, but relevant control problem is studied, namely termination detection. This study reveals how intricate it is to make information about a distributed global state available to a node locally. Termination detection occurs in distributed applications of all areas and is not specific for Distributed AI. Application of some distributed control techniques is exemplified in the later sections in distributed computations for Artificial Intelligence problems. We discuss a distributed implementation of Arc Consistency and Constraint Satisfaction and observe how termination detection and distributed evaluation of functions play a role. The paper nally presents a distributed graph algorithm, illustrating another termination detection principle, and providing an example of broadcast/convergecast and controller movement