Deadlock avoidance with a modified banker's algorithm

There are three methods for handling deadlocks in resource allocation systems: deadlock prevention, deadlock avoidance and deadlock detection combined with recovery. Of these three methods deadlock avoidance is preferable in many cases but seldom used on account of its high cost. We present a simple modification of a known deadlock avoidance algorithm, the banker's algorithm, which has a running time (mn ²) in a system consisting ofn processes andm different types of resources. Our modified algorithm gives an amortized worst case running time ofO(mn) under certain likely conditions and in that way it can be considered a competitive method for handling deadlocks. At worst, our algorithm is twice as fast as the banker's algorithm.This work was partly supported by The National Swedish Board for Technical Development (STUF) under contract number 85-3127.     

Collision avoidance for nonrigid objects

Summary The path existence problem and the collision detection problem for time-varying objects in a geometric scene are discussed. For a large class of spherical nonrigid objects, exact solutions of the path existence problem are developed based on decomposition techniques and graph traversal. For the collision detection problem of a single moving circle in the plane, efficient data structures are presented for linear/circular and polynomial paths.Work was partially supported by DFG (Mu744/1-1).     

Deadlock free buffer allocation in closed queueing networks

Blocking queueing networks are of much interest in performance analysis due to their realistic modeling capability. One important feature of such networks is that they may have deadlocks which can occur if the node capacities are not sufficiently large. A necessary and sufficient condition for the node capacities is presented such that the network is deadlock free. An algorithm is given for buffer allocation in blocking queueing networks such that no deadlocks will occur assuming that the network has the special structure called cacti-graph. Additional algorithm which takes linear time in the number of nodes, is presented to find cycles in cacti networks.Akyildiz's work was supported in part by School of Information and Computer Science, ICS, of Georgia Tech and by the Air Force Office of the Scientific Research (AFOSR) under Grant AFOSR-88-0028.     

反避税新政考

转让定价政策的调整变化,直接影响着企业在税收方面的战略部署及筹划思路,企业应随时把握局势,谋势而动。     

Pattern avoidance for alternating permutations and Young tableaux

We define a class Ln,k of permutations that generalizes alternating (up-down) permutations and give bijective proofs of certain pattern-avoidance results for this class. As a special case of our results, we give bijections between the set A2n(1234) of alternating permutations of length 2n with no four-term increasing subsequence and standard Young tableaux of shape 〈n³〉, and between the set A2n+1(1234) and standard Young tableaux of shape 〈³n−1,2,1〉. This represents the first enumeration of alternating permutations avoiding a pattern of length four. We also extend previous work on doubly-alternating permutations (alternating permutations whose inverses are alternating) to our more general context.The set Ln,k may be viewed as the set of reading words of the standard Young tableaux of a certain skew shape. In the last section of the paper, we expand our study to consider pattern avoidance in the reading words of standard Young tableaux of any skew shape. We show bijectively that the number of standard Young tableaux of shape λ/μ whose reading words avoid 213 is a natural μ-analogue of the Catalan numbers (and in particular does not depend on λ, up to a simple technical condition), and that there are similar results for the patterns 132, 231 and 312.     

Achievement and avoidance games for generating abelian groups

For any finite groupG, the DO GENERATE game is played by two players Alpha and Beta as follows. Alpha moves first and choosesx ₁ ∈G. Thek-th play consists of a choice ofx _k ∈G ?S _k ?1 whereS _n ={itx ₁,...,x _n }. LetG _n = 〈S _n 〉. The game ends whenG _n =G. The player who movesx _n wins. In the corresponding avoidance game, DON'T GENERATE, the last player to move loses. Of course neither game can end in a draw. For an arbitrary group, it is an unsolved problem to determine whether Alpha or Beta wins either game. However these two questions are answered here for abelian groups.     

A pattern avoidance criterion for free inversion arrangements

We show that the hyperplane arrangement of a coconvex set in a finite root system is free if and only if it is free in corank 4. As a consequence, we show that the inversion arrangement of a Weyl group element w is free if and only if w avoids a finite list of root system patterns. As a key part of the proof, we use a recent theorem of Abe and Yoshinaga to show that if the root system does not contain any factors of type C or F, then Peterson translation of coconvex sets preserves freeness. This also allows us to give a Kostant–Shapiro–Steinberg rule for the coexponents of a free inversion arrangement in any type.     

On systolic arrays for updating the Cholesky factorization

