Towards a fault-tolerant multi-agent system architecture
Multi-agent systems are prone to failures typical of any distributed system. Agents and resources may become unavailable due to machine crashes, communication breakdowns, process failures, and numerous other hardware and software failures. Most of the work done in fault handling in multi-agent systems deals with detection and recovery from faults such as state-inconsistencies, relying on the traditional techniques for recovering from other distributed systems failure. However, the traditional fault-tolerance techniques are designed for specific situations and they require special infrastructural support. We argue for fault-tolerance techniques that can be readily implemented using a generic agent shell with minimal or no modification to the agent infrastructure. We propose that theories from multi-agent systems literature can be effectively combined with basic fault-tolerance principles to design robust multi-agent systems. In particular, we argue that (1) teamwork may be used to create a robust brokered architecture that can recover a multi-agent system from broker failures without incurring undue overheads, (2) teamwork may also be used to guarantee a specified number of brokers in a large multi-agent system, and (3) agent autonomy can be used to prevent thrashing and guarantee acceptable levels of quality of service by an agent. We also describe the Adaptive Agent Architecture (AAA), a fault-tolerant brokered multi-agent system architecture, and present experimental evidence using the AAA to validate our approach.

title: Toward A Formalism for Conversation Protocols Using Joint Intention Theory
abstract: Conversation protocols are meant to achieve certain tasks or to bring about certain state of affairs in the world. Therefore, one may identify the landmarks or the state of affairs that must be brought about during the execution of a protocol in order to achieve its goal. Accordingly, the most important aspect of protocols is these landmarks rather than the communicative actions needed to achieve the landmarks. We show that families of conversation protocols can be expressed formally as partially ordered landmarks where each landmark is characterized by propositions that are true in the state represented by that landmark. Dialogue in natural languages is regarded as joint activity. Conversation protocols in multi-agent systems are treated as dialogue templates and are composed using speech acts from natural language dialogues. As such, we treat conversation protocols as joint action expressions and gainfully apply existing formal theories of dialogue, specifically the Joint Intention Theory, to protocols and their compositions. Conversation protocols may require agents to communicate with groups as well as individuals. However, most contemporary agent communication languages, notably FIPA and KQML, have either no provision or no well-defined semantics for group communication. Furthermore, the research on protocols so far does not correctlymore » incorporate groups into the protocols. We give a formal semantics to group communicative acts and use it to handle group communication in a formal treatment of protocols.« less

title: Distributive and Collective Readings in Group Protocols
abstract: Collaborative applications require protocols that specify how distributed entities interact with one another in order to achieve a specified behavior. Many different kinds of relationships can be established between these entities as a result of such interactions. Distributive and Collective readings are two important ways to characterize group interaction. Starting from an attempt-based semantics of group communicative acts, we distinguish between these two concepts and evaluate group protocols with respect to formation of different types of teams during the interaction.

title: STAPLE: An agent programming language based on the joint intention theory
abstract: Joint intention theory has been used for rule based creation of teams and to provide a formal semantics for communicative acts but there were no agent programming languages linked to this theory. We proposed a declarative agent programming language called STAPLE whose logical semantics is given by the joint intention theory. This paper illustrates the STAPLE support for communication and teamwork in a unified framework.

title: Direct execution of team specifications in STAPLE
abstract: Formal theories of teamwork are typically treated as software design specifications of team behavior. We take a different approach to programming teamwork by directly executing logical specifications of joint commitment and joint intention. This approach leads to a domain-independent framework for programming teamwork where one can modify (or add new) behavior for a team of agents just by modifying (or adding) logical sentences. One may also be able to predict the behavior of an agent team offline using its team intention specification and verify it by running the actual system.

