In the past two decades, multi-agent systems have emerged as a new paradigm for conceptualizing large and complex distributed software systems. Even though there are many conceptual frameworks for using multi-agent systems, there is no well established and widely accepted method for the representation of multi-agent systems. We adapt a well-known formal model, predicate transition nets, to include the notions of dynamic structure, agent communication and coordination to address the representation problems. This paper presents a comprehensive methodology for modeling multi-agents based on the extensions. We demonstrate our modeling approach with an example. Several case studies on different application domains from our previous works are also discussed.

Mobile objects can be used to gather samples from a sensor field. Civilian vehicles or even human beings equipped with proper wireless communication devices can be used as mobile sinks that retrieve sensor-data from sampling points within a large sensor field. A key challenge is how to gather the sensor data in a manner that is energy efficient with respect to the sensor nodes that serve as sources of the sensor data. In this paper, an algorithmic technique called Band-based Directional Broadcast is introduced to control the direction of broadcasts that originate from sensor nodes. The goal is to direct each broadcast of sensor data toward the mobile sink, thus reducing costly forwarding of sensor data packets. The technique is studied by simulations that consider energy consumption and data deliverability.

This paper describes the design of a decision support system for shill detection in online auctions. To assist decision making, each bidder is associated with a type of certification, namely shill, shill suspect, or trusted bidder, at the end of each auction's bidding cycle. The certification level is determined on the basis of a bidder's bidding behaviors including shilling behaviors and normal bidding behaviors, and thus fraudulent bidders can be identified. In this paper, we focus on representing knowledge about bidders from different aspects in online auctions, and reasoning on bidders' trustworthiness under uncertainties using Dempster–Shafer theory of evidence. To demonstrate the feasibility of our approach, we provide a case study using real auction data from eBay. The analysis results show that our approach can be used to detect shills effectively and efficiently. By applying Dempster–Shafer theory to combine multiple sources of evidence for shill detection, the proposed approach can significantly reduce the number of false positive results in comparison to approaches using a single source of evidence.

Applications that exploit the capabilities of sensor networks have triggered significant research on query processing in sensor systems. Energy constraints make optimizing query processing particularly important. This article addresses multiroot, multiquery optimization for region queries. The work focuses on application-layer issues exploiting query semantics. The article formulates three algorithms: a naïve algorithm, without data sharing, and a static and heuristic data-sharing algorithm. The heuristic algorithm allows sharing of partially aggregated results of preconfigured geographic regions and exploits the location attribute of sensor nodes as a grouping criterion. Simulation studies indicate the potential for significant energy savings with the proposed algorithms.

Multi-agent systems (MASs) have become an important topic in distributed systems research. These distributed multi-agent systems call for special software modeling methods that explicitly support key system properties such as resource constraints and control of conflicts. Although there have been some system modeling techniques to support MASs design and automatic analysis, most state-of-the-art techniques have not distinguished potential conflicts from real conflicts during the design stage. To solve this problem, we define a new concept, called "potential arcs," which is integrated into colored Petri net modeling to support the modeling of MASs. We present a modeling methodology based on the potential arc concept and illustrate the methodology with a case study, including some associated model analysis.

An interplay between mobile devices and static sensor nodes is envisioned in the near future. This will enable a heterogeneous design space that can offset the stringent resource and power constraints encountered in traditional static sensor networks by taking advantage of the more powerful mobile devices. As such, we present a systematic framework for end-to-end query processing, using a two-layer architecture that consists of mobile devices at the upper layer and static sensor nodes at the bottom layer. One of our key goals is to achieve energy-efficient query injection and data collection by leveraging the mobility and transmission flexibility of objects at the upper layer. We propose a pull query model that contains staged operations including query generation, query routing, query injection, and query result routing. In the context of this model, we investigate a suite of techniques for the scenario with location-ignorant sensor nodes.

To facilitate flexible data discovery, sensor networks can be supported by query processing, where a query is injected into the sensor network from some base station. In his paper we consider the problem of query injection by base stations that are mobile (mobile objects) and individual sensors are "location-ignorant". The idea is to have mobile objects take advantage of each other's independent motion plans to do a form of opportunistic query injection. We discuss methods to optimize query injection in terms of optimal injection points and transmission ranges. Numerical simulations on coverage rate metrics are provided to support the proposed methods

