Giovanna Di Marzo Projects

Engineering Self-Organising Applications

(SNF 21-68026.02)

Introduction

The growing diffusion of personal devices connected to Internet is promoting the development of pervasive and wireless applications, as well as those that are to be deployed on a Grid or on a P2P network. These applications are based on mobility of code and computation on networks with highly dynamic topologies. A characteristic of these applications is their self-organized and decentralized nature. They are made of several components and act without any central control. The global behaviour emerges then from the interactions of the different components. In addition, these applications should have the ability to modify their behaviour on a context-awareness basis (evolutive and survivable); and should have the ability to capture experiences for later recall.

Decentralized software raises engineering questions that techniques defined for traditional systems cannot answer: How can such an application not simply crash when part of the network is down or unreachable? Exception handling may be no longer sufficient for an autonomous component that needs to continue its execution despite failures. How can the different components interact and coordinate properly without run-time errors? Syntactical type checking needs to be assisted by a semantical description of behaviours and interactions. How to be sure that the application as a whole behaves correctly and delivers the desired (or a minimal) functionality in every situation? Design time model checking or testing need to be completed by run-time verification and guidance. What is the best way to design and program these applications? How can we perform the separation of concerns? How to engineer the applications such that a verification becomes possible?

Currently, these applications are developed in an ad hoc manner, leading to solutions that do not exploit entirely the decentralized aspect of the application, and consequently do not benefit from the whole network potentiality. There is a clear need for infrastructures that go beyond syntactical conformance at design time, and which enable to engineer autonomous components such that they have, at run-time, the necessary knowledge for engaging correct interoperable operations.

The goal of this project is to define innovative concepts for programming autonomous components able to check semantical conformance of each other at run-time, i.e., to understand the desired functionality and expected behaviour of other components, and to evaluate the issue of an interaction. We will use formal techniques as a basis for reliability, and correctness at run-time. This project intends to investigate formal theories for defining the semantics of behavioural description; and techniques for verifying local/global behaviour at run-time. From a software engineering point of view, the project will consider separating the different concerns: functionality, behavioural description, and interactions.

Approach

In order to make the components adaptable (robust), interoperable, and to ensure correct compositions, we will identify concepts for structuring and designing the components and their interactions. In addition to well-thought concepts, we intend to consider formal techniques as a basis for reliability, and correctness at run-time.

Since there is no central element which pilots the other components, each entity has to be self-sufficient. Therefore, it must incorporate more information than its operational behaviour, and publish more data than its signature. What we want at the end is to be able to program a component with a functional part (traditional behaviour), and a non-functional part describing all the necessary semantical information enabling composition and correct compositional behaviour. The idea is to program seperately, for each component, a functional part implementing the behaviour of the component - the traditional program code; and an abstract description of the component's behaviour - the semantical behavioural description (specification);

These two information are intended to be publicly available at run-time by other components. This extra information (description and correctness) is the glue, embedded in the component, and used to combine the components at run-time. It provides to other components, the necessary meaningful representation of the current component, which will allow run-time discovery of components and correct composition.

Current realisations:

A middleware for dynamic evolution of code (LuckyJ).

The LuckyJ environment, allows client programs to specify and locate services based on properties that clients specify. In addition, the services can be upgraded during execution without halting or provoking an error in the client program. This run-time environment acts as a middleware layer that allows programs to deposit a specification of their behaviour at run-time, and specifications that describe a service required. This is an important feature of self-organising applications since the application transparently adapts to new (or updated) services introduced into the environment. This environment currently only allows the description of basic specification relying on an ontology shared among all the participating services.
Specification carrying code as a basic interaction mechanism.

Entities carry a specification of the functional as well as non-functional capabilities they offer to the community, and a proof that their specification is correct. The specification is expressed using a specification language, e.g., a higher-order logical language, it defines a theory comprised of: functions, axioms and theorems, conveying the semantical part of the specification. Before interacting with a requesting entity, a principal may prove (through run-time proof checking) some of its own theorem on the submitted theory. This allows a principal to interact with another principal only if it can prove that the way it intends to work corresponds to what is expected. The important thing to note here is that entities do not share any common API related to the offered/requested service.
A flexible modular architecture for autonomous systems interacting through specifications.

