1 Introduction
A few decades ago, the idea of self-organization was an intriguing option in the design of a computer application, and its proponents could engage in spirited debate with more classical views of software structure. Today, in many domains (particularly those based on computer networks), the question is no longer whether to use self-organization. Real-world open systems with thousands of autonomous components do in fact organize themselves, for better or for worse. The challenge before us is to understand this dynamic and learn how to manage it (Scholtes, Reference Scholtes2011).
There is no lack of activity around software systems that in one way or another control themselves without direct human intervention. In an attempt to focus this review, we find it useful to distinguish three kinds of systems: autonomous, self-adaptive, and self-organizing. These terms are used with a wide array of meanings. We offer the following definitions, not to challenge the usage of other researchers, nor to claim that these are generally accepted, but to clarify and bound our own discussion.
An autonomous system is one that senses and responds to its environment. In software, the concept can be traced back to Wiener’s work on feedback control systems starting in the 1940s (Watson & Scheidt, Reference Watson and Scheidt2005). When the agent paradigm began to crystallize in the 1980s and 1990s, the term became common in the title ‘autonomous agent’. One widely quoted definition of ‘autonomous agent’ (Wooldridge & Jennings, Reference Wooldridge and Jennings1995) explains: ‘Agents operate without the direct intervention of humans or others, and have some kind of control over their actions and internal state’.
Recently, the term self-adaptive has come into vogue. The name suggests a system that responds to change without intervention by its creator (thus the ‘self’), but this characteristic is also true of the classic autonomous system. Definitions of ‘self-adaptive’ often distinguish it from autonomy by emphasizing the system’s ability to respond to something besides the environment. Here are two examples.
One team defines self-adaptive this way: ‘Self-adaptive systems are capable of dealing with a continuously changing environment and emerging requirements that may be unknown at design-time’ (emphasis ours; Brun et al., Reference Brun, Di Marzo Serugendo, Gqacek, Giese, Kienle, Litoiu, Mller, Pezz and Shaw2009). By this criterion, a system with a single hard-wired goal may be autonomous (adapting its behavior in the light of environmental changes in order to achieve or maintain the goal), but to be self-adaptive requires the ability to develop new goals over time, without intervention of the designer. Architectures that meet this criterion usually have some hierarchical structure of goals, and the adaptivity happens at lower levels. For example, most biological systems have a fairly immutable goal of procreation, and their self-adaptivity consists in refining their immediate plans in an effort to achieve this higher-level goal. In engineered systems, perhaps the most common form of this structure is the widely-used BDI (Belief-Desire-Intention) agent architecture (Rao & Georgeff, Reference Rao and Georgeff1991; Haddadi & Sundermeyer, Reference Haddadi and Sundermeyer1996; Kinny et al., Reference Kinny, Georgeff and Rao1996), in which agents select their intentions (changeable, immediate objectives, on which they act) from among their desires (persistent objectives). In the nature of the case, the system cannot change its top-level goal by itself. If it could, it would need some criterion to guide that adaptation, and that criterion would then become the higher-level goal. Any system’s ability to handle ‘emerging requirements that may be unknown at design-time’ is limited by the immutable top-level goal, which is known at design-time. Ultimately, the system is constrained by its designer, after all.
Another team applies the term ‘self-adaptive’ to ‘systems that are able to adjust their behavior in response to their perception of the environment and the system itself’ (emphasis ours; Cheng et al., Reference Cheng, Poladian, Garlan and Schmerl2009). This definition requires that the system be self-aware. The definition of ‘self-awareness’ is itself slippery, and the topic is the focus of a major EU research program (Egan, Reference Egan2011). Human self-awareness is recursive: we not only attend to our own state, but we are aware that we attend to our own state, and we are aware that we attend to our own state, and so forth. We know of no present-day engineered system that aspires to this kind of recursive awareness. Much work on self-adaptive software requires the system to have an internal representation of its goals (Heaven et al., Reference Heaven, Sykes, Magee and Kramer2009), or a model of its own architecture (Nierstraz et al., Reference Nierstraz, Denker and Renggli2009), or a set of explicit policies (in case of X, do Y; Georgas & Taylor, Reference Georgas and Taylor2009; Di Marzo Serugendo et al., Reference Di Marzo Serugendo, Fitzgerald and Romanovsky2010), to guide its adaptation. The system’s awareness is limited to an explicit representation that its designer has given it, and thus the ‘self’ nature of its awareness is compromised.
In sum, an autonomous system senses and responds to its environment without human intervention. Such systems are ubiquitous. Systems that claim to be self-adaptive sense and respond to something in addition to their environment, such as changing requirements or their own state, but in the examples that currently exist, this response is built in by the designer, qualifying the emphasis on the term ‘self’. Practically speaking, when we call a system self-adaptive, we imply that the changes with which the system must cope are unusually large and potentially disruptive, the kind of change that one might expect would ordinarily require redesign by a human. If we build such a system, we are claiming that it can, by itself, perform adaptations that in a previous technology generation required human intervention.
The distinction between autonomous and self-adaptive is thus a moving target. Consider, by way of illustration, the evolution of the automobile. The earliest automobiles required the human to manage all adaptation with the environment, including setting the spark advance, controlling the mixture of fuel and air, adjusting the throttle to maintain speed as the slope of the terrain changes, and adjusting speed to accommodate other vehicles. One by one, these variables have become autonomous, in the order listed (with the successive invention of the vacuum spark advance, the automatic choke, speed control, and radar sensing and braking systems). A driver accustomed (say) only to automatic spark advance would consider a car that could manage its own fuel–air mixture and control its own velocity to be self-adaptive. Modern drivers think of such a vehicle simply as autonomous. In the domain of vehicle technology, ‘self-adaptive’ now implies capabilities that are on the cutting edge of research, such as platooning, obstacle recognition and avoidance, and self-routing. A decade from now, these will be considered simply autonomous.
The self-organizing system is a special kind of autonomous system. We emphasize three points of refinement.
First, as the use of the term ‘organize’ suggests, a self-organizing system consists of multiple components that can change their interrelations. A single agent could be autonomous or self-adaptive, but we would not call it self-organizing. Definitions of self-organization often invoke the notion of disorder or ‘entropy’ across the population of elements (Parunak & Brueckner, Reference Parunak and Brueckner2001; Gershenson & Heylighen, Reference Gershenson and Heylighen2003).
Second, we are particularly interested in systems whose response to change does not require centralized reflection. As we have discussed, the awareness definition of a self-adaptive system is usually realized by explicit internal representations of aspects of the system, such as goals (Heaven et al., Reference Heaven, Sykes, Magee and Kramer2009), architecture (Nierstraz et al., Reference Nierstraz, Denker and Renggli2009), or policies (Georgas & Taylor, Reference Georgas and Taylor2009; Di Marzo Serugendo et al., Reference Di Marzo Serugendo, Fitzgerald and Romanovsky2010). We are focused on systems that require neither such explicit representations nor a central module to manage the change in the system in response to disruption. Because of this distinction, a hierarchical feedback control system, while composed of many different parts, would still be considered autonomous rather than self-organizing.
Third, to be self-organizing, this decentralized collection of entities must increase or maintain its degree of organization in the face of change. With other researchers, we measure organization in terms of the entropy of the population of elements (Parunak & Brueckner, Reference Parunak and Brueckner2001; Gershenson & Heylighen, Reference Gershenson and Heylighen2003). A self-organizing system is one that counters the natural increase of entropy among its members over time.
Our focus in this paper is on self-organizing systems, not just autonomous or self-adaptive ones. While this distinction is important and useful (Merkle et al., Reference Merkle, Middendorf and Scheidler2007), we will consider some work that does not completely meet this objective. After all, we are dealing with software engineering, not software science, and progress often depends on drawing inspiration from many sources (Di Marzo Serugendo et al., Reference Di Marzo Serugendo, Fitzgerald and Romanovsky2010; Weyns et al., Reference Weyns, Malek, Andersson and Schmerl2011).
In Section 2, we review the state of the art in software engineering for self-organizing systems. Section 3 summarizes some major trends that we see in current practice. Section 4 outlines directions for future research. Section 5 summarizes how this particular flavor of software engineering relates to the broader field, and Section 6 concludes.
2 State of the art
In this section, we begin by reviewing some of the immense literature in this field, then survey applications of self-organizing systems and some of the main mechanisms that they employ.
2.1 Literature
Our focus here is on survey articles or programmatic discussions. Later sections of this review will consider more specific studies.
While we distinguish self-organization from self-adaptation, we stand on the shoulders of extensive work in autonomous and self-adaptive software. The classic notion of a feedback control loop can be traced back to the 19th century (Maxwell, Reference Maxwell1867), and it was natural for the idea to be applied to computer programs, largely under the inspiration of Norbert Wiener (Reference Wiener1948). The flavor of adaptive control in robotic and manufacturing systems was captured in NIST’s Real-time Control System reference architecture (Albus (Reference Albus1992, Reference Albus1997)). Later, IBM’s Autonomic Computing Initiative (Kephart & Chase, Reference Kephart and Chase2003; IBM, 2006) sought to apply these techniques to purely informational systems.
Autonomous systems are the focus of much robotic research, and application concerns have led to recent efforts to define a scale of autonomy (Huang et al., Reference Huang, Pavek, Novak, Albus and Messina2005) and develop methods to test a system’s autonomy (ITEA, 2010).
Self-adaptive software has been the object of two recent seminars at Schloss Dagstuhl (Cheng et al., Reference Cheng, Poladian, Garlan and Schmerl2009; de Lemos et al., Reference de Lemos, Giese, Muoller and Shaw2012), and a special issue of the Journal of Systems and Software is in preparation on this topic (Weyns, Reference Weyns2011). The topic is the object of a careful review article (Salehie & Tahvildari, Reference Salehie and Tahvildari2009), whose approach (focusing on the functions of monitoring, detecting, deciding, and acting) very clearly captures the reflective nature of self-adaptation as opposed to self-organization.
The design and control of self-organizing software per se was the focus of four editions of the ESOA (Engineering Self-Organising Applications) workshop (Di Marzo Serugendo et al., Reference Di Marzo Serugendo, Karageorgos, Rana and Zambonelli2004; Brueckner et al., Reference Brueckner, Di Marzo Serugendo, Karageorgos and Nagpal2005, Reference Brueckner, Di Marzo Serugendo and Hales2006, Reference Brueckner, Hassas, Jelasity and Yamins2007). It is treated in Gershenson’s (Reference Gershenson2007) recent dissertation, and a wide range of shorter studies will be identified in later sections of this review. The areas of self-adaptive and self-organizing systems (SASO)together are the focus of the ongoing IEEE International Conferences on Self-Adaptive and Self-Organizing Systems (SASO, 2011)Footnote 1.
2.2 Applications
Self-organization has been applied to a wide range of problems. As noted in the introduction, self-organization is unavoidable in distributed systems, especially open ones, such as networks (Bonabeau et al., Reference Bonabeau, Henaux, Guerin, Snyers, Kuntz and Theraulaz1998; Heusse et al., Reference Heusse, Guerin, Snyers and Kuntz1998; Holzer et al., Reference Holzer, de Meer and Bettstetter2008; Scholtes, Reference Scholtes2011) and water distribution (Dötsch et al., Reference Dötsch, Denzinger, Kasinger and Bauer2010), and highly desirable in managing large numbers of robots (Sauter et al., Reference Sauter, Matthews, Parunak and Brueckner2005, Reference Sauter, Matthews, Robinson, Moody and Riddle2009; Glad et al., Reference Glad, Simonin, Buffet and Charpillet2008, Reference Glad, Buffet, Simonin and Charpillet2009, Reference Glad, Buffet, Simonin and Charpillet2010) and in agile manufacturing settings (Brueckner, Reference Brueckner2000; Peeters et al., Reference Peeters, Van Brussel, Valckenaers, Wyns, Bongaerts, Kollingbaum and Heikkila2001; Valckenaers et al., Reference Valckenaers, Van Brussel, Hadeli, Bochmann, Germain and Zamfirescu2003), where it competes with hierarchical control systems, including holonic schemes (Van Brussel et al., Reference Van Brussel, Wyns, Valckenaers, Bongaerts and Peeters1998; Valckenaers & Van Brussel, Reference Valckenaers and Van Brussel2005) that we would consider self-adaptive but not self-organizing. In purely informational settings, self-organization has been used to coordinate multiple theorem provers (Denzinger & Fuchs, Reference Denzinger and Fuchs1999), to enable documents to organize themselves (Parunak et al., Reference Parunak, Rohwer, Belding and Brueckner2006) and find likely users (Brueckner et al., Reference Brueckner, Downs, Hilscher and Yinger2008), and to reassign tasks among agents (Odell et al., Reference Odell, Van Dyke Parunak, Brueckner and Sauter2003; Cicirello & Smith, Reference Cicirello and Smith2004). Mechanisms inspired by wasps and termites have been demonstrated for self-organized construction of physical systems (Werfel, Reference Werfel2006).
2.3 Mechanisms
A wide range of instances of self-organization in nature have been isolated and characterized to the point that they can be applied in artificial systems (Parunak, Reference Parunak1997; Bonabeau et al., Reference Bonabeau, Dorigo and Theraulaz1999; Camazine et al., Reference Camazine, Deneubourg, Franks, Sneyd, Theraulaz and Bonabeau2001). These derive mostly from social animals: pheromone systems (Payton et al., Reference Payton, Daily, Estowski, Howard and Lee2001; Peeters et al., Reference Peeters, Van Brussel, Valckenaers, Wyns, Bongaerts, Kollingbaum and Heikkila2001; Sauter et al., Reference Sauter, Matthews, Parunak and Brueckner2007; Kasinger et al., Reference Kasinger, Bauer and Denzinger2009; Viroli & Casadei, Reference Viroli and Casadei2009; Viroli & Zambonelli, Reference Viroli and Zambonelli2010), stimulus-based load balancing (Werfel, Reference Werfel2006), insect clustering (Kuntz & Layzell, Reference Kuntz and Layzell1997; Monmarché, Reference Monmarché1999; Handl et al., Reference Handl, Knowles and Dorigo2003; Walsham, Reference Walsham2003; Hamdi et al., Reference Hamdi, Antoine, Monmarché, Alimi and Slimane2010), firefly synchronization (Tyrrell et al., Reference Tyrrell, Auer and Bettstetter2007). But markets (Clearwater, Reference Clearwater1996; Parunak et al., Reference Parunak, Ward, Fleischer and Sauter1999) and physical systems such as potential fields (Masoud & Masoud, Reference Masoud and Masoud2000; Flacher & Sigaud Reference Flacher and Sigaud2002; Mamei & Zambonelli, Reference Mamei and Zambonelli2005; Weyns et al., Reference Weyns, Boucke and Holvoet2008; Simonin et al., Reference Simonin, Charpillet, Buffet and Glad2011) have also been invoked. While these mechanisms can be characterized in terms of feedback control, in their natural settings they are highly decentralized and do not rely on explicit models of the structure, goals, or policies of the overall system, thus qualifying as self-organizing and not just self-adaptive.
2.4 Reflection on the state of the art
While self-organizing solutions have been widely explored, they tend to have two limiting characteristics (Weyns, Reference Weyns2011). First, most applications demonstrate the capabilities of a single mechanism, and do not consider the potential interaction of a toolkit of mechanisms. Second, among software engineers there is relatively little work on the theoretical foundations of these mechanisms. We will return to these themes when we outline directions for future work.
3 Outline of main trends
Several general trends are apparent from this brief and highly selective review: decentralization, openness, imitation of nature, and reliance on simulation. These topics are empirical, not analytic: they represent our subjective impression of dominant themes, and we do not claim that they constitute a formal basis that spans the space of self-organizing systems. These characteristics reflect our definition of ‘self-organization’, and they are common enough in practice to justify focusing on systems that exhibit them.
3.1 Decentralization
Since we distinguish self-organization from self-adaptation partly by the multi-component decentralized nature of the former, decentralization is not unexpected, but we can gain understanding by analyzing it more closely.
Decentralization is not a black-or-white dichotomy. It is useful to distinguish three levels, and in a highly populous system with heterogeneous members, one can imagine gradations and combinations along this spectrum.
At one extreme, and outside our purview, are centralized systems, in which all decisions are made at a single location. We include here not only monolithic systems, but also hierarchical feedback control systems (Albus, Reference Albus1992). Holonic systems were originally motivated by emergent dynamics over a hierarchy that defines scale rather than control (Koestler, Reference Koestler1967), but engineered holonic applications often look very much like hierarchical control (Ricketts, Reference Ricketts1996; Bongaerts, Reference Bongaerts1998; Van Brussel et al., Reference Van Brussel, Wyns, Valckenaers, Bongaerts and Peeters1998). We can view such systems as centralizing two kinds of information: declarative information about the current state of the system, and imperative information that determines next steps. (In terms of the BDI agent architecture, these kinds of information are the agent’s beliefs and intentions, respectively.)
At the other extreme are systems in which each entity interacts only with those in its local vicinity. Its neighborhood defines its view of the state of the world (declarative information, or beliefs), and it can only act within that narrow purview (imperative information, or intentions).
We have defined the endpoints in terms of local vs. global interaction, involving two kinds of information (declarative and imperative). Two other, intermediate combinations of these categories are possible.
It is quite common to collect the state of the system (declarative information) centrally, then make it available to all components, which take action locally. This approach, exemplified by the blackboard architecture (Nii, Reference Nii1986a, Reference Nii1986b) and its derivative mediator architecture (Shen & Norrie, Reference Shen and Norrie1997), is efficient for small systems, but encounters scaling problems as the size of the system increases.
In principle, one could imagine an inverse structure, choosing actions centrally and forcing agents to execute them, without the benefit of central knowledge of the system state. Because of the scaling problems of maintaining a complete, timely, centralized snapshot of the full system state, attempts to centralize both state and action often approximate this scheme. Because the centralized action decisions cannot take into account the local realities of the environment, the outcome of those actions is often disappointing.
In some cases, one can detect movement along this cline. For example, Denzinger et al. (Reference Denzinger, Fuchs and Fuchs1997) began working with multiple interacting theorem provers in a centralized setting, but then revised the system to use global information but only local decisions (Denzinger & Fuchs, Reference Denzinger and Fuchs1999). In recent work in other domains, their design has moved to a distribution of both declarative and imperative information (Dötsch et al., Reference Dötsch, Denzinger, Kasinger and Bauer2010). A motivation for this movement is the increasing need for real-time response (Denzinger et al., Reference Denzinger, Kasinger and Bauer2011), which can be hindered if multiple layers of hierarchy need to be queried to make a decision (Weyns et al., Reference Weyns, Schmerl, Grassi, Malek, Mirandola, Prehofer, Wuttke, Andersson, Giese and Goschka2012).
In some domains, yet another approach to the question of centralization and decentralization is possibleFootnote 2. Sometimes there is a (domain-specific) relationship between (declarative) beliefs and (imperative) decisions. That is, certain information may be relevant only to certain decisions, and vice-versa. If the partitioning of information lends itself to a topological structure within which neighbor relations may be defined, one can localize both kinds of information, so that each process maintains state and makes decisions within its specialty, while interacting with neighbors when necessary. (If interaction with other belief-decision clusters is never necessary, attributing such a system to a single domain is of questionable value).
Complete localization of interaction does have a weakness: it limits look-ahead. ‘It only functions acceptably when the (recent) past is representative for the (near) future’ (Valckenaers, Reference Valckenaers2011). Predictive mechanisms have been proposed to address this problem (Cheng et al., Reference Cheng, Poladian, Garlan and Schmerl2009). A particularly interesting approach uses a second-level self-organizing system to make these predictions through a model of the world in which interactions are spatially local but are allowed to evolve faster-than-real-time into the future (Parunak et al., Reference Parunak, Brueckner, Weyns, Holvoet and Valckenaers2007; Holvoet et al., Reference Holvoet, Weyns and Valckenaers2010). Mathematically, this approach is captured by the Monte Carlo tree search approach to learning Markov transition probabilities (Kearns et al., Reference Kearns, Mansour and Ng1999; Kocsis & Szepesvári, Reference Kocsis and Szepesvári2006).
Market systems represent an interesting segment of the centralized–decentralized spectrum. Classical Walrasian markets depend on posting bids centrally so that agents can make local decisions (Clearwater, Reference Clearwater1996), thus embodying our midpoint of global declarative information and local imperative information. However, an alternative form of market, Edgeworth barter (Axtell & Epstein, Reference Axtell and Epstein1997), allows agents to interact pairwise, and still guarantees global convergence. This form of market is completely distributed, and has been applied to problems of distributed constraint optimization (Parunak et al., Reference Parunak, Ward, Fleischer and Sauter1999).
3.2 Openness
In building a self-organizing system from the ground up, one can impose homogeneity on the elements. However, the kinds of self-organization that are being imposed on us (say, through the internet) force us to deal with systems whose elements do not conform to a single blueprint.
Openness greatly increases the complexity of a system. Any single element needs to be prepared to interact with everything outside of its own boundary. These candidates for interaction now include not only other elements that are like itself, but also technical, geographic, political, social and economic realities (Di Marzo Serugendo, Reference Di Marzo Serugendo2009; Scholtes, Reference Scholtes2011). Because we cannot predict all of these influences in advance, the line between the preparation of the system (its specification, design, implementation, and testing) and its operation is greatly blurred, a distinction to which we shall return.
In a closed system, entities can be designed to interact directly with each other. The need to cope with an open system has led researchers to focus on a common framework or infrastructure. Any agent that can interact with this infrastructure can be included in the system. At the most primitive level, the physical world is the infrastructure, and agents must have physical sensors and actuators to deal with it, an approach exploited in the axiom that ‘the world is its own best model’ (Brooks, Reference Brooks1991). In the natural world, animals sometimes use the physical world to hold arbitrary markers (for instance, insect pheromones), which is one form of stigmergy (Grassé, Reference Grassé1959)Footnote 3. Disembodied agents require a computational framework to hold such markers, such as a smart sensor network or RFID chips, and a major line of research (Mamei & Zambonelli, Reference Mamei and Zambonelli2005; aliCE, 2008; Viroli & Omicini, Reference Viroli and Omicini2011) is focused on designing such frameworks and their component mechanisms (Omicini & Zambonelli, Reference Omicini and Zambonelli1999; Omicini, Reference Omicini2002; Omicini et al., Reference Omicini, Ricci, Viroli, Castelfranchi and Tummolini2004; Viroli et al., Reference Viroli, Ricci, Zambonelli, Holvoet and Schelfthout2007).
The framework approach to openness imposes a ‘lowest-common denominator’ on all interacting components. There is a trade-off between the simplicity of the common interface to the framework and the range of entities that can interact. A very simple interface supports the widest range of entities, but also limits the amount of information that the entities can exchange (Valckenaers, Reference Valckenaers2011). For example, a market is a framework that permits open interaction among a wide range of economic actors by reducing all considerations to a single scalar, price, discarding much detailed information along the way. This consideration has led to the development of relatively sophisticated interaction languages, such as tuple spaces (Lejter & Dean, Reference Lejter and Dean1996; Casadei et al., Reference Casadei, Viroli and Gardelli2009) and highly structured symbolic ‘pheromones’ (Peeters et al., Reference Peeters, Van Brussel, Valckenaers, Wyns, Bongaerts, Kollingbaum and Heikkila2001).
Openness has implications for the security of a system, in two opposing directions. On the one hand, the more open a system is, the fewer restrictions are imposed on an element that seeks to participate in it, and the easier it is for malicious elements to insert themselves into the system’s operation. On the other hand, the more decentralized and localized a system’s decisions are, the harder it will be for a malicious element to understand and manipulate the overall state of the system. Roughly, open systems are easier to infiltrate than closed ones, but tend to limit the extent of damage that can be done. Thus, engineering of self-organizing systems needs to draw extensively on work on cyber-security and trust (T3 Group, 2012).
3.3 Imitation of nature
We have already observed (Section 2.3) that mechanisms for self-organizing systems tend to be drawn from nature, and in particular from biological systems. This tendency can be traced directly to the problem of openness, which organisms must confront in order to survive. The more sophisticated the organism, the more structure it can impose on its own environment, and the less open that environment becomes to other entities. A parade example is the set of rich linguistic mechanisms that humans use to coordinate with one another. Computational mechanisms modeled on human consciousness and linguistic interaction are the holy grail of AI research, but still beyond our grasp. Artificial versions of cognition have been described as autistic (Valckenaers, Reference Valckenaers2011) and schizophrenic (Sengers, Reference Sengers1999; Höning, Reference Höning2011), ‘idiot savants’ with focused capability but lacking adaptability. This realization may lie behind the preference for simpler insect models in self-organizing software (Valckenaers, Reference Valckenaers2011), though in fact humans often use the same kind of simple mechanisms that insects do (Parunak, Reference Parunak2006).
3.4 Simulation
Simulation, rather than formal analysis, plays a prominent role in the engineering of most current self-organizing systems (De Wolf et al., Reference De Wolf, Holvoet and Samaey2005). The complexity of these systems makes the development of formal models difficult (Höning, Reference Höning2011). In fact, a set of even very simple agents interacting with one another has the computational power of a Turing machine (Edmonds & Bryson, Reference Edmonds and Bryson2004), or perhaps even more (Wegner, Reference Wegner1997), and by Rice’s theorem (Rice, Reference Rice1953), any non-trivial feature of such a system is formally undecidable.
Some proponents of simulation argue that a simulation, being a computer program, is a partial recursive function, and thus refuse to recognize any distinction between simulation and formal analysis (Epstein, Reference Epstein2006) such as that in the previous paragraph is invalid. The distinction we are making is not one of formal structure, but of insight. A computer program such as a simulation of a self-organizing system, while every bit as formal as a proof, has a very different structure. Most program structures are algorithmic: first do X, then do Y, and then do ZFootnote 4. Such a structure does not lend itself to determining properties such as whether the system will halt, how rapidly it converges, how thoroughly it explores the space of possible behaviors, and whether its equilibria are stable or unstable. In general, such characterizations are unattainable (Edmonds & Bryson, Reference Edmonds and Bryson2004). Thus, it is likely that the engineering of self-organizing software will continue to rely heavily on simulation. However, as with many formal results, there are special cases where formal methods can support the engineering of self-organizing systems, as we shall see in the next section.
4 Challenges for future research
The themes of current systems highlight a number of opportunities for future research. These opportunities are not unexplored, but represent the cutting edge of current work in this field. We consider first the problem of composing more complex systems, then the challenge of characterizing and controlling an existing system, and finally the objective of understanding self-organizing systems formally.
4.1 System composition
In Section 2.4, we observed that most current applications focus on a single mechanism or phenomenon. Weyns (Reference Weyns2010) demonstrates the integration of multiple mechanisms in an industrial application, but such hybrid approaches are the exception rather than the rule. Beal suggests that ‘the composition of phenomena into a larger complex system is rather understudied’ (Beal, Reference Beal2011), and identifies three areas that must be pursued.
First, self-organizing phenomena must be reduced to primitives with well-characterized properties and interfaces. The idea of method fragments (Puviani et al., Reference Puviani, Di Marzo Serugendo, Frei and Cabri2011) is to decompose an approach into fragments using SPEM (Software & Systems Process Engineering Metamodel; OMG, 2008) as the underlying formalism, so that they can be reused and combined with each other. A small but growing circle of activity in defining self-organization mechanisms as software design patterns (De Wolf & Holvoet, Reference De Wolf and Holvoet2007; Gardelli et al., Reference Gardelli, Viroli and Omicini2007; Kasinger et al., Reference Kasinger, Bauer and Denzinger2009; Holvoet et al., Reference Holvoet, Weyns and Valckenaers2010) is also a step in this direction.
Second, we need means of composition that allow self-organizing phenomena to be combined with predictable results. Current efforts that emphasize the centrality of frameworks (aliCE, 2008) and architectures (Weyns, Reference Weyns2010) are seeking to address this problem, but the need for ‘predictable results’ awaits advances in formal analysis (Section 4.3).
Third, we need means of abstraction that allow details of a complex self-organizing system to be hidden when engineering or analyzing larger subunits. This characteristic, identified by Simon as critical to artificial systems (Simon, Reference Simon1969), also requires a depth of formal insight that is not yet at hand.
The imitation of nature that is so common in identifying individual mechanisms for self-organization holds promise here as well, if we shift our focus from the individual organisms or species to the level of the ecosystem (Kephart et al., Reference Kephart, Hogg and Huberman1989; Brueckner, Reference Brueckner2000; Janssen, Reference Janssen2002; Viroli & Zambonelli, Reference Viroli and Zambonelli2010; Beal, Reference Beal2011; SAPERE, 2011). In natural ecosystems, individual organisms interact in different ways, including amensalism, competition, antagonism, commensalism, and competition. For example, in a mutualistic relation such as pollination, insects and plants benefit one another by exchanging products or services. Tools such as service-oriented architectures (Brazier et al., Reference Brazier, Kephart, Parunak and Huhns2009) can enable software entities to discover one another and dynamically compose themselves into larger systems on the basis of mutually beneficial interactions.
4.2 System characterization and control
People build systems to perform some task, and need to be able to characterize their behavior and control them.
At design time, we need to understand a range of trade-offs that self-organizing mechanisms impose. These include (Denzinger et al., Reference Denzinger, Kasinger and Bauer2011) locality vs. optimality, optimality vs. flexibility, scalability vs. efficiency, efficiency vs. centralization, centralization vs. decentralization, exploration vs. exploitation, and greediness vs. purposefulness. (All of these trade-offs presume that we have well-defined measures of each property, itself a major research challenge). Depending on the requirements of the application, certain regions of each of these scales may qualify as faulty behavior, and techniques of safety engineering can be adopted to identify and avoid them (Di Marzo Serugendo, Reference Di Marzo Serugendo2009).
As the system is operating, we need ways to characterize its behavior. Observing and analyzing the series of events that it generates is one way to gain this insight (Hudson et al., Reference Hudson, Denzinger, Kasinger and Bauer2010). One important challenge in this task is that while the nature of the system’s behavior as acceptable or unacceptable manifests at the system level, our self-organizing agenda requires us to focus on locally observable phenomena. Information theoretic measures such as the entropy over agent options (Brueckner & Parunak, Reference Brueckner and Parunak2003) or over signals passing between agents (Holzer et al., Reference Holzer, de Meer and Bettstetter2008; Höning & La Poutre, Reference Höning and La Poutre2010) have proven a promising local window into global system behavior.
Like behavior characterization, behavior control is difficult in a decentralized setting, and is not widely explored (Weyns, Reference Weyns2011). A system of local constraints with attributes defined over component interfaces (Georgiadis et al., Reference Georgiadis, Magee and Kramer2002) is one promising way forward. Another is to deploy a control swarm in parallel with the functioning swarm (Merkle et al., Reference Merkle, Middendorf and Scheidler2007). In some cases centralization may be unavoidable, and a fruitful avenue of exploration is how to combine centralized control where necessary with local control most of the time (Di Marzo Serugendo et al., Reference Di Marzo Serugendo, Fitzgerald and Romanovsky2010).
An important current area of research that promises to contribute to system characterization and control is work on normative MAS (Boella et al., Reference Boella, Torre and Verhagen2007), particularly mechanisms for the emergence and maintenance of norms (Villatoro, Reference Villatoro2011). Results in this area offer the prospect of a system that develops its own characterization that it can then report to its stakeholders.
4.3 Formal analysis of self-organizing systems
Attempts to gain a formal purchase on self-organizing systems usually involve one or more of three critical dimensions: a vertical dimension (emergence) that relates lower-level and higher-level behaviors, a horizontal dimension (organization) that relates entities to one another within a single level, and a temporal dimension (dynamics) that explores how the system develops through time. To see the distinction among these dimensions, consider a stream of automobiles traveling down a highway. The vertical dimension describes how the behaviors of the components in an individual automobile join to produce the behavior of the overall automobile, or (at the next level) how the interactions of individual automobiles yield system-level features such as net throughput of the traffic system. The horizontal dimension includes the rules of the road that regulate the interactions of automobiles with each other. The temporal dimension describes changes in the system over time, including the transition from fluid flow to a traffic jam, or the periodic variations in traffic density depending on time of day.
4.3.1 Emergence
Perhaps the most widely recognized phenomenon in dealing with self-organizing systems is emergence (De Wolf & Holvoet, Reference De Wolf and Holvoet2005), which we define (Parunak & Brueckner, Reference Parunak and Brueckner2004) as system-level behavior that is not explicitly specified in the individual components. Emergence is a feature of the vertical dimension, describing the relation between the behavior of components and that of the entire system. Abstracted from software, the problem has a long history, forming the central focus of statistical mechanics, which seeks to relate the observed characteristics of materials at human scale to the interactions of atoms and molecules. This perspective allows the application of concepts such as entropy (Parunak & Brueckner, Reference Parunak and Brueckner2001; Guerin & Kunkle, Reference Guerin and Kunkle2004; Holzer et al., Reference Holzer, de Meer and Bettstetter2008; Scholtes, Reference Scholtes2010), phase shifts (Savit et al., Reference Savit, Brueckner, Parunak and Sauter2002; Brueckner & Parunak, Reference Brueckner and Parunak2005; Scholtes et al., Reference Scholtes, Botev, Hohfeld, Schloss and Esch2008), master equations (Bonabeau, Reference Bonabeau2002; Lerman et al., Reference Lerman, Martinoli and Galstyan2005), and universality (Parunak et al., Reference Parunak, Brueckner and Savit2004) to multi-agent systems. There are further insights to be gained from this approach. For example, the renormalization group (Binney et al., Reference Binney, Dowrick, Fisher and Newman1992) has the potential to illuminate discontinuities in the behavior of a self-organizing system. By considering the system as it approaches certain limits (e.g. low agent density and high number of agents, allowing the use of a gas model, as in Bachrach et al. (Reference Bachrach, Beal and McLurkin2010)), we can place bounds on system characteristics of interest, offering ‘thermodynamic guarantees’ (Scholtes, Reference Scholtes2011) of system behavior.
The mapping from micro to macro behaviors is not symmetrical. To derive the macro behavior from the micro, we run simulations, or (in the appropriate limits) apply techniques from statistical mechanics, and these techniques are useful in system verification. Earlier in the design process, given a specified macro behavior, we need to find micro behaviors that will yield it. The best approach to this problem that we know consists of various forms of generate and test, such as synthetic evolution, which has been applied successfully to define local agent behaviors satisfying a macro specification (Sauter et al., Reference Sauter, Matthews, Parunak and Brueckner2002; Booker, Reference Booker2003). This approach requires a system architecture whose representation lends itself to such evolutionary search, one whose structure remains valid under genetic operators such as mutation and crossover.
An interesting facet of the vertical problem is the level at which goals are satisfied. Individually selfish agents may not yield good results at the group level. We need to develop ways to define and achieve ‘group-selfish behavior’ (Valckenaers, Reference Valckenaers2011), in which the system as a whole pursues objectives that may not be optimal from the point of view of the components. Insights into this objective may come from biology. The notion of the gene, rather than the individual, as the focus of natural selection Dawkins (Reference Dawkins1976) can be viewed as a process for favoring a well-defined group of agents (those agents possessing the gene) as opposed to individuals.
4.3.2 Organization
The horizontal dimension explores how constraints on which agents can interact affect the behavior of the whole system. Patterns of interactions among agents at the same level are naturally represented as a graph, a class of mathematical object that is amenable to a variety of formal tools (Newman, Reference Newman2010). For example, useful definitions of autonomy and emergence can be formalized in terms of entropy on signals over the edges in the interaction graph (Holzer et al., Reference Holzer, de Meer and Bettstetter2008), and usability can be defined in terms of similar measures on edges connecting the system to users (Höning & La Poutre, Reference Höning and La Poutre2010). It has been suggested (Scholtes, Reference Scholtes2010) that the Laplacian spectrum of a network, which captures aspects of the graph’s modular and hierarchical structures, may facilitate formalization of the relation between these structures and dynamical processes such as distributed consensus, decentralized coordination and information dissemination (Scholtes, Reference Scholtes2011).
4.3.3 Temporal
Self-organization is a process that takes place through time, and an adequate formalization of self-organizing systems must support reasoning about the temporal dimension. In many cases, systems need to predict their own behavior in order to adapt appropriately (Parunak et al., Reference Parunak, Brueckner, Weyns, Holvoet and Valckenaers2007; Cheng et al., Reference Cheng, Poladian, Garlan and Schmerl2009; Holvoet et al., Reference Holvoet, Weyns and Valckenaers2010; Valckenaers, Reference Valckenaers2011), but the nonlinear nature of component interactions means that trajectories diverge over time, leading to a prediction horizon (Parunak et al., Reference Parunak, Belding and Brueckner2008) beyond which any prediction is essentially random. Estimating this horizon is critical to scoping the predictive activity of a system, and quantifying the uncertainty that is inevitable in a self-organizing system (Scholtes, Reference Scholtes2011).
One approach to formalizing the temporal dimension is to define formal languages to specify system development (Beal, Reference Beal2010a). At this point, one may legitimately invoke Epstein’s (Reference Epstein2006) insistence on the formal nature of any computer program, since higher-level primitives nominated by a programming language do offer a useful abstraction that can give insight to the behavior of the system programmed in the language. There are a number of examples that could inspire further work in this area, including languages modeling gene network development (Doursat, Reference Doursat2006), term-rewriting systems modeling plant growth (Prusinkiewicz & Lindenmayer, Reference Prusinkiewicz and Lindenmayer1990) and their generalization in MGS (Spicher & Michel, Reference Spicher and Michel2006), Coore’s (Reference Coore1999) Growing Point Language for interconnect topologies, Nagpal’s (Reference Nagpal2001) Origami Shape Language, Werfel’s (Reference Werfel2006) system for distributed adaptive structure generation, and Beal’s (Reference Beal2010b) Proto system for spatial computing.
5 Relation to conventional (software) engineering
Engineering of self-organizing systems has drawn much from the engineering of conventional software. In this section, we highlight some of the points of continuity and contrast.
Let’s begin with engineering in general. We have already noted the inappropriateness of the feedback control metaphor for a decentralized approach to self-organization. Nevertheless, the engineering of physical systems has a great deal to teach us. One example is how one handles noise. Engineering of physical systems, unlike conventional software engineering, devotes much attention to modeling and quantifying noise in the interfaces between components. Traditional software engineering assumes that noise (i.e. errors) can be eliminated, while other disciplines recognize that it is unavoidable and seek to damp it or provide for graceful degradation (Beal & Knight Jr, Reference Beal and Knight2008; Beal, Reference Beal2011). Another example is the adaptation of methods for safety engineering to increasing the robustness and dependability of self-organizing software (Di Marzo Serugendo, Reference Di Marzo Serugendo2009).
The notion of an architecture is a powerful way to engage the challenge of system composition and openness, providing a framework for algorithms and identify complementarities and system-level issues (Weyns, Reference Weyns2010, Reference Weyns2011). Research on frameworks to provide interaction environments for components (aliCE, 2008; Viroli & Omicini, Reference Viroli and Omicini2011) is a way to instantiate insights from an architectural approach.
There has been a historical shift in system analysis away from functional analysis and toward object-oriented system decomposition. Self-organizing systems benefit from this shift: system functions are usually distributed over many components, and even if some group of components specializes to support a function, that association happens dynamically, rather than being specified in the design (Valckenaers, Reference Valckenaers2011).
The notion of design patterns provides a useful way to abstract individual self-organizing mechanisms so that they can subsequently be recombined in novel ways (Simonin et al., Reference Simonin, Charpillet, Buffet and Glad2011). The approach has been applied to a number of mechanisms, including market-based control (De Wolf & Holvoet, Reference De Wolf and Holvoet2007), gradient fields (De Wolf & Holvoet Reference De Wolf and Holvoet2007; Kasinger et al. Reference Kasinger, Bauer and Denzinger2009), predictive swarms (Parunak et al., Reference Parunak, Brueckner, Weyns, Holvoet and Valckenaers2007; Weyns et al., Reference Weyns, Schmerl, Grassi, Malek, Mirandola, Prehofer, Wuttke, Andersson, Giese and Goschka2012), replication, collective sort, evaporation, aggregation, and diffusion (Gardelli et al., Reference Gardelli, Viroli and Omicini2007). It is instructive to observe that the last three patterns are sub-components of a pheromone approach to constructing gradient fields, highlighting both the value of this approach and the need for further development.
Closely related to this work is the application of SPEM (OMG, 2008) to facilitate the isolation and integration of method fragments (Puviani et al., Reference Puviani, Di Marzo Serugendo, Frei and Cabri2011), illustrated by isolating fragments from Adelfe, CUP, MetaSelf, General Methodology, and SDA, and then recombining them using PASSI.
Finally, engineers of self-organizing systems can take advantage of recent advances in iterative and incremental development (Larman & Basili, Reference Larman and Basili2003; Beal, Reference Beal2011). It is impossible to anticipate in advance the states accessible to a self-organizing system as it evolves in an open environment. As a result, the line between development and operation inevitably blurs (Baresi et al., Reference Baresi, Bencomo, Cukic, Gorla, Inverardi, Nier-strasz, Park, Smith, Vogel, de Lemos and Andersson2010). The system must be specified in terms of desired performance and means of incrementally correcting deficiencies (Beal, Reference Beal2010b), leading to systems that grow and react rather than being constructed and controlled (Scholtes, Reference Scholtes2010). The need for this perspective is particularly strong in the verification and validation (V&V) of a system. Traditionally, successful completion of V&V is necessary before a system is deployed. Self-organizing systems require mechanisms for ‘run-time V&V’ (Becker et al., Reference Becker, Karsai, Mankovskii, Muoller, Pezze, Schaofer, Sousa, Tahvildari, Tamura, Villegas and Wong2010) that can continuously monitor the system’s performance as it reorganizes itself in response to unanticipated conditions. It is an open question whether run-time V&V can in fact be done in a fully decentralized manner, or whether some reference to an explicit model of system objectives is necessary. That is, a system can be engineered to organize itself to meet system objectives without carrying a model of those objectives, but it may be the case that it cannot report whether or not it is in fact meeting the objectives unless it has such a model, since the latter task is intrinsically reflective.
6 Conclusion
The engineering of self-organizing software is a challenging domain that has attracted a wide range of creative talent. In spite of the difficulty of the problem and the wide range of approaches, there are consistent themes and well-defined problems to focus future research. As the information universe becomes more distributed and decentralized, the difference between the engineering of self-organizing systems and that of other software will shrink, and the themes that are beginning to manifest themselves in the self-organizing community will be increasingly recognized as staples of software engineering in general.
Acknowledgments
This review relies heavily on many colleagues who were kind enough to share their observations on the field, and their own work, with us (alphabetically by last name: Bernhard Bauer, Jake Beal, Olivier Buffet, François Charpillet, Jörg Denzinger, Giovanna Di Marzo Serugendo, Regina Frei, Kurt Geihs, Arnaud Glad, Nicolas Höning, Holger Kasinger, Andrea Omicini, Ingo Scholtes, Olivier Simonin, Paul Valckenaers, Mirko Viroli, and Danny Weyns). The authors particularly appreciate the detailed reviews of the field that several respondents contributed (Beal, Reference Beal2011; Denzinger et al., Reference Denzinger, Kasinger and Bauer2011; Höning, Reference Höning2011; Scholtes, Reference Scholtes2011; Simonin et al., Reference Simonin, Charpillet, Buffet and Glad2011; Valckenaers, Reference Valckenaers2011; Viroli & Omicini, Reference Viroli and Omicini2011; Weyns et al., Reference Weyns, Malek, Andersson and Schmerl2011). Even though these reviews are not publicly available, we have borrowed extensively from their ideas and in some cases their wording, and have cited them in order to give appropriate credit. Naturally, we are responsible for how we have combined the ideas that they have so generously shared with us. Think of this exercise as an example of an ‘open system’, in which the components, in this case the contributions of our informants, are allowed to interact in ways that they perhaps did not anticipate. We provide the ‘infrastructure’ for the interaction, and as is often the case in self-organizing systems, the infrastructure makes a great deal of difference in the overall outcome. In selecting the studies that we cite, we draw heavily on the suggestions of our informants, so our citations should be understood as examples and make no claim to be exhaustive.
