Engineering with Complexity and Emergence
November 15-16, 2005
Two half day sessions on Tue 15th (pm) and Wed 16th (pm)

Satellite workshop of the
European Conference on Complex Systems


ECE'05 workshop news:
>> updated workshop programme now available <<
>> special issue publication in TAAS <<

What is the workshop about?

New software engineering paradigms are being created by harnessing the properties of complex systems such as emergence. This radical new approach to building robust, scalable and practical systems is influenced, but not limited to, inspiration from both biological systems and social systems. These systems demonstrate some very "nice" properties that engineers strive for. For example, properties of self-repair, self-management and self-adaptation to changing environments. These so-called "self-star" (or self-*) properties are increasingly sought by engineers working with complex "always-on" distributed information systems. This is because central control, administration and programming of massively distributed semi-autonomous entities is not a realistic option. But currently the engineering of such systems is a "black art" with little established methodology or toolbox of dependable and tested mechanisms that can harness emergence for self-organisation and management tasks. Some even claim that "emergence", by definition, can never be used for engineering since it depends on surprise or unexpected behaviour. In this workshop we aim to address and discuss these issues by bringing together leaders in the field and showcasing the best recent work that harnesses complexity and emergence to solve hard engineering problems within information systems. We will include presentations from the concluding EU BISON project and the on-going EU DELIS project.

Organising Committee: Ozalp Babaoglu, David Hales, Mark Jelasity, Alberto Montresor (University of Bologna, Italy), Franco Zambonelli (University of Modena and Reggio Emilia), Giovanna Di Marzo (University of Geneva, Switzerland)

Location: Cité Internationale Universitaire de Paris, 17 boulevard Jourdan, 75014 Paris

Directions and Maps
see the ECCS'05 website

:  see the ECCS'05 website

Publication: Articles based on selected talks will be considered for publication in a Special Issue of the ACM Transactions on Autonomous and Adaptive Systems Journal (TAAS).

Related Event: See also the MA4CS'05 Satellite workshop which follows ECE'05 on Friday 18th.

ECE Workshop Programme (subject to change)

Day 1 - Tuesday 15th November


Welcome and Introduction - Chair: Ozalp Babaoglu


Geoff Canright
, Telenor R&D, Norway
Engineering, without complexity, maybe with emergence

Abstract: There are three interesting and important nouns in the title of this workshop. In this talk, I will critically analyze these three nouns: what do they mean, and how do they fit together? I will avoid empty words as much as possible, by trying to ground my discussion in both the scientific and the engineering points of view. Furthermore, I will refer to some of my own work (using chemotaxis for load balancing), done in connection with the EU BISON project, to illustrate my points via concrete examples. Finally—as indicated by my title—I will propose that “complexity” is not (yet) a useful term for engineering purposes, whereas “emergence”, while in serious need of improvement, has some utility for practical engineers who need to solve real-world problems.


Mark Jelasity
, University of Bologna, Italy.
Fully decentralized and robust ranking protocols

Abstract: Emergence is often associated with a "surprise-factor": local interactions result in something unexpected at the global level. Engineering emergence is about removing this surprise. We give examples of how not to be surprised by the results of certain kinds of local interactions. In the  example we focus on the local interactions (that otherwise make some sense on their own) can be interpreted as calculating the dominant  eigenvector of certain graphs that are related to the adjacency matrix of the network topology graph, thereby providing each node with a rank value that can be used e.g. to order search hits. Credits go to Geoff Canright who directed my attention to this problem.


Coffee Break


Vincent Chevrier
, LORIA, France.
Natural inspiration for the design of complex systems

Abstract: We are interested in the design of systems  being able to produce a collective response from interactions between simple individuals. Such systems are able to exhibit a lot of “self-star” properties. To  design them, we have to define the individual behaviors (as simple as possible) such as to obtain the expected collective behavior. To tackle this engineering issue we take inspiration in natural self-organized systems: it will be the topic of the talk. After a general overview of our approach; we will present an original model of specialisation inspired from a phenomenon in rats' groups; and then; we will review the problems we face while engineering systems.


Andreas Deutsch
, Technical University Dresden
Self-organization in interacting cell networks: from microscopic rules to emergent behavior

Abstract: The purpose of this talk is two-fold. First, we demonstrate that interacting cell networks are prime candidates to study principles of self-organized pattern formation. In addition, they offer a multitude of possibilities for microscopic interactions that might also be relevant for dynamic communication networks. Examples of interacting cell systems are life cycles of bacteria or social amoebae, embryonic tissue formation, wound healing or tumour growth and metastasis. Then, we show that mathematical modeling of dynamic cell networks (biomathematics) has developed techniques which allow to analyze how specific microscopic interactions imply the emergence of a particular macroscopic behavior. These techniques might also be applied in the context of dynamic communication networks.


Manolis Koubarakis
, Technical University of Crete
Using self-organising data structures to build distributed resource sharing applications

Abstract: Distributed hash tables are self-organising data structures that have recently become prominent for the implementation of distributed resource sharing applications. In this talk, we show how to use a distributed hash table to provide information retrieval  and filtering functionality in digital library environments. In an information retrieval scenario, a user poses a query and the system returns information about matching digital resources. In an information filtering scenario, a user posts a continuous query to the system to receive notifications whenever certain events of interest take place. We demonstrate that information retrieval and filtering applications are a good candidate for the application of self-organising data structures to improve system functionality, performance and availability. This is joint work with my students Christos Tryfonopoulos and Stratos Idreos.


End of Tuesday Session

Day 2 - Wednesday 16th November


Introduction - Chair: David Hales


Franco Zambonelli, University of Modena and Reggio Emilia, Italy.
Tackling the "engineering emergence" oxymoron: some preliminary thoughts

Abstract: It is getting more and more recognized that the exploitation of self-organization and emergent behaviors can be a feasible way to bear the complexities and dynamics of modern ICT systems. However, attempting at defining a practice of engineering such emergent and self-organizing systems in a reliable and repeatable way appears a contradiction in terms. This talk develops some preliminary thoughts on how such an challenge can be possibly tackled, i.e., on which concepts and guidelines promise to properly pave the way to a practice of engineering emergent systems.


Coffee Break


Alberto Montresor
, University of Trento, Italy.
Engineering topologies: from self-organization to self-maintenance

Abstract: The role of topologies in large-scale overlay networks is becoming more and more important. But building and maintaining topologies is not simple: it is not a case that many popular overlay networks are based on unstructured, "unwanted" topologies. The goal of this talk is to show how several different topologies may be built using a simple, common mechanism. Credits go to Mark Jelasity and his T-Man protocol.


Gianni Di Caro, IDSIA, Switzerland
Swarm intelligence for adaptive routing in dynamic networks

Abstract: We introduce AntHocNet, a novel swarm intelligence algorithm for adaptive routing in heterogeneous networks. Building on ideas from previous work on the application of the Ant Colony Optimization framework to routing, and in combination with techniques from dynamic programming, AntHocNet is a reactive-proactive algorithm tailored to deal with the challenges posed by highly dynamic network environments. We apply AntHocNet to both mobile ad hoc networks and wired datagram networks.  Extensive experimental results will show the effectiveness of the general swarm intelligence approach over a broad range of network scenarios characterized by different sources of non-stationarity. We compare the algorithm with popular state-of-the-art approaches and show its superiority in all the considered situations. We also present results indicating that the algorithm is remarkably scalable in terms of performance and generated overhead.


Panel Discussion



BISON logo