The shadow approach: An orphan detection protocol for mobile agents

Joachim Baumann, Kurt RothermelLecture Notes in Computer Science 1998 · DOI · OpenAlex

Introduction

In the late 1990s, the "mobile agent" paradigm emerged as a powerful way to distribute computation. Mobile agents are autonomous programs capable of migrating between network nodes to perform tasks locally. However, this autonomy introduces the problem of orphans: agents that continue to consume resources (CPU, memory, bandwidth) after their results are no longer needed or their parent application has crashed. Detecting these "zombie" agents is challenging because they lack a fixed location or a persistent connection to their creator.

The Shadow Protocol

To address the orphan problem, the authors propose the Shadow Approach. This protocol enforces a mandatory relationship between every mobile agent and a persistent data structure called a "shadow."

Agent and Shadow Creation

When an application initiates a mobile agent, the system simultaneously creates a shadow on a stable node. This shadow serves as the "source of truth" for the agent's status and location.

Creation of an agent and its corresponding shadow by an application.

Termination Mechanisms

The protocol employs two primary methods for orphan detection and termination:

  1. Passive Termination (TTL): Every agent is assigned a Time-to-Live (TTL). To remain active, the agent must periodically check in with its shadow. If the shadow has been deleted by the user or the check-in fails, the agent terminates itself. To prevent agents from circumventing this by spawning children, any new agent inherits only the remaining TTL of its parent.
  2. Active Termination (Proxy Paths): When a user cancels a task, the system can actively "hunt" the agent. As an agent migrates, it leaves behind a trail of "agent proxies." These proxies form a path from the shadow to the agent's current location, allowing for immediate termination signals.
The proxy path connecting a shadow to a mobile agent across multiple places.

Key Insights

  • Artificial Tethers: By imposing a mandatory anchor (the shadow), the system restores the hierarchy lost during agent migration.
  • Path Optimization: The protocol includes logic to detect and remove circular proxy paths. If an agent returns to a previously visited node, the path is shortened to reduce messaging overhead.
  • Location Transparency: While the agent moves, its identifier remains constant, and the shadow maintains the necessary routing information to reach it.

Implementation and Results

The Shadow Protocol was implemented and validated within the Mole agent system at the University of Stuttgart. The primary contribution is a theoretical framework that guarantees orphan termination within a strict worst-case time bound (the agent's TTL plus network timeout).

While the protocol is robust against short-term network partitions, it faces challenges with long-term node failures that break the proxy path. Future work suggests using shadow replication to enhance resilience against the failure of the shadow's host node itself.

Summary updated

BibTeX
@inproceedings{baumann1998shadow,
  author = {Joachim Baumann and Kurt Rothermel},
  title = {{The shadow approach: An orphan detection protocol for mobile agents}},
  booktitle = {Lecture Notes in Computer Science},
  year = {1998},
  doi = {10.1007/bfb0057644},
}
Figure