title: Hierarchical Fusion of Multiple Classifiers for Hyperspectral Data Analysis
abstract: Many classification problems involve high dimensional inputs and a large number of classes. Multiclassifier fusion approaches to such difficult problems typically centre around smart feature extraction, input resampling methods, or input space partitioning to exploit modular learning. In this paper, we investigate how partitioning of the output space (i.e. the set of class labels) can be exploited in a multiclassifier fusion framework to simplify such problems and to yield better solutions. Specifically, we introduce a hierarchical technique to recursively decompose a C-class problem into C_1 ) class problems. A generalised modular learning framework is used to partition a set of classes into two disjoint groups called meta-classes. The coupled problems of finding a good partition and of searching for a linear feature extractor that best discriminates the resulting two meta-classes are solved simultaneously at each stage of the recursive algorithm. This results in a binary tree whose leaf nodes represent the original C classes. The proposed hierarchical multiclassifier framework is particularly effective for difficult classification problems involving a moderately large number of classes. The proposed method is illustrated on a problem related to classification of landcover using hyperspectral data: a 12-class AVIRIS subset with 180 bands. For this problem, the classification accuracies obtained were superior to most other techniques developed for hyperspectral classification. Moreover, the class hierarchies that were automatically discovered conformed very well with human domain experts’ opinions, which demonstrates the potential of using such a modular learning approach for discovering domain knowledge automatically from data.

title: Using model checking to debug device firmware
abstract: Device firmware is a piece of concurrent software that achieves high performance at the cost of software complexity. They contain subtle race conditions that make them difficult to debug using traditional debugging techniques. The problem is further compounded by the lack of debugging support on the devices. This is a serious problem because the device firmware is trusted by the operating system.Model checkers are designed to systematically verify properties of concurrent systems. Therefore, model checking is a promising approach to debugging device firmware. However, model checking involves an exponential search. Consequently, the models have to be small to allow effective model checking.This paper describes the abstraction techniques used by the ESP compiler to extract abstract models from device firmware written in ESP. The abstract models are small because they discard some of the details in the firmware that is irrelevant to the particular property being verified. The programmer is required to specify the abstractions to be performed. The ESP compiler uses the abstraction specification to extract models conservatively. Therefore, every bug in the original program will be present in the extracted model.This paper also presents our experience with using Spin model checker to develop and debug VMMC firmware for the Myrinet network interfaces.

title: Design of randomized multichannel packet storage for high performance routers
abstract: High performance routers require substantial amounts of memory to store packets awaiting transmission, requiring the use of dedicated memory devices with the density and capacity to provide the required storage economically. The memory bandwidth required for packet storage subsystems often exceeds the bandwidth of individual memory devices, making it necessary to implement packet storage using multiple memory channels. This raises the question of how to design multichannel storage systems that make effective use of the available memory and memory bandwidth, while forwarding packets at link rate in the presence of arbitrary packet retrieval patterns. A recent series of papers has demonstrated an architecture that uses on-chip SRAM to buffer packets going to/from a multichannel storage system, while maintaining high performance in the presence worst-case traffic patterns. Unfortunately, the amount of on-chip storage required grows as the product of the number of channels and the number of separate queues served by the packet storage system. This makes it too expensive to use in systems with large numbers of queues. We show how to design a practical randomized packet storage system that can sustain high performance using an amount of on-chip storage that is independent of the number of queues.

title: NAMD: Biomolecular Simulation on Thousands of Processors
abstract: NAMD is a fully featured, production molecular dynamics program for high performance simulation of large biomolecular systems. We have previously, at SC2000, presented scaling results for simulations with cutoff electrostatics on up to 2048 processors of the ASCI Red machine, achieved with an object-based hybrid force and spatial decomposition scheme and an aggressive measurement-based predictive load balancing framework. We extend this work by demonstrating similar scaling on the much faster processors of the PSC Lemieux Alpha cluster, and for simulations employing efficient (order N log N) particle mesh Ewald full electrostatics. This unprecedented scalability in a biomolecular simulation code has been attained through latency tolerance, adaptation to multiprocessor nodes, and the direct use of the Quadrics Elan library in place of MPI by the Charm++/Converse parallel runtime system.

title: A hierarchical field framework for unified context-based classification
abstract: We present a two-layer hierarchical formulation to exploit different levels of contextual information in images for robust classification. Each layer is modeled as a conditional field that allows one to capture arbitrary observation-dependent label interactions. The proposed framework has two main advantages. First, it encodes both the short-range interactions (e.g., pixelwise label smoothing) as well as the long-range interactions (e.g., relative configurations of objects or regions) in a tractable manner. Second, the formulation is general enough to be applied to different domains ranging from pixelwise image labeling to contextual object detection. The parameters of the model are learned using a sequential maximum-likelihood approximation. The benefits of the proposed framework are demonstrated on four different datasets and comparison results are presented