Optimal Petri-Net-Based Polynomial-Complexity Deadlock-Avoidance Policies for Automated Manufacturing Systems

Even for a simple automated manufacturing system (AMS), such as a general single-unit resource allocation system, the computation of an optimal or maximally permissive deadlock-avoidance policy (DAP) is NP-hard. Based on its Petri-net model, this paper addresses the deadlock-avoidance problem in AMSs, which can be modeled by systems of simple sequential processes with resources. First, deadlock is characterized as a perfect resource-transition circuit that is saturated at a reachable state. Second, for AMSs that do not have one-unit resources shared by two or more perfect resource-transition circuits that do not contain each other, it is proved that there are only two kinds of reachable states: safe states and deadlock. An algorithm for determining the safety of a new state resulting from a safe one is then presented, which has polynomial complexity. Hence, the optimal DAP with polynomial complexity can be obtained by a one-step look-ahead method, and the deadlock-avoidance problem is polynomially solved with Petri nets for the first time. Finally, by reducing a Petri-net model and applying the design of optimal DAP to the reduced one, a suboptimal DAP for a general AMS is synthesized, and its computation is of polynomial complexity.      

Providing multi-user access to distributed array processors

This paper describes the integration of two ICL Distributed Array Processors (DAPs) into a dual ICL 2976 configuration running the Edinburgh Multi-Access System (EMAS). The principles underlying the general multi-access service are not compromised; special scheduling arrangements provide effective control and use of the DAP resource while allowing multi-user access to the DAPs for DAP program development.     

ComPaSS: A Communication Package for Scalable Software Design

In massively parallel computers (MPCs), efficient communication among processors is critical to performance. This paper describes the initial implementation of the ComPaSS communication library to support scalable software development in MPCs. ComPaSS provides high-level global communication operations for both data manipulation and process control, many of which are based upon a small set of low-level communication primitives. The low-level operations of the ComPaSS library are provably optimal for a class of architectures representative of many commercial scalable systems, in particular those using wormhole routing and n-dimensional mesh network topologies. This paper concentrates on the multicast and multireceive components of the ComPaSS library, which are fundamental to implementing efficient high-level data parallel operations. The design of the multicast and multireceive primitives is described and an example of a data parallel application utilizing ComPaSS multicast is given. The scalability of these primitives is discussed, and improvements in performance resulting from use of the library on a 64-node nCUBE-2 are presented.     

Deadlock avoidance in sequential resource allocation systems withmultiple resource acquisitions and flexible routings

Considers the deadlock avoidance problem for the class of conjunctive/disjunctive (sequential) resource allocation systems (C/D-RAS), which allows for multiple resource acquisitions and flexible routings. First, a siphon-based characterization for the liveness of Petri nets (PNs) modeling C/D-RAS is developed, and subsequently, this characterization facilitates the development of a polynomial-complexity deadlock avoidance policy (DAP) that is appropriate for the considered RAS class. The resulting policy is characterized as C/D-RUN. The last part of the paper exploits the aforementioned siphon-based characterization of C/D-RAS liveness, in order to develop a sufficiency condition for C/D-RAS liveness that takes the convenient form of a mixed integer programming (MIP) formulation. The availability of this MIP formulation subsequently allows the “automatic” correctness verification of any tentative C/D-RAS DAP for which the controlled system behavior remains in the class of PNs modeling C/D-RAS, and the effective flexibility enhancement of the aforementioned C/D-RUN DAP implementations. Finally, we notice that, in addition to extending and complementing the current theory on deadlock-free sequential resource allocation to the most powerful class of C/D-RAS, the presented results also (i) nontrivially generalize important concepts and techniques of ordinary PN structural analysis to the broader class of nonordinary PNs, while (ii) from a practical standpoint, they can find direct application in the (work-) flow management of modern production, service and/or transportation environments     

Realizing Network Control Policies Using Distributed Action Plans

The increasing complexity in size and heterogeneity of networks requires the development of network management tools that are less dependent on human intervention. Many tasks in network management consist of the coordination and execution of multiple activities across different network platforms. In the first part of this paper we introduce a language to write Distributed Action Plans (DAPs). A DAP is meant to specify one of these distributed network management tasks. To run these plans we use policy agents. These are agents that can be specified in PDL, an event-driven programming language developed at Bell Labs to perform policy-based network management. The second half of the paper shows how DAPs are translated into PDL and describes the policy agent system that executes these DAPs.     

