13307472
Direct execution of team specifications in STAPLE
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.
14123026
Distributive and Collective Readings in Group Protocols
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.
17321819
Toward A Formalism for Conversation Protocols Using Joint Intention Theory
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
14133109
Representing and executing protocols as joint actions
Families of conversation protocols can be expressed formally as partially ordered landmarks where the landmarks represent the state of affairs that must be brought about during the goal-directed execution of a protocol. Then, concrete protocols represented as joint action expressions can be derived from the partially ordered landmarks and executed directly by joint intention interpreters, thus nearly eliminating the need to implement a separate protocol handling system. This approach also supports (1) flexibility in the actions used to achieve landmarks, (2) shortcutting protocol execution, and (3) application of the joint intention theory to provide automatic exception handling along with a correctness criterion for protocols.
127631
Semantics of Agent Communication Languages for Group Interaction
Group communication is the core of societal interactions. Therefore, artificial agents should be able 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. We give semantics for group communication that we believe can profitably enrich the agent communication languages. In our semantics, individual communication is a special case of group communication wherein each communicating group consists of a single agent.
34159357
A P1500 compliant programmable BistShell for embedded memories
We describe the design and implementation of an IEEE P1500 compliant programmable BIST for embedded memories. The proposed design can be embedded in other cores or systems with minimum test generation or test application overhead. The programmability of our BIST is useful when the algorithm is being refined while the memory architecture is under production. A variety of test algorithms can be implemented with the programmability provided in our design with no change to the BIST hardware. As an example we demonstrate the implementation of an algorithm to detect open decoder faults. This example is shown for its didactic content as it brings out the programmable axis of our design. Our design also offers means to perform dedicated delay tests as well as scan tests for diagnosis. We show by synthesis experiments that the extra area cost for the BIST hardware is relatively small for medium to large memories.
6010311
MEGA3: Integrated software for Molecular Evolutionary Genetics Analysis and sequence alignment
With its theoretical basis firmly established in molecular evolutionary and population genetics, the comparative DNA and protein sequence analysis plays a central role in reconstructing the evolutionary histories of species and multigene families, estimating rates of molecular evolution, and inferring the nature and extent of selective forces shaping the evolution of genes and genomes. The scope of these investigations has now expanded greatly owing to the development of high-throughput sequencing techniques and novel statistical and computational methods. These methods require easy-to-use computer programs. One such effort has been to produce Molecular Evolutionary Genetics Analysis (MEGA) software, with its focus on facilitating the exploration and analysis of the DNA and protein sequence variation from an evolutionary perspective. Currently in its third major release, MEGA3 contains facilities for automatic and manual sequence alignment, web-based mining of databases, inference of the phylogenetic trees, estimation of evolutionary distances and testing evolutionary hypotheses. This paper provides an overview of the statistical methods, computational tools, and visual exploration modules for data input and the results obtainable in MEGA.
5423499
On k-coverage in a mostly sleeping sensor network
Sensor networks are often desired to last many times longer than the active lifetime of individual sensors. This is usually achieved by putting sensors to sleep for most of their lifetime. On the other hand, surveillance kind of applications require guaranteed k-coverage of the protected region at all times. As a result, determining the appropriate number of sensors to deploy that achieves both goals simultaneously becomes a challenging problem. In this paper, we consider three kinds of deployments for a sensor network on a unit square - a √n x √n grid, random uniform (for all n points), and Poisson (with density n). In all three deployments, each sensor is active with probability p, independently from the others. Then, we claim that the critical value of the function npπr2/log(np) is 1 for the event of k-coverage of every point. We also provide an upper bound on the window of this phase transition. Although the conditions for the three deployments are similar, we obtain sharper bounds for the random deployments than the grid deployment, which occurs due to the boundary condition. In this paper, we also provide corrections to previously published results for the grid deployment model. Finally, we use simulation to show the usefulness of our analysis in real deployment scenarios.
14007083
A Malleable-Job System for Timeshared Parallel Machines
Malleable jobs are parallel programs that can change the number of processors on which they are executing at run time in response to an external command. One of the advantages of such jobs is that a job scheduler for malleable jobs can provide improved system utilization and average response time over a scheduler for traditional jobs. In this paper, we present a programming system for creating malleable jobs that is more general than other current malleable systems. In particular, it is not limited to the master-worker paradigm or the Fortran SPMD programming model, but can also support general purpose parallel programs including those written in MPI and Charm++, and has built-in migration and load-balancing, among other features.
8973422
ESP: a language for programmable devices
This paper presents the design and implementation of Event-driven State-machines Programming (ESP)—a language for programmable devices. In traditional languages, like C, using event-driven state-machine forces a tradeoff that requires giving up ease of development and reliability to achieve high performance. ESP is designed to provide all of these three properties simultaneously.
ESP provides a comprehensive set of features to support development of compact and modular programs. The ESP compiler compiles the programs into two targets—a C file that can be used to generate efficient firmware for the device; and a specification that can be used by a verifier like SPlN to extensively test the firmware.
As a case study, we reimplemented VMMC firmware that runs on Myrinet network interface cards using ESP. We found that ESP simplifies the task of programming with event-driven state machines. It required an order of magnitude fewer lines of code than the previous implementation. We also found that model-checking verifiers like SPIN can be used to effectively debug the firmware. Finally, our measurements indicate that the performance overhead of using ESP is relatively small.