This architecture, derived from LuckyJ (see above), allows entities to carry specifications expressed using different kinds of specification language, to perform the corresponding matching, and method calls. This architecture implements simple primitives for an entity to register its specifications, or for requesting a service, and for the environment to execute the corresponding requested code once it has been found. The underlying model is modular enough to allow easy integration of new specification languages.
A prototype including specifications expressed either in Prolog, or as regular expressions.
The above architecture currently allows specifications written in Prolog, or as regular expressions. In the case of Prolog, the middleware calls SWI Prolog tool to decide about the conformance of two specifications, in the case of regular expressions we have implemented a tool that checks two regular expressions, and is able to transform them into Java code.
A preliminary set of tools for managing specifications, and codes.
This set of tools helps: 1. to specify correct specifications in Prolog or as regular expressions (Regex), 2. to test whether the specification will correctly match a request or an announced specification and to transform them into XML files (SpecEditor); 3. to manually handle addition and removal of entities from the system (useful for testing and debugging).
MiniVM.
In order to minimises the basic execution layer that needs to be run on all devices participating in an self-organising application, we have implemented a "mini" Java virtual machine where common program services such as compilation, class loading and garbage collection are extracted and run as services that client programs locate and exploit in a self-organising fashion. In addition, this VM allows core services to evolve as easily as middleware services. The MiniVM is based on the Lana programming model and is implemented using the Joeq virtual machine. In a first stage, the compiler and class loader were extracted from the Joeq code base, the compiler was modified to generate address neutral code, and a linker layer was added to replace the relocatable addresses in the code image with fixed addresses. The Lana object-oriented programming model is added on top of this. The Lana model suits well self-organising applications, since it contains a discovery layer that allows programs to locate devices in their vicinity, and to announce and locate services using a message board that each device carries. In addition, communication between programs is secure and asynchronous. When a method call is made, a security key is generated for the caller that allows it to asynchronously detect a reply to the call, even if a network disconnection occurs during the method execution. The MiniVM approach allows programs to search their network for required services, and to simplify the environment so that all programs can share basic services such as compilation and garbage collection.

Ongoing Work

Integration of new specification languages: HOL and Isabelle theorem checker, JENA, and the Common Simple Logic (CSL)
A prototype working in combination with a positioning system.

Papers

G. Di Marzo Serugendo: "Trust as an Interaction Mechanism for Self-Organising Systems", In International Conference on Complex Systems (ICCS'04), May 2004.
C. Razafimahefa and C. Bryce. "A MiniVM for the Dynamic Computer Environments". Technical Report, Object Systems Group, University of Geneva, 2004.
M. Oriol, G. Di Marzo Serugendo, "A Disconnected Service Architecture for Unanticipated Run-time Evolution of Code", IEE Proceedings-Software, Special Issue on Unanticipated Software Evolution, Susan Eisenbach (Ed), 2004.
"Engineering Self-Organising Systems: Nature-Inspired Approaches to Software Engineering". G. Di Marzo Serugendo, A. Karageorgos, O. F. Rana, F. Zambonelli (Eds), LNAI 2977, Springer-Verlag, 2004.
G. Di Marzo Serugendo, N.Foukia, S. Hassas, A.Karageorgos, S. Kouadri Mostéfaoui, O. F. Rana, M. Ulieru, P. Valckenaers, C.Van Aart, "Self-Organising Applications: Paradigms and Applications", in Engineering Self-Organising Systems: Nature-Inspired Approaches to Software Engineering, G. Di Marzo Serugendo, A. Karageorgos, O. F. Rana, F. Zambonelli (Eds), LNAI 2977, Springer-Verlag, 2004.
G. Di Marzo Serugendo, "Engineering Emergent Behaviour: A Vision", Invited Talk. Multi-Agent-Based Simulation III. 4th International Workshop, MABS 2003 Melbourne, Australia, July 2003, Revised Papers. D. Hales, B. Edmonds, E. Norling, J. Rouchier (Eds), LNAI 2927, Springer-Verlag, 2003.

PhD Thesis

M. Oriol: "An Approach to the Dynamic Evolution of Software Systems". PhD in Information Sysems. Faculty of Economic and Social Sciences, University of Geneva, 2004.
C. Razafimahefa: "A Programming Model and Execution Environment for Autonomous Systems". PhD in Information Systems. Faculty of Economic and Social Sciences, University of Geneva, 2004.

Additional Activities

This project started October 2002 and ends September 2004. See A Social Semantical Infrastructure Supporting Ambient Intelligence for a follow-up.

G. Di Marzo Serugendo
September 2004.