Concurrency and parallelism in MC and MD simulations in physics

Certain problems lend themselves admirably to SIMD architecture computers. A number of such problems in physics will be discussed and their implementation on the ICL DAP analyzed. Monte Carlo (MC) problems such as the 3-D Ising model and quantum chromodynamics (QCD) calculations need care and attention with respect to maintaining detailed balance on a SIMD architecture, whereas molecular dynamics (MD) problems do not pose such problems. The efficient use of a DAP requires the development of parallel algorithms designed to make use of the particular architecture and size of the machine, though further software developments must be made which remove the user one stage farther from the particular details of the computer. Experience on the DAP, especially those with only 2 Mbytes of store such as the Edinburgh DAPs, has led to thought about the detailed precisions necessary for the various calculations being done—many computers operate at an accuracy which is in excess of requirement whereas the bit-serial DAP can have its program finely tuned in accuracy.The present DAPs are far from the modern state of the art in fabrication, and future engines of similar design could be made with present technology with a rating well over a Gflop, providing very cost-effective computing.     

Computing minimal siphons in Petri net models of resource allocation systems: a parallel solution

Siphons are related to the liveness properties of Petri net models. This relation is strong in the case of resource allocation systems (RASs). Siphons can be used in these systems in order to both characterize and prevent/avoid deadlock situations. However, the computation of these structural components can be very time consuming or, even, impossible. Moreover, if, in general, the complete enumeration of the set of minimal siphons must be avoided (there can exist an exponential number of such components), some deadlock prevention methods rely on its (complete or partial) computation and enumeration. The special syntactical constraints of some classes of RASs can help in developing specific algorithms to compute siphons in a more efficient way. In this work, a known method for siphon computation is adapted to get advantage of the special (syntactical) structure of a class of RASs; a parallel implementation is proposed and some experimental results are presented.     

Computing (r, Q) policy for an inventory system with limited sharable resource

This paper deals with inventory systems with limited resource for a single item or multiple items under continuous review (r, Q) policies. For the single-item system with a stochastic demand and limited resource, it is shown that an existing algorithm can be applied to find an optimal (r, Q) policy that minimizes the expected system costs. For the multi-item system with stochastic demands and limited resource commonly shared among all items, an optimization problem is formulated for finding optimal (r, Q) policies for all items, which minimize the expected system costs. Bounds on the parameters (i.e., r and Q) of the optimal policies and bounds on the minimum expected system costs are obtained. Based on the bounds, an algorithm is developed for finding an optimal or near-optimal solution. A method is proposed for evaluating the quality of the solution. It is shown that the algorithm proposed in this paper finds a solution that is (i) optimal/near-optimal and/or (ii) significantly better than the optimal solution with unlimited resource.     

Using Shared-Resource Capacity for Robust Control of Failure-Prone Manufacturing Systems

Deadlock-free resource allocation has been an active area of research in flexible manufacturing. Most researchers have assumed that allocated resources do not fail, and thus, little research has addressed the discrete-event supervision of manufacturing systems that are subject to resource failure. In our previous work, we developed supervisory controllers to ensure robust deadlock-free operation for systems with unreliable resources. These controllers guarantee that parts requiring failed resources do not block the production of parts that are not requiring failed resources. This previous work assumes that parts requiring failed resources can be advanced into failure-dependent (FD) buffer space (buffer space exclusively dedicated to parts requiring unreliable resources). Supervisors admit only states for which a sequence of such part advancements is feasible. The research presented in this paper relaxes this assumption because, in some systems, providing FD buffer space might be too expensive or it might be desirable to load the system more heavily with FD parts. In this paper, we concentrate on distributing parts requiring failed resources throughout the buffer space of shared resources so that these distributed parts do not block the production of part types that are not requiring failed resources. The approach presented here requires no state enumeration and is polynomial in stable measures of system size. We also present results from simulation experiments that compare system performance under these new policies with system performance under our previously published supervisors. These results show that our new policies allow better performance if the required part mixes favor FD part types. The systems of interest are single-unit resource allocation systems.     

Path-Value Functions for Which Dijkstra’s Algorithm Returns Optimal Mapping