Security modeling for agents has been one of the most challenging issues in developing practical mobile agent software systems. In the past, researchers have developed mobile agent systems with emphasis either on protecting mobile agents from malicious hosts or protecting hosts from malicious agents. In this paper, we propose a security based mobile agent system architecture that provides a general solution to protecting both mobile agents and agent hosts in terms of agent communication and agent migration. We present a facilitator agent model that serves as a middleware for secure agent communication and agent migration. The facilitator agent model, as well as the mobile agent model, is based on agent-oriented G-nets — a high level Petri net formalism. To illustrate our formal modeling technique for mobile agent systems, we provide an example of agent migration to show how a design error can be detected.

Agents are becoming one of the most important topics in distributed and autonomous decentralized systems, and there are increasing attempts to use agent technologies to develop large-scale commercial and industrial software systems. The complexity of such systems suggests a pressing need for system modeling techniques to support reliable, maintainable, and extensible design. G-nets are a type of Petri net defined to support system modeling in terms of a set of independent and loosely-coupled modules. In this paper, we customize the basic G-net model to define a so-called "agent-based G-net" that can serve as a generic model for agent design. Then, to progress from an agent-based design model to an agent-oriented model, new mechanisms to support inheritance modeling are introduced. To illustrate our formal modeling technique for multiagent systems, an example of an agent family in electronic commerce is provided. Finally, we demonstrate how we can use model checking to verify some key behavioral properties of our agent model. This is facilitated by the use of an existing Petri net tool.

With the increasing importance of complex software systems in the software industry, the need for using agent technologies to develop large-scale commercial and industrial software systems is growing rapidly. Such systems are complex, and there is a pressing need for system modeling techniques to support reliable, maintainable and extensible design. G-nets are a type of Petri net defined to support the modeling of a system as a set of independent and loosely-coupled modules. In this paper, we first introduce an extension of G-nets - the agent-based G-net - as a generic model for agent design. Then, to progress from an agent-based design model to an agent-oriented model, new mechanisms to support inheritance modeling are introduced. To illustrate our formal modeling technique for multi-agent systems, an example of an agent family in electronic commerce is provided.

Agents are becoming one of the most important topics in distributed and autonomous decentralized systems (ADS), and there are increasing attempts to use agent technologies to develop software systems in electronic commerce. Such systems are complex and there is a pressing need for system modeling techniques to support reliable, maintainable and extensible design. G-Nets are a type of Petri net defined to support modeling of a system as a set of independent and loosely-coupled modules. The authors first introduce an extension of G-Net, agent based G-Net, as a generic model for agent design. Then new communication mechanisms are introduced to support asynchronous message passing among agents. To illustrate that our formal modeling technique is effective for agent modeling in electronic commerce, a price-negotiation protocol example between buyers and sellers is provided. Finally, by analyzing an ordinary Petri net reduced from our agent based G-Net models, we conclude that our agent based G-Net models are L3-live, concurrent and effective for agent communications.

UML, being the industry standard as a common OO modeling language, needs a well-defined semantic base for its notation. Formalization of the graphical notation enables automated processing and analysis tasks. This paper describes a methodology for synthesis of a Petri net model from UML diagrams. The approach is based on deriving Object Net Models from UML statechart diagrams and connecting these object models based on UML collaboration diagram information. The resulting system-level Petri net model can be used as a foundation for formal Petri net analysis and simulation techniques. The methodology is illustrated on some small examples and a larger case study. The case study reveals some unexpected invalid system-state situations.

Abstract Over the last two decades, considerable research has been done in distributed operating systems, which can be attributed to faster processors and better communication technologies. A distributed operating system requires distributed algorithms to provide basic operating system functionality likemutual exclusion,deadlock detection, etc. A number of such algorithms have been proposed in the literature. Traditionally, these distributed algorithms have been presented in a theoretical way, with limited attempts to simulate actual working models. This paper discusses our experience in simulating distributed algorithms with the aid of some existing tools, including OPNET and Xplot. We discuss our efforts to define a basic model‐based framework for rapid simulation and visualization, and illustrate how we used this framework to evaluate some classic algorithms. We have also shown how the performance of different algorithms can be compared based on some collected statistics. To keep the focus of this paper on the approach itself, and our experience with tool integration, we only discuss some relatively simple models. Yet, the approach can be applied to more complex algorithm specifications. Copyright © 2001 John Wiley & Sons, Ltd.

G-nets are a type of Petri net defined to support the modeling of a system as a set of independent and loosely-coupled modules. The modular features of G-nets provide support for incremental design and successive modification, however the G-net formalism is not fully object-oriented due to a lack of support for inheritance. We introduce extensions to G-nets to support explicit modeling of inheritance. Bounded buffer examples are used, which we define as subclasses of an unbounded buffer, to illustrate the expressive power of the extended G-net models. Various forms of inheritance are formalized and discussed in the context of concurrent object-oriented design. In addition, the inheritance anomaly problem is examined and discussed.

