This paper deals with deadlock and fairness issues that may arise when network users request resources for guaranteed service with the resource reservation protocol (RSVP). A deadlock occurs when a request can only be satisfied if the resources reserved for another request are released, but the reserved resources are never released. The fairness issue occurs when some reservation requests may be satisfied but only after a very long wait. Our approach to these issues is based on our belief that a network should provide stable throughput and fairness whatever the behavior of the user. Our methods are unique in two respects. First, during the session setup phase, a node directly connected to the requesting users terminates the users' behavior and makes reservations fairly and efficiently in place of the users. Second, our three admission control methods allocate resources for each reservation request by considering not only the current residual bandwidth but also the properties of the requesting session; e.g., its weight (the number of resources it requires) or its age (how long it has been waiting for session setup). Our methods do not maximize the throughput since they always keep a certain amount of resources unreserved for fairness. From simulation results, however, they do provide quite fair behavior, and their throughput is stable regardless of the network size and the session holding time.

A fault-tolerant wormhole routing algorithm on mesh-connected processors is proposed. The proposed algorithm is based on the solid fault model and allows the fault polygons to be overlapped. The algorithm compares the position of fault region relative to current channel with the fault direction field of a misrouted message to route around overlapped fault polygons. A node deactivating algorithm to convert non-solid fault region into solid fault region is also proposed. The proposed routing algorithm uses four virtual channels and is deadlock and livelock free.

We propose a fault-tolerant routing algorithm for 2D meshes. Our routing algorithm can tolerate any number of concave fault regions. It is based on xy-routing and uses the concept of the fault ring/chain composed of fault-free elements surrounding faults. Three virtual channels per physical link are used for deadlock-free routing on a fault ring. Four virtual channels are needed for a fault chain. For a concave fault ring, fault-free nodes in the concave region have been deactivated to avoid deadlock in the previous algorithms, which results in excessive loss of the computational power. Our algorithm ensures deadlock-freedom by restricting the virtual channel usage in the concave region, and it minimizes the loss of the computational power. We also extend the proposed routing scheme for adaptive fault-tolerant routing. The adaptive version requires the same number of virtual channels as the deterministic one.

Petri nets are one of useful models for discrete event systems in which liveness problem as well as reachability problem is one of big issues. But, it has not been completely solved from the point of view of useful initial-marking-based liveness conditions in general Petri nets. In this paper, to guarantee local liveness (i. e. , liveness underMoD) for each minimal deadlock (MSDL),ND=(SD,TD,FD,MoD), with real deadlock-trap structure, it is shown that the minimum number of required live minimal structural traps (MSTRs),NT=(ST,TT,FT,MoT) s. t. SD ST, is conditionally (which means that the conditions of Lemma 4-9 are fulfilled for a bounded MSDL ND containing at least one MSTR NT s. t. SD ST and see also Remarks 4-2 (3) in Sect. 4. 3) "one. " Note that this local liveness for ND s. t. SD ST is one of useful necessary conditions for liveness condition of general Petri nets N=(S,T,F,Mo) s. t. S SD. However, because this has not been discussed in literature and is not trivial, some new concepts such as T-cornucopias and return paths are introduced into the real deadlock-trap structure s. t. SD ST in N and this is proven by dividing it into two cases: ND s. t. SD ST is live and unbounded under MoD and ND s. t. SD ST is live and bounded under MoD. Usefulness for the results obtained is also discussed.

Recursive Diagonal Torus (RDT) is a class of interconnection network for massively parallel computers with 216 nodes. In this paper, message transfer algorithms on the RDT are proposed and discussed. First, a simple one-to-one message routing algorithm called the vector routing is introduced and its practical extension called the floating vector routing is proposed. In the floating vector routing both the diameter and average distance are improved compared with the fixed vector routing. Next, broadcasting and hypercube emulation algorithm scheme on the RDT are shown. Finally, deadlock-free message routing algorithms on the RDT are discussed. By a simple modification of the e-cube routing and a small numbers of additional virtual channels, both one-to-one message transfer and broadcast can be achieved without deadlock.

