Abstract
The concept of autonomy is a central concept in distributed computational systems and in multi-agent systems in particular. With diverse implications in philosophy and despite frequent use in social sciences and the theory of computation, autonomy remains somewhat a vague notion. Most researchers do not discuss the details of this concept, but rather assume a general, common-sense understanding of autonomy in the context of computational multi-agent systems. We will review the existing definitions and formalisms related to the notion of autonomy. We re-introduce two concepts: relative autonomy and absolute autonomy. We argue that even though the concept of absolute autonomy does not make sense in computational settings, it is useful if treated as an assumed property of computational units. For example, the concept of autonomous agents may facilitate more flexible and robust abstract architectures. We adopt and discuss a new formalism based on results from the study of massively parallel multi-agent systems in the context of evolvable virtual machines. We also present the architecture for building such architectures based on our multi-agent system KEA, where we use the extended notion of dynamic linking. We augment our work with theoretical results from cham algebra for concurrent and asynchronous information processing systems. We argue that for open distributed systems, entities must be connected by multiple computational dependencies and a system as a whole must be subjected to influence from external sources. However, the exact linkages are not directly known to the computational entities themselves. This provides a useful notion and the necessary means to establish an relative autonomy in such systems.