A Study of Building Internet Marketplaces on the Basis of Mobile Agents for Parallel Processing

In this paper, we propose a framework of Internet marketplaces on the basis of mobile agents. It not only simulates real commercial activities by consumers, agents and merchants, but also provides an environment for parallel processing. The latter is particularly important as more shops (sites) can be searched in real time to provide consumers with better choices. Meanwhile, if the number of mobile agents is very large and the dispatch is processed in a serial way, it can become a bottleneck that impacts the efficiency as a whole. In this paper, we also present and discuss several hierarchical dispatch models where the dispatch of multiple mobile agents can be processed in parallel over different hosts. We study these models analytically and empirically. The conducted experiments show that, in comparison with several serial mobile agent models, parallel mobile agent models can improve the performance significantly. In addition, in the best case for the parallel dispatch model, the time complexity for dispatching n mobile agents is O(log₂ n).     

Contiguous Search Problem in Sierpiński Graphs

In this paper we consider the problem of capturing an intruder in a particular fractal graph, the Sierpiński graph SG _n . The problem consists of having a team of mobile software agents that collaborate in order to capture the intruder. The intruder is a mobile entity that escapes from the team of agents, moving arbitrarily fast inside the network, i.e., traversing any number of contiguous nodes as long as no other agent resides on them. The agents move asynchronously and they know the network topology they are in is a Sierpiński graph SG _n . We first derive lower bounds on the minimum number of agents, number of moves and time steps required to capture the intruder. We then consider some variations of the model based on the capabilities of the agents: visibility, where the agents can “see” the state of their neighbors and thus can move autonomously; locality, where the agents can only access local information and thus their moves have to be coordinated by a leader. For each model, we design a capturing strategy and we make some observations. One of our goals is to continue a previous study on what is the impact of visibility on complexity: in this topology we are able to reach an optimal bound on the number of agents required by both cleaning strategies. However, the strategy in the visibility model is fully distributed, whereas the other strategy requires a leader. Moreover, the second strategy requires a higher number of moves and time steps. A preliminary version of this paper has been presented at the 4th International Conference on Fun with Algorithms (FUN’07) 17.     

Searching for a black hole in arbitrary networks: optimal mobile agents protocols

Consider a networked environment, supporting mobile agents, where there is a black hole: a harmful host that disposes of visiting agents upon their arrival, leaving no observable trace of such a destruction. The black hole search problem is the one of assembling a team of asynchronous mobile agents, executing the same protocol and communicating by means of whiteboards, to successfully identify the location of the black hole; we are concerned with solutions that are generic (i.e., topology-independent). We establish tight bounds on the size of the team (i.e., the number of agents), and the cost (i.e., the number of moves) of a size-optimal solution protocol. These bounds depend on the a priori knowledge the agents have about the network, and on the consistency of the local labelings. In particular, we prove that: with topological ignorance Δ+1 agents are needed and suffice, and the cost is Θ(n ²), where Δ is the maximal degree of a node and n is the number of nodes in the network; with topological ignorance but in presence of sense of direction only two agents suffice and the cost is Θ(n ²); and with complete topological knowledge only two agents suffice and the cost is Θ(n log n). All the upper-bound proofs are constructive.A preliminary version of this paper appeared in the Proceedings of the 21st ACM Symposium on Principles of Distributed Computing [21].     

Stochastic Ambient Calculus

Mobile Ambients (MA) have acquired a fundamental role in modelling mobility in systems with mobile code and mobile devices, and in computation over administrative domains. We present the stochastic version of Mobile Ambients, called Stochastic Mobile Ambients (SMA), where we extend MA with time and probabilities. Inspired by previous models, PEPA and Sπ, we enhance the prefix of the capabilities with a rate and the ambient with a linear function that operates on the rates of processes executing inside it. The linear functions associated with ambients represent the delays that govern particular administrative domains. We derive performance measures from the labelled transition semantics as in standard models. We also define a strong Markov bisimulation in the style of reduction semantics known as barbed bisimulation. We argue that performance measures are of vital importance in designing any kind of distributed system, and that SMA can be useful in the design of the complicated mobile systems.     

Multi-agent Physical A* with Large Pheromones

Physical A* (PHA*) and its multi-agent version MAPHA* are algorithms that find the shortest path between two points in an unknown real physical environment with one or many mobile agents [A. Felner et al. Journal of Artificial Intelligence Research, 21:631–679, 2004; A. Felner et al. Proceedings of the First International Joint Conference on Autonomous Agents and Multi-Agent Systems, Bologna, Italy, 2002:240–247]. Previous work assumed a complete sharing of knowledge between agents. Here we apply this algorithm to a more restricted model of communication which we call large pheromones, where agents communicate by writing and reading data at nodes of the graph that constitutes their environment. Previous works on pheromones usually assumed that only a limited amount of data can be written at each node. The large pheromones model assumes no limitation on the size of the pheromones and thus each agent can write its entire knowledge at a node. We show that with this model of communication the behavior of a multi-agent system is almost as good as with complete knowledge sharing. Under this model we also introduce a new type of agent, a communication agent, that is responsible for spreading the knowledge among other agents by moving around the graph and copying pheromones. Experimental results show that the contribution of communication agents is rather limited as data is already spread to other agents very well with large pheromones     

