The concept of autonomy is a central concept in distributed computational systems and in multi-agent systems in particular. 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 review existing definitions and formalisms related to the notion of autonomy. We re-introduce two concepts: relative autonomy and absolute autonomy. 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 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 a relative autonomy in such systems.