Synchronizations frequently occur in the modeling and design of distributed and concurrent systems. Designing a correct system from subsystems by considering the synchronizations of events is a difficult and complex task because it often destroys some desirable properties of subsystems and induces the whole system deadlocks. This paper formulates a property-preserving transition-reduction transformation to handle the synchronization problem in Petri net-based system design. It starts by designing correct subsystems without taking transition-reduction consideration. Synchronizations are then introduced by merging transitions of subsystems. Depending on the structure of transitions, two classes of transition-reductions are investigated. For each class, this paper shows that many structural and behavior properties can be preserved.

A large automatic system in manufacturing is usually composed of a set of subsystems sharing the usage of some resources. It is a major design issue to prove the liveness, boundedness and reversibility of the composite system. In this paper, the subsystems are modeled as augmented marked graphs. These augmented marked graphs are then composed into a composite system by merging those places representing the same sources. Conditions are provided under which siphons, traps, liveness, boundedness and reversibility of the subsystems are preserved in the composite system.

The fault-state detection approach for blackbox testing consists of two phases. The first is to bring the system under test (SUT) from its initial state to a targeted state t and the second is to check various specified properties of the SUT at t. This paper investigates the first phase for testing systems specified as observable nondeterministic finite-state machines with probabilistic and weighted transitions. This phase involves two steps. The first step transfers the SUT to some state t' and the second step identifies whether t' is indeed the targeted state t or not. State transfer is achieved by moving the SUT along one of the paths of a transfer tree (TT) and state identification is realized by using diagnosis trees (DT). A theoretical foundation for the existence and characterization of TT and DT with minimum weighted height or minimum average weight is presented. Algorithms for their computation are proposed.

This paper presents an approach for detecting and resolving feature interactions (FI) in telephone systems. In this approach, the basic telephone system (POTS) and the features are each represented as a temporal colored Petri net (TCP-net). When the POTS is enhanced with some features, their TCP-nets are integrated. The functionality of a feature is represented as a temporal formula and the behavior of the enhanced system is represented as the set of all firing sequences each of which realizes a transition-invariant of the TCP-net representing the feature. FI can be detected by inspecting whether or not the temporal formula is violated when executing some of these firing sequences. Three theorems are provided for finding realizing sequences and detecting FIs. Detailed examples are used to illustrate the specification of telephone features and the detection and resolution of FIs.

Proposes an approach to the synthesis and analysis of a FMS with a place/transition net. In this approach, a use case is represented as a firing sequence and is used to construct a net representing each working entity (e.g. a manufacturing machine) or the whole system, while invariance-preserving transformations are used to ensure place and transition invariants are preserved during synthesis and simplification. A detailed example is used for illustration.

This paper proposes a timed workflow model and a temporal consistency checking approach. The proposed model incorporates the duration of task, the duration of flow, and the concept of multiple time axes task execution into the conventional workflow model. It enables the modeling of global business processes.

A novel and efficient protocol based on a single logical ring for multicast communication among a group of processes is presented. The senders and receivers are merged in the same group and this peer group reflects a cooperative (mirror) group of information servers. The protocol maintains consistency in the group by using two strategies. First, by placing a total sequence number in each of the multicast messages, it guarantees total ordering of message delivery for each member. Second, in contrast to other ring protocols which are based on real token passing, it uses a virtual token and achieves message atomicity by using up to n point-to-point control messages. Since no real token passing messages are rotating on the ring, the position of the token holder is calculated by using a logical clock located in each of the processes. The protocol can tolerate communication faults, process crash failures and network partitioning. The protocol has been implemented and experimental results show that the protocol achieves satisfactory performance.

