Faculté informatique et communications IC, Section des systèmes de communication, Institut d'informatique fondamentale IIF (Laboratoire de systèmes répartis LSR)

Fault-tolerant and transactional mobile agent execution

Pleisch, Stefan ; Schiper, André (Dir.)

Thèse sciences Ecole polytechnique fédérale de Lausanne EPFL : 2002 ; no 2654.

Add to personal list
    Summary
    Mobile agents constitute a computing paradigm of a more general nature than the widely used client/server computing paradigm. A mobile agent is essentially a computer program that acts autonomously on behalf of a user and travels through a network of heterogeneous machines. However, the greater flexibility of the mobile agent paradigm compared to the client/server computing paradigm comes at additional costs. These costs include, among others, the additional complexity of developing and managing mobile agent-based applications. This additional complexity comprises such issues as reliability. Before mobile agent technology can appear at the core of tomorrow's business applications, reliability mechanisms for mobile agents must be established. In this context, fault tolerance and transaction support are mechanisms of considerable importance. Various approaches to fault tolerance and transaction support exist. They have different strengths and weaknesses, and address different environments. Because of this variety, it is often difficult for the application programmer to choose the approach best suited to an application. This thesis introduces a classification of current approaches to fault-tolerant and transactional mobile agent execution. The classification, which focuses on algorithmic aspects, aims at structuring the field of fault-tolerant and transactional mobile agent execution and facilitates an understanding of the properties and weaknesses of particular approaches. In a distributed system, any software or hardware component may be subject to failures. A single failing component (e.g., agent or machine) may prevent the agent from proceeding with its execution. Worse yet, the current state of the agent and even its code may be lost. We say that the agent execution is blocked. For the agent owner, i.e., the person or application that has configured the agent, the agent does not return. To achieve fault-tolerance, the agent owner can try to detect the failure of the agent, and upon such an event launch a new agent. However, this requires the ability to correctly detect the crash of the agent, i.e., to distinguish between a failed agent and an agent that is delayed by slow processors or slow communication links. Unfortunately, this cannot be achieved in systems such as the Internet. An agent owner who tries to detect the failure of the agent thus cannot prevent the case in which the agent is mistakenly assumed to have crashed. In this case, launching a new agent leads to multiple executions of the agent, i.e., to the violation of the desired exactly-once property of agent execution. Although this may be acceptable for certain applications (e.g., applications whose operations do not have side-effects), others clearly forbid it. In this context, launching a new agent is a form of replication. In general, replication prevents blocking, but may lead to multiple executions of the agent, i.e., to a violation of the exactly-once execution property. This thesis presents an approach that ensures the exactly-once execution property using a simple principle: the mobile agent execution is modeled as a sequence of agreement problems. This model leads to an approach based on two well-known building blocks: consensus and reliable broadcast. We validate this approach with the implementation of FATOMAS, a Java-based FAult-TOlerant Mobile Agent System, and measure its overhead. Transactional mobile agents execute the mobile agent as a transaction. Assume, for instance, an agent whose task is to buy an airline ticket, book a hotel room, and rent a car at the flight destination. The agent owner naturally wants all three operations to succeed or none at all. Clearly, the rental car at the destination is of no use if no flight to the destination is available. On the other hand, the airline ticket may be useless if no rental car is available. The mobile agent's operations thus need to execute atomically, i.e., either all of them or none at all. Execution atomicity also needs to be ensured in the event of failures of hardware or software components. The approach presented in this thesis is non-blocking. A non-blocking transactional mobile agent execution has the important advantage that it can make progress despite failures. In a blocking transactional mobile agent execution, by contrast, progress is only possible when the failed component has recovered. Until then, the acquired locks generally cannot be freed. As no other transactional mobile agents can acquire the lock, overall system throughput is dramatically reduced. The present approach reuses the work on fault-tolerant mobile agent execution to prevent blocking. We have implemented the proposed approach and present the evaluation results.
    Résumé
    Récemment, les agents mobiles sont devenus à la mode en tant que paradigme plus général que le traditionel paradigme client/serveur. Un agent mobile est un programme qui agit de façon autonome pour le compte d'un utilisateur et qui traverse un réseau d'ordinateurs hétérogènes. Cependant la plus grande flexibilité du paradigme, comparé au paradigme client/serveur, a un coût. Ce coût comprend entre autres une plus grande complexité du développement et de la gestion des applications. Il faut aussi compter dans cette complexité additionelle l'aspect fiabilité. Avant que la technologie des agents mobiles ne puisse s'installer au coeur des futures applications de business, la fiabilité doit être développée. Parmi ces mécanismes, la tolérance aux fautes et le support transactionnel sont extrêmement importants. Actuellement il existe différentes approches pour la tolérance aux fautes et le support transactionnel, chacune ayant des avantages et des inconvénients, et résolvant des problèmes dans des domaines d'applications différents. À cause de cette variété, il est souvent difficile pour le développeur d'applications de choisir la meilleure approche. Une des contributions de cette thèse est l'introduction d'une classification des approches existantes. Cette classification, qui est centrée sur les aspects algorithmiques, tente de structurer le domaine des agents tolérants aux fautes et transactionnels, et aide à comprendre les avantages et désavantages d'approches particulières. Dans un système distribué n'importe quel composant logiciel ou matériel peut être sujet à une défaillance. Celle-ci (par exemple, celle d'un agent ou d'une machine) peut empêcher l'agent de continuer son exécution ; plus grave encore, l'état actuel de l'agent, et même son code, peuvent être perdus. Nous disons que l'agent est bloqué. Le propriétaire de l'agent, c'est-à-dire la personne ou l'application qui a configuré l'agent, constate que l'agent ne revient pas. Pour être tolérant aux fautes, le propriétaire peut essayer de détecter la défaillance de l'agent, dans le but d'envoyer un nouvel agent. Par contre, ceci nécessite de pouvoir détecter correctement les défaillances d'un agent, et donc de pouvoir faire la distinction entre un agent défaillant et un agent qui aurait été retardé par des processeurs ou des liens de communication lents. Malheureusement, ceci n'est pas possible dans des systèmes tels que l'Internet. Le propriétaire de l'agent qui essaye de détecter la défaillance de son agent ne peut donc pas empêcher le cas où il commettrait une erreur sur l'état de l'agent. Dans ce cas, il risque d'envoyer un nouvel agent, ce qui conduit à des exécutions multiples de l'agent, et donc à une violation de la propriété d'exécution "une et une seule fois" (exactly-once). Bien que ceci puisse être acceptable pour certaines applications, comme par exemple les applications dont les opérations n'ont pas d'effets de bord, ce n'est pas le cas de toutes les applications. Dans ce contexte, l'envoi d'un nouvel agent est une forme de réplication. La réplication empêche les blocages de l'agent, mais peut conduire à des exécutions multiples de l'agent. Cette thèse propose une approche qui assure la propriété d'exécution exactly-once en utilisant un principe simple : l'exécution de l'agent mobile est modélisée comme une séquence de problèmes d'agréments. Ce modèle mène a une approche fondée sur deux blocs de bases : le consensus et la diffusion (multicast) fiable. Notre approche est validée grâce à FATOMAS (FAult-TOlerant Mobile Agent System), un système développé en Java, dont nous évaluons la performance. Les agents mobiles transactionnels s'exécutent comme une transaction. Supposons par exemple qu'un agent doive acheter un ticket d'avion, réserver une chambre d'hôtel et louer une voiture. Le propriétaire de l'agent exige en général que les trois opérations réussissent ou aucune. En effet, louer une voiture n'a pas de sens si aucun vol n'est disponible. Par ailleurs, le ticket d'avion est inutile si aucune voiture ne peut être louée sur place. Les opérations de l'agent mobile doivent donc s'exécuter de facon atomique. L'atomicité de l'exécution doit être garantie même en cas de défaillance de composants logiciels ou matériels. L'approche proposée dans cette thèse est non-bloquante. Une exécution non-bloquante de l'agent transactionnel permet de continuer l'exécution malgré des défaillances. Dans une exécution bloquante, un progrès n'est possible que lorsque le composant défaillant redémarre. Entre temps, les verrous acquis ne peuvent être libérés, et comme aucun autre agent mobile transactionnel ne peut acquérir ces verrous, la performance du système est considérablement réduite. Notre approche est basée sur notre proposition dans le domaine des agents tolérants aux fautes. Nous avons implémenté l'approche proposée, et présentons ses performances.