Towards a Theory of Self-organization

Self-organization is an evolutionary process in which the e.ects of the environment are minimal; i.e., where the development of new, complex structures primarily takes place in and throughout the system itself. Natural phenomena, living forms, or social systems (e.g., growing crystals, cells aggregation, ant colonies) are examples of self-organizing systems in which a global order of the system emerges from local interactions. In the newly emerging fields of distributed systems (p2p, ad-hoc networks, sensor networks, cooperative robotics), self-organization has become one of the most desired properties. The major feature of all recent scalable distributed systems is their extreme dynamism in terms of structure, content, and load. In peer-to-peer systems, self-organization is handled through protocols for node arrival and departure, based either on a fault-tolerant overlay network, such as in CAN, Chord, Pastry, or on a localization and routing infrastructure [2]. In ad-hoc networks, self-organizing solutions have been designed to cluster ad-hoc nodes [4]. Self-organizing algorithms have also been developed to arrange mobile robots into prede.ned geometric patterns (e.g., [3]).