How to meet when you forget: log-space rendezvous in arbitrary graphs

Two identical (anonymous) mobile agents start from arbitrary nodes in an a priori unknown graph and move synchronously from node to node with the goal of meeting. This rendezvous problem has been thoroughly studied, both for anonymous and for labeled agents, along with another basic task, that of exploring graphs by mobile agents. The rendezvous problem is known to be not easier than graph exploration. A well-known recent result on exploration, due to Reingold, states that deterministic exploration of arbitrary graphs can be performed in log-space, i.e., using an agent equipped with O(log n) bits of memory, where n is the size of the graph. In this paper we study the size of memory of mobile agents that permits us to solve the rendezvous problem deterministically. Our main result establishes the minimum size of the memory of anonymous agents that guarantees deterministic rendezvous when it is feasible. We show that this minimum size is Θ(log n), where n is the size of the graph, regardless of the delay between the starting times of the agents. More precisely, we construct identical agents equipped with Θ(log n) memory bits that solve the rendezvous problem in all graphs with at most n nodes, if they start with any delay τ, and we prove a matching lower bound Ω(log n) on the number of memory bits needed to accomplish rendezvous, even for simultaneous start. In fact, this lower bound is achieved already on the class of rings. This shows a significant contrast between rendezvous and exploration: e.g., while exploration of rings (without stopping) can be done using constant memory, rendezvous, even with simultaneous start, requires logarithmic memory. As a by-product of our techniques introduced to obtain log-space rendezvous we get the first algorithm to find a quotient graph of a given unlabeled graph in polynomial time, by means of a mobile agent moving around the graph.     

Cost Comparison of Alternative Architectures for IP-over-Optical Core Networks

We explore alternative architectures to reduce cost of IP-over-optical core networks. We conducted a detailed cost study of three architectures. We start with a Baseline architecture that captures present mode of operations with future traffic projections and utilizes technologies such as Ethernet line-cards and OTN sub-wavelength switching. The next architecture, Streamlined, replaces the hub-and-spoke topology of Baseline with a flat topology and is also more judicious in its restoration design. Our detailed study shows significant cost savings for the Streamlined architecture compared to the Baseline. We reduce the cost further in our third proposed architecture: Ethernet enabled IP core consisting of OTN switches (with and without packet switching) and without any backbone routers or MPLS switches. Our results also demonstrate that we can achieve significant reduction in switching costs but reducing cost of transport remains a significant challenge. This paper is an extended version of our previous work published in (11th international conference on the design of reliable communication networks (DRCN), pp 227–234, 2015).     

Minimalism Distribution Supermodularity

We have designed and implemented multi-agent strategies for manipulation tasks by distributing mechanically-based sequential algorithms across several autonomous spatially-separated agents, such as mobile robots. Our experience using mobile robots for the manipulation of large objects (couches, boxes, file cabinets, etc.) leads us to recommend a minimalist architecture for multi-agent programming. In particular, our methodology has led us to derive asynchronous distributed strategies that require no direct communication between agents, and very sparse geometric and dynamic models of the objects our robots manipulate. We argue for a design principle called supermodularity, which is orthogonal both to the notion of modularity in cognitive AI and also to horizontal decomposition (the non-modularity advocated in the subsumption/connectionist literature.) Finally, we discuss a simple mobotscheme infrastructure to implement supermodular architectures. In the past few years we have programmed many supermodular manipulation protocols and tested them extensively on our team of mobile robots. We describe why we think the supermodular infrastructure results in robust, simple, readable, manipulation strategies that can be recycled and reused.     

Location and Configuration Management in Mobile-Switch ATM Networks

The features of two important application scenarios, supporting mobile switches with fixed end users and mobile switches with mobile users, are dramatically different from those of the traditional wired network structure. To exploit mobile switches, the location and configuration management of mobile switches is essential to handle the mobility and topology change of the wireless/mobile ATM network. In this paper we address the location management and configuration problems of mobile switches in an ATM network. We investigate several aspects of the location management problem including architecture to support switch mobility, mobile switch tracking, and mobile switch locating. We propose an approach that is based on the Private Network-Network Interface (PNNI) protocol. We extend the PNNI protocol to enable it to handle mobile switches. Moreover, we develop analytical models to determine the tracking and locating costs for mobile switches under the proposed scheme. The models illustrate the relation between total cost (tracking cost + locating cost) and peer group size. The models can be used to derive the optimal configuration for an ATM network with mobile switches.     