This paper presents a method for modeling of communication protocols using G-Nets — an object-based Petri net formalism. Our approach focuses on specification of one entity in one node at one time, with the analysis that allows consideration of other layers and nodes in addition to module analysis. We extend G-Nets by the notion of timers, which aids the construction of protocol software models. Our method prevents some types of potential deadlocks and livelocks from being introduced into the produced net models. We present certain net synthesis rules to prevent some potential design errors by including error cases in the model. Thus, our node (site) interplay modeling includes cases in which a message may arrive corrupted or can be lost entirely before it would get to its destination node. Also, since our models have deadlock-preserving skeletons, the verification of global deadlock non-existence can be performed on the less complex skeleton rather than on the full G-Net model. Our analysis method discovers some deadlocks plus other unacceptable markings, which do not allow restoration of the initial state. Finding potential livelocks or overspecification is also a part of the analysis.

Rethinking the design strategies in implementing RPC based distributed systems offers significant promise. An area where additional RPC functionality is desirable is in the support for the procedural parameter or callback procedure. RPC support for callback procedures is desirable both for smooth development of new distributed applications as well as for distributing the execution of existing sequential programs. The paper analyzes the general problem of supporting callback procedures. The analysis flushes out the design requirements for an RPC implementation to support callbacks and explores potential advantages of implementing general support for callback procedures.

As part of our continuing research on using Petri nets to support automated analysis of Ada tasking behavior, we have investigated the application of Petri net reduction for deadlock analysis. Although reachability analysis is an important method to detect deadlocks, it is in general inefficient or even intractable. Net reduction can aid the analysis by reducing the size of the net while preserving relevant properties. We introduce a number of reduction rules and show how they can be applied to Ada nets, which are automatically generated Petri net models of Ada tasking. We define a reduction process and a method by which a useful description of a detected deadlock state can be obtained from the reduced net's information. A reduction tool and experimental results from applying the reduction process are discussed.

An emerging challenge for software engineering is the development of the methods and tools to aid design and analysis of concurrent and distributed software. Over the past few years, a number of analysis methods that focus on Ada tasking have been developed. Many of these methods are based on some form of reachability analysis, which has the advantage of being conceptually simple, but the disadvantage of being computationally expensive. We explore the effectiveness of various Petri net-based techniques for the automated deadlock analysis of Ada programs. Our experiments consider a variety of state space reduction methods both individually and in various combinations. The experiments are applied to a number of classical concurrent programs as well as a set of “real-world” programs. The results indicate that Petri net reduction and reduced state space generation are mutually beneficial techniques, and that combined approaches based on Petri net models are quite effective, compared to alternative analysis approaches.

Over the past few years, a number of research investigations have been initiated for static analysis of concurrent and distributed software. In this paper we report on experiments with various optimization techniques for reachability-based deadlock detection in Ada programs using Petri net models. Our experimental results show that various optimization techniques are mutually beneficial with respect to the effectiveness of the analysis.

A tasking query language (TQL) for aiding very general analysis of Ada tasking in a Petri-net-based environment is discussed. An important principle of TQL's design is that of hiding the formalism upon which the analysis framework is built. Instead, TQL defines a language by which queries of Ada interactions themselves can be expressed. Examples of TQL's capabilities are presented, and a sample analysis session using the gas station program is described.>

For distributed systems, system reliability is defined as the probability that the system can run an entire task successfully. When the system's hardware configuration is fixed, the system reliability is mainly dependent on the software design. The task allocation problem is addressed with the goal of maximizing the system reliability. A quantitative problem model, algorithms for optimal and suboptimal solutions, and simulation results are provided and discussed.>

The application of Petri net reduction to Ada-tasking deadlock detection is investigated. Net reduction can ease reachability analysis by reducing the size of the net while preserving relevant properties. By combining Petri net theory and knowledge of Ada-tasking semantics some specific efficient reduction rules are derived for Petri net models of Ada-tasking. A method by which a useful description of a detected deadlock state can be easily obtained from the reduced net's information is suggested.>