Up to now, the only useful and well-known structural or initial-marking-based necessary and sufficient liveness conditions of Petri nets have only been those of an extended free-choice (EFC) net and its subclasses such as a free-choice (FC) net, a forward conflict free (FCF) net, a marked graph (MG), and a state machine (SM). All the above subclasses are activated only by deadlock-trap properties (i.e., real d-t properties in this paper), which mean that every minimal structural deadlock (MSDL ND=(SD, TD, FD, MoD)) in a net contains at least one live minimal structural trap (MSTR NT=(ST, TT, FT, MoT)) which is initially marked. However, the necessary and sufficient liveness conditions for EFCF, EBCF, EMGEFCFEBCF, AC (EFCFC), and the net with kindling traps NKT have recently been determined, in which each MSDL without real d-t properties was also activated by a new type of trap of trap, i.e., behavioral traps (BTRs), which are defined by introducing a virtual MSTR, a virtual maximal structural trap (virtual STR), a virtual MSDL, and a virtual maximal structural deadlock (virtual SDL) into a target MSDL. In this paper, a structural or initial-marking-based necessary and sufficient condition for local liveness (i.e., virtual deadlock-trap properties) of each MSDL ND s.t. SDST, SDST, SDST (but ND s.t. SDST is dead owing to real deadlock-trap properties) in a general Petri net N is presented by extending that in NKT. Specifically, live minimal behavioral traps (MBTRs) as well as live maximal behavioral traps (BTRs), i.e., virtual deadlock-trap properties, in a general Petri net N are characterized using the real d-t properties of each MSDL ND s.t. SDST for a general Petri net N, which were also obtained by extending the concept of return paths in NKT in connection with an MSDL which contains at least one MSTR and by using the concepts of T-cornucopias and absolute T-cornucopias in a subclass Ñ of N. In other words, BTRs are defined by introducing a virtual MSTR, a virtual STR, a virtual MSDL, and a virtual SDL into a target MSDL without real d-t properties. Additionally, a structural or initial-marking-based necessary and sufficient condition for liveness of a new subclass Nn of a general Petri net N (i.e., a general Petri net without time) is derived, and the usefulness of the obtained results is also discussed.