We have considered the systolic implementation of several methods for updating the Cholesky factorization. For positive rank-k changes there are simple one-pass arrays that implement algorithms based on elimination and plane rotations. In the case of negative rank-one changes, we do not feel that the standard algorithm [2] has a practical implementation. We have introduced a new algorithm for the case of a negative rank-k change and provided an attractive two-pass systolic implementation.     

Guaranteed avoidance strategies

We consider a dynamical system under the control of two agents, one of whom desires to keep the system's state out of a given set regardless of the other agent's actions. The guaranteed avoidance conditions of Ref. 1 are generalized to admit piecewiseC ¹ test functions; this generalization permits application to a wider class of problems. The results are illustrated by application to a version of the homicidal chauffeur game.Dedicated to R. BellmanThis paper is based on research supported by NSF under Grant No. ENG-78-13931.     

Descent pattern avoidance

We extend the notion of consecutive pattern avoidance to considering sums over all permutations where each term is a product of weights depending on each consecutive pattern of a fixed length. We study the problem of finding the asymptotics of these sums. Our technique is to extend the spectral method of Ehrenborg, Kitaev and Perry. When the weight depends on the descent pattern we show how to find the equation determining the spectrum. We give two length 4 applications. First, we find the asymptotics of the number of permutations with no triple ascents and no triple descents. Second, we give the asymptotics of the number of permutations with no isolated ascents or descents. Our next result is a weighted pattern of length 3 where the associated operator only has one non-zero eigenvalue. Using generating functions we show that the error term in the asymptotic expression is the smallest possible.     

On systolic array methods for band matrix factorizations

A systolic array for band matrixQR factorization is presented and its connection with various other arrays explained. It is shown how the computations should be performed on banded rectangular matrices which appear in several numerical problems.     

Conditional targeting for communication

In this work we propose the use of a targeting method applied to chaotic systems in order to reach special trajectories that encode arbitrary sources of messages. One advantage of this procedure is to overcome dynamical constraints which impose limits in the amount of information that the chaotic trajectories can encode. Another advantage is the message decoding, practically instantaneous and independent of any special technique or algorithm. Furthermore, with this procedure, information can be transmitted with no errors due to bounded noise.     

Impartial achievement and avoidance games for generating finite groups

We study two impartial games introduced by Anderson and Harary and further developed by Barnes. Both games are played by two players who alternately select previously unselected elements of a finite group. The first player who builds a generating set from the jointly selected elements wins the first game. The first player who cannot select an element without building a generating set loses the second game. After the development of some general results, we determine the nim-numbers of these games for abelian and dihedral groups. We also present some conjectures based on computer calculations. Our main computational and theoretical tool is the structure diagram of a game, which is a type of identification digraph of the game digraph that is compatible with the nim-numbers of the positions. Structure diagrams also provide simple yet intuitive visualizations of these games that capture the complexity of the positions.     

Coordination and collision avoidance for Lagrangian systems with disturbances

In this paper we address the problem of cooperation and collision avoidance for Lagrangian systems with input disturbances. We design control laws that guarantee cooperation as well as collision-free maneuvers. We show, using a two-step proof, that the avoidance part of the control laws guarantees safety of the agents independently of the coordinating part. Then, we establish an ultimate bound on the region to which all the agents converge to. The obtained theoretical results are illustrated through numerical examples.     

A linear systolic algorithm for the connected component problem

A linear systolic algorithm is proposed for the connected component problem. Given an undirected graph withn vertices,m edges, andp connected components, the proposed algorithm uses (n –p + 1) cells pipelined together to figure out, in (m + 3(n –p) + 2) systolic cycles, which component each vertex belongs to.This research was supported by the National Science Council of the Republic of China under the Contract NSC77-0408-E007-01.     

Path planning in formation and collision avoidance for multi-agent systems

This paper investigates, in a centralized manner, the motion planning problem for a team of unicycle-like mobile robots in a known environment. In particular, a multi-agent collision-free patrolling and formation control algorithm is presented, which combines outcomes of: (i) stability analysis of hybrid systems, (ii) algebraic geometry, and (iii) classical potential functions. The objective is achieved by designing a Lyapunov-based hybrid strategy that autonomously selects the navigation parameters. Tools borrowed from algebraic geometry are adopted to construct Lyapunov functions that guarantee the convergence to the desired formation and path, while classical potential functions are exploited to avoid collisions among agents and the fixed obstacles within the environment. The proposed navigation algorithm is tested in simulation and then validated by using the robots of a remote accessible robotic testbed.