Dijkstra’s algorithm (DA) is one of the most useful and efficient graph-search algorithms, which can be modified to solve many different problems. It is usually presented as a tool for finding a mapping which, for every vertex v, returns a shortest-length path to v from a fixed single source vertex. However, it is well known that DA returns also a correct optimal mapping when multiple sources are considered and for path-value functions more general than the standard path-length. The use of DA in such general setting can reduce many image processing operations to the computation of an optimum-path forest with path-cost function defined in terms of local image attributes. In this paper, we describe the general properties of a path-value function defined on an arbitrary finite graph which, provably, ensure that Dijkstra’s algorithm indeed returns an optimal mapping. We also provide the examples showing that the properties presented in a 2004 TPAMI paper on the image foresting transform, which were supposed to imply proper behavior of DA, are actually insufficient. Finally, we describe the properties of the path-value function of a graph that are provably necessary for the algorithm to return an optimal mapping.     

A general FORTRAN to C translator

Theorists in Edinburgh University Physics Department are currently using two ICL Distributed Array Processors (DAPs), programmed in a matrix and vector extension of FORTRAN called DAP FORTRAN, to perform a variety of numerical simulations. However, many of the next generation of array processors, in particular the GEC Rectangular Image and Data processor (GRID), will be programmed in parallel extensions of C, like GRID-extended C. In this paper software is described which translates DAP FORTRAN into GRID-extended C, as well as FORTRAN 77 into C, enabling DAP FORTRAN programs to be run on the GRID.     

Rate adaptive shaping for the efficient transport of data traffic in diffserv networks

In this paper, we introduce the need for traffic shaping for the efficient transport of aggregate Internetworking traffic over Differentiated Services (DiffServ) networks. We propose a family of rate adaptive shapers (RASs) that aim at reducing the traffic burstiness. Although RASs can be used in either pure Best-Effort or any QoS enabled networks, our study is focused on their use in DiffServ networks where the traffic is subject to traffic control consisting of marking the packets according to a pre-negotiated traffic conditioning specification. RASs aim to increase the ratio of packets that are assigned the highest level of forwarding treatment by buffering and appropriate scheduling of packets before applying traffic control functions. The key ideas that motivate RASs design are introduced and evaluated by means of extensive simulations. Some additional enhancements are also discussed.     

Towards a Scalable and Robust DHT

The problem of scalable and robust distributed data storage has recently attracted a lot of attention. A common approach in the area of peer-to-peer systems has been to use a distributed hash table (or DHT). DHTs are based on the concept of virtual space. Peers and data items are mapped to points in that space, and local-control rules are used to decide, based on these virtual locations, how to interconnect the peers and how to map the data to the peers. DHTs are known to be highly scalable and easy to update as peers enter and leave the system. It is relatively easy to extend the DHT concept so that a constant fraction of faulty peers can be handled without any problems, but handling adversarial peers is very challenging. The biggest threats appear to be join-leave attacks (i.e., adaptive join-leave behavior by the adversarial peers) and attacks on the data management level (i.e., adaptive insert and lookup attacks by the adversarial peers) against which no provably robust mechanisms are known so far. Join-leave attacks, for example, may be used to isolate honest peers in the system, and attacks on the data management level may be used to create a high load-imbalance, seriously degrading the correctness and scalability of the system. We show, on a high level, that both of these threats can be handled in a scalable manner, even if a constant fraction of the peers in the system is adversarial, demonstrating that open systems for scalable distributed data storage that are robust against even massive adversarial behavior are feasible. Supported by NSF-ANIR 0240551, NSF-CCF 0515080, and NSF-CCR 0311795.     

面向大规模云资源调度的可扩展分布式调度方法

云数据中心异构物理服务器的能耗优化资源分配问题是NP难的组合优化问题,当资源分配问题规模较大时,求解的空间比较大,很难在合理时间内求得最优解。基于分而治之的思想,从调度模式方面提出可扩展分布式调度方法,即当云数据中心待调度的物理服务器的数量比较大时,将待调度的服务器划分为若干个服务器集群,然后在每个服务器集群建立能耗优化的资源分配模型,并利用约束编程框架Choco求解模型,获得能耗最优的资源分配方式。将提出的基于可扩展分布式调度方法的能耗优化云资源调度算法与非扩展调度算法进行实验比较,实验结果表明,提出的基于可扩展分布式调度方法的能耗优化云资源调度算法在大规模云资源分配上有明显的性能优势。     

Robust Supervisory Control for Product Routings With Multiple Unreliable Resources