The use of Petri nets for defining a general static analysis framework for Ada tasking is advocated. The framework has evolved into a collection of tools that have proven to be a very valuable platform for experimental research. The design and implementation of tools that make up the tasking-oriented toolkit for the Ada language (TOTAL) are defined and discussed. Modeling and query/analysis methods and tools are discussed. Example Ada tasking programs are used to demonstrate the utility of each tool individually as well as the way the tools integrate. TOTAL is divided into two major subsystems, the front-end translator subsystem (FETS) and the back-end information display subsystem (BIDS). Three component tools that make up FETS are defined. Examples demonstrate the way these tools integrate in order to perform the translation of Ada source to Petri-net format. The BIDS subsystem and, in particular, the use of tools and techniques to support user-directed, but transparent, searches of Ada-net reachability graphs are discussed.>

An approach for automated modeling and verification of communication protocols is presented. A language that specifies the input/output behavior of protocol entities is introduced as the starting point of the approach, and verification of the linguistic specifications is discussed. Rules for conversion of the specifications into a Petri net model (based on a timed Petri net) are presented and illustrated by examples. This leads to a second level of verification on the net model. The approach is illustrated by its application to a part of the LAPD protocol.>

Ada tasking constructs involving time are modeled by timed Petri nets. Such modeling is helpful in interpreting the (often) ambiguous semantics described in the Ada reference manual. Timed and conditional entry call models that shed light on determining implementable interpretations are presented. From a general selective wait model, it is shown how to apply Petri net reduction operations to derive other selective wait models.>

An approach for automated modeling and verification of communication protocols is presented. A language that specifies input/output behavior of protocol entities is introduced as the starting point, and some verification of the specifications is discussed. Further verification is aided by translation of the specifications to a timed Petri net model.>

A discussion is presented of research on the development of a toolkit that supports general static analysis using a Petri net framework for Ada tasking. The toolkit integrates some custom and general-purpose tools. The custom tools were defined and implemented specifically for research in Ada tasking analysis; the general-purpose tools are Petri net tools developed to support arbitrary Petri-net-based research. The analysis toolkit is divided into two major subsystems. The first is the front-end translator subsystem, which translates Ada source (or design-level source specified in a design language called Ada Tasking Language) into a Petri net format. The translation allows one to base current and future analysis techniques on a model that is both theoretically mature and actively investigated. The second is the back-end information display subsystem, which receives user queries and presents tasking analysis results. Example Ada tasking programs are used to demonstrate the utility of the tools individually as well as collectively.>

A method is presented for detecting deadlocks in Ada tasking programs using structural; and dynamic analysis of Petri nets. Algorithmic translation of the Ada programs into Petri nets which preserve control-flow and message-flow properties is described. Properties of these Petri nets are discussed, and algorithms are given to analyze the nets to obtain information about static deadlocks that can occur in the original programs. Petri net invariants are used by the algorithms to reduce the time and space complexities associated with dynamic Petri net analysis (i.e. reachability graph generation).>

Optimal task allocation for redundant, heterogeneous distributed computer systems is examined. It is assumed that the systems under consideration are required for execution of long-term mission applications such as space flights. A formal description of the problem is given and formal, quantitative task allocation models are derived. Both an optimal allocation algorithm and an approximating optimal algorithm are derived, discussed, and compared by simulation results. For the latter case, a formula for computing the error associated with the approximation used, is also presented.>

The authors deal with the task allocation problem in distributed software design, with the goal of maximizing the system reliability. A quantitative problem model, algorithms for optimal and suboptimal solutions, and simulation results are provided and discussed. Because the authors use a new allocation goal-to maximize system reliability-this paper complements the existing body of knowledge in task allocation.>

Using Ada as a representative distributed programming language, the author discusses some ideas on complexity metrics that focus on Ada tasking and rendezvous. Concurrently active rendezvous are claimed to be an important aspect of communication complexity. A Petri net graph model of Ada rendezvous is used to introduce a rendezvous graph, an abstraction that can be useful in viewing and computing effective communication complexity.>

In this paper a technique called process merging is introduced. This technique allows the merging of two communicating sequential processes into a new single process. Thus, this technique can be used to reconfigure a distributed program after a faulty processing element has been detected. The technique is most applicable to dedicated multiple microprocessor systems where the need for continuous operation is critical. A process merging algorithm which operates on distributed programs using the CSP notation is presented in detail and its operation is discussed. In order to illustrate the merging technique, the algorithm's behavior is demonstrated using two classical distributed programs: the Bounded Buffer, Producer, Consumer program and the Dining Philosophers program. Finally, the merging technique is examined with respect to its demands on overall system operation and overhead. This examinatiQn leads to suggestions for future research.

Distributed computing systems represent a wide variety of computer systems, ranging from a centralized star network to a completely decentralized computer system. The design of software for distributed computing systems is more complicated due to many design constraints and interactions of software components of the system.