Mechanisms for environments in multi-agent systems: Survey and opportunities <s> Overlay networks <s> Hash tables - which map "keys" onto "values" - are an essential building block in modern software systems. We believe a similar functionality would be equally valuable to large distributed systems. In this paper, we introduce the concept of a Content-Addressable Network (CAN) as a distributed infrastructure that provides hash table-like functionality on Internet-like scales. The CAN is scalable, fault-tolerant and completely self-organizing, and we demonstrate its scalability, robustness and low-latency properties through simulation. <s> BIB001 </s> Mechanisms for environments in multi-agent systems: Survey and opportunities <s> Overlay networks <s> This paper presents the design and evaluation of Pastry, a scalable, distributed object location and routing substrate for wide-area peer-to-peer ap- plications. Pastry performs application-level routing and object location in a po- tentially very large overlay network of nodes connected via the Internet. It can be used to support a variety of peer-to-peer applications, including global data storage, data sharing, group communication and naming. Each node in the Pastry network has a unique identifier (nodeId). When presented with a message and a key, a Pastry node efficiently routes the message to the node with a nodeId that is numerically closest to the key, among all currently live Pastry nodes. Each Pastry node keeps track of its immediate neighbors in the nodeId space, and notifies applications of new node arrivals, node failures and recoveries. Pastry takes into account network locality; it seeks to minimize the distance messages travel, according to a to scalar proximity metric like the number of IP routing hops. Pastry is completely decentralized, scalable, and self-organizing; it automatically adapts to the arrival, departure and failure of nodes. Experimental results obtained with a prototype implementation on an emulated network of up to 100,000 nodes confirm Pastry's scalability and efficiency, its ability to self-organize and adapt to node failures, and its good network locality properties. <s> BIB002 </s> Mechanisms for environments in multi-agent systems: Survey and opportunities <s> Overlay networks <s> Making effective use of the vast amounts of data gathered by large-scale sensor networks will require scalable, self-organizing, and energy-efficient data dissemination algorithms. Previous work has identified data-centric routing as one such method. In an asso-ciated position paper [23], we argue that a companion method, data-centric storage (DCS), is also a useful approach. Under DCS, sensed data are stored at a node determined by the name associated with the sensed data. In this paper, we describe GHT, a Geographic Hash Table system for DCS on sensornets. GHT hashes keys into geographic coordi-nates, and stores a key-value pair at the sensor node geographically nearest the hash of its key. The system replicates stored data lo-cally to ensure persistence when nodes fail. It uses an efficient consistency protocol to ensure that key-value pairs are stored at the appropriate nodes after topological changes. And it distributes load throughout the network using a geographic hierarchy. We evaluate the performance of GHT as a DCS system in simulation against two other dissemination approaches. Our results demonstrate that GHT is the preferable approach for the application workloads predicted in [23], offers high data availability, and scales to large sensornet deployments, even when nodes fail or are mobile. <s> BIB003 </s> Mechanisms for environments in multi-agent systems: Survey and opportunities <s> Overlay networks <s> In situated multi-agent systems (situated MASs), agents are explicitly placed in an environment. A situated agent does not not use long-term planning to decide what action sequence should be executed, but selects actions on the basis of its current position, the world it perceives and limited internal state. Situated agents exploit the environment to coordinate their behavior and to reach a common goal. In a recent project, we applied situated MASs to the control of an automated transportation system that uses automatic guided vehicles (AGVs) to transport loads in a warehouse. In contrast to traditional approaches where the AGVs are controlled by a central server, in this project we model the AGVs as agents in a situated MAS, aiming to improve flexibility and openness. Since the physical environment of AGVs is very restricted, it offers little opportunities for agents to use the environment. We introduce a virtual environment for agents to live in. This virtual environment (1) offers a medium that agents can use to exchange information and coordinate their behavior, and (2) serves as a suitable abstraction to shield low-level physical processing from the AGV agents. Since the only infrastructure available to the AGVs is a wireless network, the virtual environment is necessarily distributed over the AGVs. Synchronization of the state of the virtual environment is provided by ObjectPlaces, a middleware infrastructure that offers support to exchange and share information among nodes in mobile and ad-hoc networks. In this paper, we demonstrate how the environment is used creatively in the design of a MAS solution, helping to manage the complexity of engineering a complex real-world application. <s> BIB004
Another important class of interaction mechanism is intended to support interaction networks. It is based on overlay networks that rule and describe relationships among agents. The topology of such a network is built such that agents can interact with one another efficiently. Overlay networks are distributed data structures providing agents with applicationspecific views of their network of acquaintance BIB003 BIB001 BIB002 . This mechanism is not only related to distributed computing, but can be applied to any kind of logically networked MAS. Name: Overlay networks. Motivations: To represent and allow the maintenance of agent relationships. Constituent atoms: Tables representing the physical, interactive, or social surrounding of agents. Creation and maintenance: Protocols to let new agents join and leave the topology, and to deal with reconfigurations. Usage: Agents access the tables to interact with each other efficiently. Examples: Distributed Hash Tables BIB003 BIB001 BIB002 , Social Dependency Nets  The constituent atoms of an overlay network are a set of tables defining a topology (e.g. tables indicate the neighbors of a specific agent, describing an overlay topology). Creation and maintenance is performed by means of specific protocols that adjust the overlay network topology upon connection and disconnections of agents. Their usage consists in agents sending and routing data to each other on the basis of the topology. A first illustration of this mechanism is the Content Addressable Network approach BIB003 BIB001 . Other approaches, like Chord BIB002 , are based on the same principles. The basic idea of the content addressable network is that interactions in MAS are difficult to manage because of the system dynamics (agents connecting, disconnecting, and moving) and because of the unknown and dynamic topology of the network of acquaintance among agents. To overcome these problems, agents are projected in a virtual space with a predictable topology, where interacting is easy and unnecessary details for the application are abstracted. When an agent enters the system, it gets a location in the virtual space (i.e. an address) and a reference to its new neighbors. The location of an agent is not related to the physical network, but to application parameters. So, for example, all agents having similar properties can get located in a specific area of the space. With such a mechanism in place, interaction becomes easy because agents look for specific partners in those areas of the space where they should be located. Another interesting proposal is the agent middleware 'ObjectPlaces' that supports agent coordination in mobile and ad hoc networks BIB004 . ObjectPlaces provides two distinct abstractions for this support. A view is a collection of data gathered from a category of nodes in the network. Views support coordination by information sharing and they keep the data up-to-date if node properties change. For example, an agent can create a view on all nodes within 50 m. The second abstraction is the role, which supports protocol-based coordination. A role encapsulates the behavior of an agent engaging in an interaction protocol. ObjectPlaces allows the execution of protocols by activating roles on network nodes that satisfy common constraints (e.g. to be in the same area), and it changes the role activation (by deallocation and reallocation) whenever a node does not verify the constraints anymore. The advantage of overlay networks is that the environment is built on the basis of application-level needs, and that it is directly accessible by agents to support their interactions. In other words, the environment decouples agents interactions from the underlying physical network and it provides a suitable 'glue' adapted to applicationspecific needs.