Performance analysis of a mobile agent prototype system based on VIRGO P2P protocols

The mobile agent technique has been broadly used in next generation distributed systems. The system performance measurement and simulation are required before the system can be deployed on a large scale. In this paper, we address performance analysis on a finite state mobile agent prototype on the basis of Virtual Hierarchical Tree Grid Organizations (VIRGO). The finite states refer to the migration, execution, and searching of the mobile agent. We introduce a novel evaluation model for the finite state mobile agent. The experimental results based on this evaluation model show that the finite mobile agents can perform well under multiple agent conditions and are superior to the traditional client/server approach. Copyright © 2013 John Wiley & Sons, Ltd.     

Computation in networks of passively mobile finite-state sensors

The computational power of networks of small resource-limited mobile agents is explored. Two new models of computation based on pairwise interactions of finite-state agents in populations of finite but unbounded size are defined. With a fairness condition on interactions, the concept of stable computation of a function or predicate is defined. Protocols are given that stably compute any predicate in the class definable by formulas of Presburger arithmetic, which includes Boolean combinations of threshold-k, majority, and equivalence modulo m. All stably computable predicates are shown to be in NL. Assuming uniform random sampling of interacting pairs yields the model of conjugating automata. Any counter machine with O(1) counters of capacity O(n) can be simulated with high probability by a conjugating automaton in a population of size n. All predicates computable with high probability in this model are shown to be in P; they can also be computed by a randomized logspace machine in exponential time. Several open problems and promising future directions are discussed. Supported in part by NSF grants CCR-9820888, CCR-0098078, and CNS-0305258 (Aspnes), by ONR grant N00014-01-1-0795 (Diamadi), and by NSF grant CSE-0081823 (Fischer and Peralta). A preliminary version of this paper appeared in the proceedings of the 23rd ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, St. John’s, Newfoundland, Canada, July 2004.     

How to Prove Impossibility Under Global Fairness: On Space Complexity of Self-Stabilizing Leader Election on a Population Protocol Model

A population protocol is one of distributed computing models for passively-mobile systems, where a number of agents change their states by pairwise interactions between two agents. In this paper, we investigate the solvability of the self-stabilizing leader election in population protocols without any kind of oracles. We identify the necessary and sufficient conditions to solve the self-stabilizing leader election in population protocols from the aspects of local memory complexity and fairness assumptions. This paper shows that under the assumption of global fairness, no protocol using only n−1 states can solve the self-stabilizing leader election in complete interaction graphs, where n is the number of agents in the system. To prove this impossibility, we introduce a novel proof technique, called closed-set argument. In addition, we propose a self-stabilizing leader election protocol using n states that works even under the unfairness assumption. This protocol requires the exact knowledge about the number of agents in the system. We also show that such knowledge is necessary to construct any self-stabilizing leader election protocol.     

Modeling the Exogenous Coordination of Mobile Channel-based Systems with Petri Nets

In this paper, we discuss how to model systems that communicate through and are coordinated by mobile channels. Mainly, we focus on modeling the exogenous coordination behavior imposed by these channels. We use Petri Nets as our modeling language, for they provide a graphically and mathematically founded modeling formalism. We give Petri Nets for a set of mobile channel types. This allows us to construct models of applications, by taking the Petri Net of each component and each mobile channel, and composing them together. For this purpose, we define a special Petri Net composition function. We also discuss analysis and simulation of these models and their exogenous coordination behavior.     

Belief Fusion: Aggregating Pedigreed Belief States

We introduce a new operator – belief fusion– which aggregates the beliefs of two agents, each informed by a subset of sources ranked by reliability. In the process we definepedigreed belief states, which enrich standard belief states with the source of each piece of information. We note that the fusion operator satisfies the invariants of idempotence, associativity, and commutativity. As a result, it can be iterated without difficulty. We also define belief diffusion; whereas fusion generally produces a belief state with more information than is possessed by either of its two arguments, diffusion produces a state with less information. Fusion and diffusion are symmetric operators, and together define a distributive lattice. Finally, we show that AGM revision can be viewed as fusion between a novice and an expert. This revised version was published online in August 2006 with corrections to the Cover Date.     

Beyond ‘mobility’: A new understanding of moving with technology