Transformations preserving (i.e., neither losing nor creating) specific properties are often used to simplify a system so that certain specified properties can be detected more easily from the transformed system. For five classes of transformations on place/transition systems (PTSs), namely, insertion, elimination, replacement, composition and decomposition, this paper provides the conditions which can be used for determining whether or not they preserve the place-invariants and transition-invariants of the PTS. A place-invariant is a subset of places whose total number of tokens remains unchanged under any execution of the system. A transition-invariant is a multiset of transitions whose execution in a certain order will leave the distribution of tokens unchanged. Unlike the basic approach of detecting place-invariants, which requires lengthy computation on the entire system of row matrix equations, the proposed conditions are for very general transformations and involve computation of only the new, eliminated and affected places and transitions.

S.S. Lam and A.U. Shankar (1982) have proposed a projection method for protocol verification. They claim that the method guarantees the faithfulness of the safety and liveness properties of a protocol system. Although not clearly defined, `faithfulness' appears to mean that `the image protocol system is live (respectively, safe) if and only if the original protocol system is live (respectively, safe). It is shown that the `only if' part is not true for certain liveness properties, and a remedy is suggested.

This paper shows that graph traversal techniques have fundamental differences between serial and distributed computations in their behaviors, computational complexities, and effects on the design of graph algorithms. It has three major parts. Section I describes the computational environment for the design and description of distributed graph algorithms in terms of an architectural model for message exchanges. The computational complexity is measured in terms of the number of messages transmitted. Section II presents several distributed algorithms for the pure traversal, depth-first search, and breadth-first search techniques. Their complexities are also given. Through these descriptions are brought out some of the intrinsic differences in the behaviors and complexities of the fundamental traversal techniques between a serial and a distributed computation environment. Section III gives the distributed version of the Ford and Fulkerson algorithm for the maximum flow problem by means of depth-first search, the largest-augmentation search and breadth-first search. The complexities of these methods are found to be 0(f*|A|), 0((l + logM/(M-1)f*|V||A|) and O(|V|6), respectively, where f* is the maximum flow value of the problem, M is the maximum number of ucs in a cut, |V| is the number of vertices, and |A| is the number of arcs. Lastly, it is shown that the largest augmentation search may be a better method than the other two. This is contrary to the known results in serial computation.

A simple and efficient method for processing general equijoin queries in a distributed relational database is described. The query is first decomposed into a set of simple queries, each being involved with only one of the joining domains and its relevant equijoins. An extended version of Hevner and Yao's STRATEGY PARALLEL or STRATEGY SERIAL is then applied on each of them for generating transmission schedules. These schedules will fully reduce (with respect to a simple query) some specified relations. The latter are then transmitted to the result site for final processing. In the case of minimizing total time, our method has a lower order of complexity than ALGORITHM GENERAL studied by Hevner and Apers. Examples show that our method gives better and more efficient solutions than theirs.

There exist two approaches for solving the maximum network flow problem.In the fLrst approach, flow is augmented along paths and is always conserved at the vertmes In the second approach, flow is augmented through layers and is sometimes not conserved at some of the vertices.Many methods based on these two approaches are first briefly revmwed A computational comparison is then presented of eight of the methods--depth-first search, breadth-fLrst search, largestaugmentatmn, Dmic, layer-updating, Karzanov, Dimc-Karzanov, and Kinanwala-Rao.Problems with up to 1500 vertices and 7960 arcs have been tested.Computatmnal results show that Dnuc's method is better than all of the other methods.However, for small-sized problems (up to 25 vertices and 200 arcs), the performances of the depth-first and breadth-first methods are comparable to Dinic's method.Hence, with programming simphclty and memory space requirements taken into consideration, the former also seem to be a good chome for small problems.

This paper consists of two parts The first part describes an algorithm for solving the multifacility location problem with rectilinear distance, usmg a mmm]tml-cut approach.The second part is a Fortran program of this algorithm Key Words and Phrases: multffacillty, optimal locatmn, rectilinear distance, minmaum cut CR Categories: 3.57, 5 41 The Algorithm: A Program for the Multifaeility Location Problem with Rectilinear Distance by the Mimmum-Cut Approach.

No abstract available.