Description

Increasingly inexpensive processors and sensors have made computing systems pervasive to every aspect of our lives. These systems can range from active sensor networks monitoring a facility to passive tags storing location-based information. As these systems become more common, and increase in size and complexity, challenges arise for their programming and control; they become true complex systems. A key challenge is to provide powerful programming models to facilitate the development of applications in dynamic and heterogeneous environments. The main conceptual difficulty is that we typically have direct control only over the local activities of individual components, while the application task is often expressed at the global scale. Bridging the gap between local and global activities is not easy, but it is possible: distributed algorithms have been designed for many tasks ranging from sensor networks and MANET (mobile ad-hoc networks) to organization of information in complex networks. However, most of these algorithms are closely tied to the application task and domain, making them difficult to generalize to solve other tasks.

One promising framework is that of self-organization, where control is widely distributed, and the many separate components act and interact in such a way as to produce a desired global result. Although this approach is potentially very powerful, with numerous examples of biological and social systems that robustly work in this way, there are many aspects of designing such systems that are not yet well understood.

There are two main classes of problems that must be addressed to fulfill the power of self-organization in pervasive computing:

1. Engineering Self-Organized Systems
   • Most work in self-organization starts by reverse-engineering a given self-organizing biological or social system (e.g., ant foraging), and applying the result to a specific application scenario (e.g., routing in sensor networks). Although this approach produces powerful results for that specific application scenario, it is not trivial to generalize it to other scenarios, and to derive general engineering methodologies from it.
   • Other works start by directly engineering distributed algorithms that rely on a few basic mechanisms (e.g., broadcast and localization), and, by exploiting local interactions and local computations, can provably lead a system to a final coherent global state. Unlike traditional distributed algorithms, self-organizing algorithms disregard micro-level issues such as ordering of events, process synchronization, and structure of the underlying network (issues for which no possibility of control is assumed). Rather, they require that the algorithm will eventually converge despite micro-level contingencies (e.g., network dynamics, failure of some components). Although this approach produces the desired system functionalities by design, it is difficult to apply the mechanism to complex and articulated applications with several partners involved.
   • Some work achieves self-organization by carefully designing and engineering the local interactions among individual components: glider-guns and other cellular-automata constructions are remarkable examples of this practice. Such systems may lack desirable features of those discussed above, such as robustness to perturbations. As in the previous case, the construction of such algorithms is not driven by sound engineering principles, instead being more of a trial-and-error procedure that is not easily generalizable. Moreover, it is very difficult to find concrete applications for such systems.
2. Using Self-Organization in Complex Systems
   • Many self-organizing systems revolve around a multitude of easily expendable agents repetitively interacting according to some pattern. However, in many computing scenarios, individual devices are not so disposable (e.g., PDAs), and interactions have to comply with strict energy budgets (as in sensor networks). Accordingly, the application of self-organizing ideas has to be carefully tuned to such characteristic scenario requirements.
   • Many self-organizing systems consider a homogeneous set of components (e.g., ants, cells, etc.). Most complex computing scenarios, by contrast, involve considerable heterogeneity. Components can differentiate both in terms of resources available (Internet servers vs. wireless sensors) and in terms of functionalities (client, service provider, broker, etc.). How can we apply and possibly take advantage of such heterogeneity in the self-organizing mechanisms?
   • Nature has demonstrated over and over that it can provide solutions to computational problems (nature-inspired computing). How can the new science spawned from self-organized nature-inspired approaches help us build more intelligent and reliable systems?
   • Self-organizing systems typically assume that their components will follow specified behaviors even if they have no knowledge of the global task or of their role in achieving it (e.g., ants are hard-wired to carry out a given foraging algorithm, and there is nothing they can do about it). To apply self-organization to concrete complex scenarios, it may be important to encourage users to participate by giving them explicit knowledge of the global process, e.g., developing applications allowing them to see and understand what they are achieving collectively.
   • An essential part of self-organization is the interaction between individuals. When modeling these interactions, one generally falls into the so-called new science of networks. Interactions between individuals can generally be modeled as a complex network. Studying the dynamics of the network (how the network changes) and the dynamics in the network (how the interactions in the network changes) are very important in the modeling and engineering of self-organized behavior.

The aim of this track is to foster research and discussion on the above two sets of problems. In particular, the goal is to bring together researchers and practitioners working on both the theory and the deployment of self-organizing and complex systems, with the goal of cross-pollination between different fields and approaches. Participants will share analytical tools and real-world experiences, make contacts leading to new applications, and advance the understanding of self-organization and its use in pervasive systems.

Topics to be covered in this track include, but are not limited to, the following:

• Context-aware computing
• Middleware services and agent technologies for pervasive computing
• Wireless sensor networks and RFID technologies
• Mobile/wireless computing systems and services
• Intelligent environments, smart devices and smart spaces
• Theory of self-organizing systems: understanding how global results emerge from local actions, etc.
• Complex Systems: Complex Networks, Swarm Systems, Bio-Inspired Systems.
• Control of self-organizing systems: designing low-level behaviors to achieve desired high-level results, etc.
• Leveraging properties of self-organizing systems: robustness, scalability, etc.
• Macro-programming
• Nature Inspired Computing