We report a surprising experience with mobile technology: the lead author found herself seeing and acting differently while running over part of her usual running track with the exercise‐tracking application ‘Strava’ on her phone, even without focal attention to the app. We apply the method of problematization to a detailed empirical account of this experience, in conjunction with a literature analysis of taken‐for‐granted assumptions underpinning research on ‘mobile technology use’. This reveals that, while the relationship of attention, perception, movement and technology was a key element of the surprise, these themes are not well accounted for in current IS literature. In response, we employ William Gibson's ecological theory of visual perception to reinterpret the empirical account and thereby build a new understanding of the human plus mobile technology that we term moving‐with‐technology. We introduce to IS: moving‐with‐technology as a new analytical perspective; the new phenomena of digital sub‐species, digital‐niches and asynchronous co‐location; and stimulus for new ecologically oriented ‘mobile methods’. Moving‐with‐technology also has practical implications for urban planners who are using data from digital trace‐making tools such as Strava in their decision‐making, thereby generating what we call ecological feedback loops.     

Introduction to mobile agents

This article will lead you into the world of mobile agents, an emerging technology that makes it much easier to design, implement and maintain distributed systems. You will find that mobile agents reduce network traffic and provide an effective means of overcoming network latency. Perhaps most important, through their ability to operate asynchronously and independently of the process that created them, they help you to construct highly robust and fault-tolerant systems thereby directly or indirectly benefiting the end user.Read on and let us introduce you to software agents, including mobile as well as stationary agents. We will explain the benefits of mobile agents and demonstrate the impact they have on the design of distributed systems. This article then concludes with a brief overview of some contemporary mobile agent systems.This article is based on a chapter of a book by the authors entitledProgramming and Deploying Java ^TM Mobile Agents with Aglets ^TM, ISBN 0-201-32582-9, Addison-Wesley, 1998.     

Coding Mobile Synchronizing Petri Nets into Rewriting Logic

Mobile Synchronizing Petri Nets (MSPN's) are a model for mobility and coordination based on coloured Petri Nets, in which systems are composed of a collection of (possibly mobile) hardware devices and mobile agents, both modelled homogenously. In this paper we approach their verification, for which we have chosen to code MSPN's into rewriting logic. In order to obtain a representation of MSPN systems by means of a rewrite theory, we develop a class of them, that we call ν-Abstract Petri nets (ν-APN's), which are easily representable in that framework. Moreover, the obtained representation provides a local mechanism for fresh name generation. Then we prove that, even if ν-APN's are a particular class of MSPN systems, they are strong enough to capture the behaviour of any MSPN system. We have chosen Maude to implement ν-APN's, as well as the translation from MSPN's to ν-APN's, for which we make intensive use of its reflective features.     

Spanning-tree based coverage of continuous areas by a mobile robot

This paper considers the problem of covering a continuous planar area by a square-shaped tool attached to a mobile robot. Using a tool-based approximation of the work-area, we present an algorithm that covers every point of the approximate area for tasks such as floor cleaning, lawn mowing, and field demining. The algorithm, called Spanning Tree Covering (STC), subdivides the work-area into disjoint cells corresponding to the square-shaped tool, then follows a spanning tree of the graph induced by the cells, while covering every point precisely once. We present and analyze three versions of the STC algorithm. The first version is off-line, where the robot has perfect apriori knowledge of its environment. The off-line STC algorithm computes an optimal covering path in linear time O(N), where N is the number of cells comprising the approximate area. The second version of STC is on-line, where the robot uses its sensors to detect obstacles and construct a spanning tree of the environment while covering the work-area. The on-line STC algorithm completes an optimal covering path in time O(N), but requires O(N) memory for its implementation. The third version of STC is “ant”-like. In this version, too, the robot has no apriori knowledge of the environment, but it may leave pheromone-like markers during the coverage process. The ant-like STC algorithm runs in time O(N), and requires only O(1) memory. Finally we present simulation results of the three STC algorithms, demonstrating their effectiveness in cases where the tool size is significantly smaller than the work-area characteristic dimension. This revised version was published online in August 2006 with corrections to the Cover Date.     

On the Expressiveness of Movement in Pure Mobile Ambients

Pure Mobile Ambients (i.e., Mobile Ambients without communication) provides three mobility primitives: in and out for ambient movement, and open to dissolve ambient boundaries. In this paper we consider the expressiveness of the primitives in and out for ambient movement; more precisely, we concentrate on the interplay between ambient movement and the ability to create new names (exploiting the restriction operator). To this aim, we consider a version of Pure Mobile Ambients (with explicit recursive definitions instead of replication) and we concentrate on the three fragments of the calculus that can be obtained removing either one or both between movement and the ability to create new names. The unique mobility primitive that we retain in all of the considered calculi is open. Te three fragments are denoted as follows: MA^−mv without ambient movement, MA_−v without restriction, and MA^−mv_−v without both movement and restriction. We prove that both the fragments MA^−mv and MA_−v are Turing-complete, while this is not the case for MA^−mv_−v. Indeed, we prove that in this latter calculus the existence of an infinite computation turns to be a decidable property.