Manufacturing systems are often subject to resource failure. In past work, we developed ldquorobustrdquo supervisory controllers for the single-unit resource allocation model. These guarantee that if any subset of resources fail, parts in the system requiring failed resources do not block the production of parts not requiring failed resources. To establish supervisor correctness, we assumed that each part type required at most one unreliable resource in its route. We now relax this assumption using a central buffer and present supervisors that guarantee robust operation without assumptions on route structure.     

Scheduling customers in a non-removal real-time system with an application to disk scheduling

In this article, we consider the problem of scheduling customers in a real-time system in which all customers are required to be serviced. Such anon-removal system can be distinguished from aremoval real-time system in which customers can be removed prior to completing service. We describe and evaluate a simple paradigm for mapping policies for removal systems to policies for non-removal systems. We show that several policies known to be optimal for removal systems map into policies which are also optimal for non-removal systems. The article concludes with an application of this paradigm to scheduling requests with real-time constraints on disk subsystems.This work is supported, in part, by the Office of Naval Research under contract N00014-87-K-0796 and the National Science Foundation under grant IRI-9114197.     

一种用于大规模图像分类的可扩展学习算法

随着大规模图像分类数据集的出现,设计一种可扩展的、高效的多类分类算法成为目前一个重要的挑战。基于迹范数正则惩罚函数,提出了一种新的大规模多类图像分类的可扩展学习算法。把具有挑战性的非光滑优化问题重构为一个带l1正则惩罚的无穷维优化问题,进而设计了一个简单而有效的加速坐标下降算法。展示了如何在量化的密集视觉特征的压缩域中进行高效的矩阵计算,该压缩域有100000个例子,1000多维特征和100多类图片。在图像网的子集“Fungeus”,“Ungulate”和“Vehicles”上的实验结果表明,提出方法的性能明显优于目前最先进的16高斯Fisher向量方法。     

An Asymptotically Efficient Simulation-Based Algorithm for Finite Horizon Stochastic Dynamic Programming

We present a simulation-based algorithm called "Simulated Annealing Multiplicative Weights" (SAMW) for solving large finite-horizon stochastic dynamic programming problems. At each iteration of the algorithm, a probability distribution over candidate policies is updated by a simple multiplicative weight rule, and with proper annealing of a control parameter, the generated sequence of distributions converges to a distribution concentrated only on the best policies. The algorithm is "asymptotically efficient," in the sense that for the goal of estimating the value of an optimal policy, a provably convergent finite-time upper bound for the sample mean is obtained     

Comments on “Deadlock avoidance policy for Petri net modelingof flexible manufacturing systems with shared resources”'

In the domain of flexible manufacturing systems, given a structural (static) model of the system, the existence of cycles of resources in such a model is a necessary condition for a deadlock to be reached. This condition is not sufficient in the general case because we cannot ensure that a state which establishes a circular-wait situation is reachable (cycles of resources are only potential circular-waits). In the above mentioned paper (Xing et al., 1996) and Ezpeleta et al. (1998), two results which directly imply that the existence of cycles of resources is also a sufficient condition are presented. These results are established for a subclass of FMS, where choices are not allowed in the process plans, and where each part uses one and only one system resource in each state during its processing. Both approaches use Petri nets to model the systems, namely production Petri nets (PPN), and linear systems of simple sequential processes with resources. In fact, both models are very similar. Here we show that the proof of the result in the Xing et al. is not correct, we also show that the result itself is correct (it is implied by the result in Ezpeleta et al.). Moreover, we think that the approach in Ezpeleta et al. is clearer, and that it provides more insight into the problem     

An approach for modeling and analysis of security system architectures

Security system architecture governs the composition of components in security systems and interactions between them. It plays a central role in the design of software security systems that ensure secure access to distributed resources in networked environment. In particular, the composition of the systems must consistently assure security policies that it is supposed to enforce. However, there is currently no rigorous and systematic way to predict and assure such critical properties in security system design. A systematic approach is introduced to address the problem. We present a methodology for modeling security system architecture and for verifying whether required security constraints are assured by the composition of the components. We introduce the concept of security constraint patterns, which formally specify the generic form of security policies that all implementations of the system architecture must enforce. The analysis of the architecture is driven by the propagation of the global security constraints onto the components in an incremental process. We show that our methodology is both flexible and scalable. It is argued that such a methodology not only ensures the integrity of critical early design decisions, but also provides a framework to guide correct implementations of the design. We demonstrate the methodology through a case study in which we model and analyze the architecture of the Resource Access Decision (RAD) Facility, an OMG standard for application-level authorization service.