If a general Petri net N = (S, T, F, Mo) is transition-live under Mo, it is evident that each maximal structural deadlock SDL(D) in N as well as each minimal structural deadlock MSDL (ND) in each D is also transition-live under Mo. However, since the converse of the latter of the above is not always true, it is important to obtain the conditions for this converse to be true if we want to have a useful necessary and sufficient "initial-marking-based" or "structural" liveness condition for N. Up to now, usefull and well-known structural or initial-marking-based necessary and sufficient liveness conditions of Petri nets have only been those of an asymmetric choice (AC) net and its subclasses such as an EFC net, an FC net, an FCF net, MG, and SM. However, all the above subclasses are activated only by real or virtual deadlock-trap properties which are local liveness for each minimal deadlocks; in other words, the above topics of this paper are unconditionally satisfied in those subclasses because of their special structure of nets. In this paper, a necessary and sufficient structural liveness condition for a general Petri net N with globally structural live minimal structural deadlocks is presented as follows: The next () or () is satisfied. () N has no SDL D. () If N has at least one SDL D, () or () is satisfied under the condition that each MSDL ND in N is transition-live under Mo. () N has no singular MSDL (α) (i.e., (α-) and (α-)). () If N has at least one singular MSDL (α-)((α-), resp.), every semi-MDSL ()((), resp.) NDS = (SDS, TDS, FDS, MoDS with respect to each singular MSDL (α-)((α-), resp.), is transition-live under the MoDS under the condition of "the condition (**)", where the locally structural liveness for this NDS means (1) or (2)((3), resp.) of Lemma 4-4 and "the condition (**)" is defined in Lemma 4-7 of this paper. The relationship between the above results and the liveness problem for N is also shown.

Petri nets are useful in modeling and analyzing various types of discrete-event systems such as parallel processing systems, distributed systems, and sequential control systems, because Petri nets can easily be used to represent such properties of these systems as concurrency, nondecidability, and causality. Various behavioral analytic problems on Petri nets are reduced to reachability and liveness on them. It is also known that the decidability of liveness is equivalent to that of reachability which is solvable. However, useful necessary and sufficient structural liveness conditions have been given only for extended free-choice (EFC) nets and their subclasses. Moreover recently, a necessary and sufficient structural liveness condition for a useful subclass NKT=(SKT, TKT, FKT, MoKT) (i.e., a Petri net in which each minimal structural deadlock (MSDL) contains at least one real or virtual kindling trap, each locally structural-live MSDL ND=(SD, TD, FD, MoD) is never globally dead even if all key transitions for local liveness of each MSDL are controlled by the net of SKTSD s.t. SKTSD, and there exists no singular MSDL of type (α)) has also been given. In this paper, in order to give one of the bases for a necessary and sufficient "structural" or "initial-marking-based" liveness condition for a general Petri net N, we will, first, directly present a necessary and sufficient local liveness condition for each MSDL with a real deadlock-trap structure in a subclass Ñ (N) using the net structure and initial token distribution and extending basic concepts used in NKT, where Ñ is a general Petri net without live behavioral traps, local liveness means a useful necessary condition for the above final goal, and real deadlock-trap structure means that each MSDL in Ñ contains at least one minimal structural trap. Secondly, a new subclass is shown in which, if the above locally structural liveness condition for each MSDL holds, then the whole-net liveness is also guaranteed. It is also argued that the obtained results are applicable to describing new live behavioral traps and deriving a necessary and sufficient structural liveness condition, which is the final goal in this work, for a general Petri net N.

In communication protocols, the behaviour of a protocol entity is related to the behaviour of another protocol entity as they communicate under sets of communication rules (protocols). Thus, it is desirable to concentrate on the design of one protocol entity and generate the corresponding protocol entity automatically. Furthermore, it is desirable that the protocol is formal, precise and unambiguous that is, it is described using FDTs (Formal Description Techniques). In this paper, we propose a protocol synthesis algorithm in which, from a LOTOS specification of a single given entity, LOTOS specification of the corresponding peer entity is generated automatically. Unlike previous works, where FSMs (Finite State Machines) were used to synthesize protocols, we use LOTOS, which is one of FDTs developed by ISO, in our proposed synthesis algorithm. We prove that the generated protocol is logical errors free, collectively represented as deadlock free, if the given entity is in certain forms which are natural in the context of connunication protocols.

In this paper, it is proven that the following three decision problems on validation of protocols with bounded capacity channels are NP-complete. (1) Given a protocol with the channel capacity being 1, determine whether or not there exist deadlocks in the protocol. (2) Given a protocol with the channel capacity being 1, determine whether or not there exist unspecified receptions in the protocol. (3) Given a protocol with the channel capacity being 2, determine whether or not there exist overflows such that the channel capacity is not bounded by 1 in the protocol. These results suggest that, even when all channeles in a protocol are bounded by 1 or 2, protocol validation should be in general interactable. It also clarifies the boundary of computational complexity of protocol validation problems because the channel capacity 0 does not allow protocols to transmit and recieve messages.

The structural necessary and sufficient condition for "the transition-liveness means the place-liveness and vice-versa" of a subclass NII of general Petri nets is given as "the place and transition live Petri net, or PTL net, ÑII". Furthermore, "the one-token-condition Petri net, or OTC net, II" which means that every MSDL (minimal structural deadlock) is "transition and place live" under at least one initial token, i.e., II is "transition and place live" under the above initial marking. These subclasses NII, ÑII( NII), and II(ÑII) are almost the general Petri nets except at least one MSTR(minimal structural trap) and at least one pair of "a virtual MSTR or a virtual STR" and "a virtual MSDL" of an MBTR (minimal behavioral trap) in connection with making an MSDL transition-live.