One of the most common approaches to deadlock prevention is a mechanism known as buffer preallocation. The key concept is that buffers are allocated, most usually for a virtual circuit or class of virtual circuits, before any data is transmitted, and this allocation is done in such a way that no deadlocks are possible. This preallocation typically occurs through the transmission of reservation control messages prior to the transmission of normal data traffic. Control traffic deadlock prevention has yet to be studied. It is shown that deadlocks may occur in connection with this initializing control traffic, and that the resolution of such deadlocks must be handled with some care. If such resolution is not handled with sufficient care, a condition termed standoff may result, whereby contention for the allocation of one or more critical buffers results in resource being allocated to none of the contending parties. Protocols that prevent the phenomenon of standoff, thereby ensuring true deadlock-free operation are described.>

A machine model in which load operations can be performed in parallel with arithmetic operations by two separate functional units is considered. For this model, the evaluation of a set of expression trees is discussed. A dynamic programming algorithm for producing an approximate solution is described and analyzed. For binary trees its worse-case cost is at most $\min (1.091,1 + {{(2\log n)} / n})$ times the optimal cost.

We consider a machine model in which load operations can be performed in parallel with arithmetic operations by two separate functional units. For this model, the evaluation of a set of expression trees is discussed. A dynamic programming algorithm to produce an approximate solution is described and analyzed. For binary trees its worse case cost is at most 9.1% worse than the optimal cost.

Distributed algorithms for the detection and resolution of deadlocks in store-and-forward computer communication networks are presented and validated. The algorithms use a fixed amount of storage at each node (that is independent of the size of the network). The detection algorithm is simple but requires network-wide coordination. The resolution algorithm is based on earlier approaches, but uses the network-wide coordination to address certain synchronization problems. When the detection and resolution algorithms are merged, it is guaranteed that packets will arrive at their destinations in finite time.

A distributed algorithm for the detection of deadlocks in store-and-forward communication networks is presented. At first, we focus on a static environment and develop an efficient knot detection algorithm for general graphs. The knot detection algorithm uses at most O(n2+ m) messages and O(log (n)) bits of memory to detect all deadlocked nodes in the static network. Using the knot detection algorithm as a building block, a deadlock detection algorithm in a dynamic environment is developed. This algorithm has the following properties: It detects all the nodes which cause the deadlock. The algorithm is triggered only when there is a potential for deadlock and only those nodes which are potentially deadlocked perform the algorithm. The algorithm does not affect other processes at the nodes.

A distributed algorithm for the detection of deadlocks in store-and-forward communication networks is presented. At first, we focus on a static environment and develop an efficient knot detection algorithm for general graphs. The knot detection algorithm uses at most Ο(n2 + m) messages and Ο(log(n)) bits of memory to detect all deadlocked nodes in the static network. Using the knot detection algorithm as a building block, a deadlock detection algorithm in a dynamic environment is developed. This algorithm has the following properties: It detects all the nodes which cause the deadlock. The algorithm is triggered only when there is a potential for deadlock and only those nodes which are potentially deadlocked perform the algorithm. The algorithm does not affect other processes at the nodes.

The paper introduces a reliable distributed procedure for establishing and cancelling routes in a circuit-switched data network that uses local path identifiers (LPID). The procedure ensures that the route is set up properly unless a failure is encountered, data messages are delivered to their destinations unless they encounter a cancellation process and the route is cancelled, and all LPID entries are released after a failure or session completion.

This paper discusses SNA/LEN, a possible extension of Systems Network Architecture intended to allow peer, dynamic, and easy to use networking functions for a variety of node sizes down to and including the new generation of personal computers. After reviewing the special requirements posed by small systems and the need for including them as equal partners in networks, the LEN architecture is described. This is done by following a sequence of steps that begin when a logical resource at some node that may not yet be part of the connectivity of an existing network requests a session with a remote logical resource of unknown location. After connectivity with the preexisiting network is established, directory services locates the remote object, route selection services determines the preferred path, a session is activated, and deadlock-free flow control assures a useful flow of data. Preliminary quantitative results from an LEN prototype are presented.

In computer networks, message routing is often accomplished by network nodes using local information. The unavailability of global information intuitively makes hard routing problems virtually impossible. This paper formalizes this intuition by examining a hard (NP-complete) routing problem, the problem of multi-destination routing. It is shown that with only limited information it is impossible to optimize network utilization for the multi-destination routing problem. Moreover, it is impossible to even approximate optimality to within a specific tolerance. Several versions of this result are proved; the versions differ in terms of the amount of information available at a node, and the extent to which the problem cannot be approximated. An improved local information algorithm is presented which is best possible amongst local information algorithms.

In computer communication networks, routing is often accomplished by maintaining copies of the network topology and dynamic performance characteristics in various network nodes. The present paper describes an algorithm that allows complete flexibility in the placement of the topology information. In particular, we assume that an arbitrary subset of network nodes are capable of maintaining the topology. In this environment, protocols are defined to allow automatic updates to flow between these more capable nodes. In addition, protocols are defined to allow less capable nodes to report their topology data to the major nodes, and acquire route information from them.

Abstract Let G = (V, E) be a graph with weight function w:E rightarrow Z+ and length function l:E /rightarrow Z+. The problem of determining for v1, V2 /in V whether there is a path from v1 to v2 with weight at most W and length at most L is NP‐complete. This paper gives two approaches to meeting or approximating the length and weight constraints. The first approach is to use a pseudopolynomial‐time algorithm which determines whether a path meets the constraints. Its running time is O (n5 b log nb) where n = |V| and b is the largest length or weight. If tables with O (n3b) entries are kept then all instances of multiple constraints may be decided. Table size may be substantially decreased if one is willing to tolerate incorrect answers to rare instances. The algorithm is suitable for distributed execution. In the second approach, an objective function is defined which evaluates a path's distance from meeting the constraints. Polynomial‐time algorithms attempt to find good paths in terms of the objective function. One algorithm is at most 1.62 times worst than optimal. A notion of “average worst‐case behavior” is defined. The algorithm's “average” behavior is 1.51 times worse than optimal.

In this paper we study some link control protocols for use in point-to-multipoint communication over broadcast links. We concentrate on automatic repeat request protocols of the go-back-Ntype and define, analyze, and compare three such protocols. A major contribution of this paper is a relatively simple protocol which is easy to implement and performs very well under a wide range of conditions. Our analytical models show that this protocol performs considerably better than the other go-back-Nprotocols, particularly in environments with a large number of receivers.

There are two primary means of resource allocaUon in computer systems.One ~s the powerful mechanism of using a centrahzed resource manager to allocate the resources.An apparently weaker mechanism is for the asynchronous processes of the system to allocate resources with some type of message passing.A unifying treatment of these two methods is provided.It is shown that a managed system may be simulated by the processes using test and set instructions.As a corollary, a wide variety of synchronization algorithms may be accomplished without a manager.The simulation works correctly even m an environment where processes die in an undetectable manner.All memory cells are of s~ze at most four.Thus this general simulation provides the first known algorithm for fairly synchronizing dying processes with bounded sized memory cells.In particular, the simulation solves the/-crmcal section problem w~th test-and-set instructions operating on bounded size memory.

Algorithms for effectively routing messages from a source to multiple destination nodes in a store-and-forward computer network are studied. The focus is on minimizing the network cost (NC), which is the sum of weights of the links in the routing path. Several heuristic algorithms are studied for finding the NC minimum path (which is an NP-complete problem). Among them are variations of a minimum spanning tree (MST) heuristic and heuristics for the traveling salesman problem, both of which use global network information. Another set of heuristics examined are based on using only the shortest paths to the destinations. While the MST algorithm has the best worst case performance among all algorithms, a detailed, empirical study of the "average" performance of the algorithms on typical, randomly chosen networks reveals that simpler heuristics are almost as effective. The NC cost measure is also compared to the destination cost (DC), which is the sum of weights of the shortest path distances to all destinations. A scheme of algorithms is given which trades off between NC and DC.

In computer networks, message routing is often accomplished by network nodes using local information. The unavailability of global information intuitively makes hard routing problems virtually impossible. This paper formalizes this intuition by examining a hard (NP-complete) routing problem, the problem of multi-destination routing. It is shown that with only limited information it is impossible to optimize network utilization for the multi-destination routing problem. Moreover, it is impossible to even approximate optimality to within a specified tolerance. Several versions of this result are proved; the versions differ in terms of the amount of information available at a node, and the extent to which the problem cannot be approximated.

A new distributed algorithm is presented for dynamically determining weighted shortest paths used for message routing in computer networks. The major features of the algorithm are that the paths defined do not form transient loops when weights change and the number of steps required to find new shortest paths when network links fail is less than for previous algorithms. Specifically, the worst case recovery time is proportional to the largest number of hopshin any of the weighted shortest paths. For previous loop-free distributed algorithms this recovery time is proportional toh2.

Several algorithms are presented for the nonpreemptlve assignment of n independent tasks to m unrelated processors One algorithm requires polynomial Ume in n and m and IS at most 2x/~ times worse than optimal in the worst case This is the best polynomial-time algorithm known for scheduling such sets of tasks.An algorithm with slightly better worst case performance requires polynomial time in n but exponential ume in m This 1s the best algorithm known that requires time O(nlogn) for every fixed value of m KEY WORDS AND PHRASES nonpreemptlve schedules, worst case fimshlng time, performance ratio, unrelated processors, largest processing time CR CATEGORIES' 4 32, 4 35, 5 25, 5 39 IntroductzonThis paper presents a number of polynomial-time algorithms for the scheduling of a set of n independent tasks on m processors of different speeds.The processors are unrelated in the sense that there is no notion of a fast processor always requiring less time than a slow processor, irrespective of the task being executed.Rather, the time required for the execution of a task on a processor is a function of both the task and the processor.This models the situation in which general-purpose processors have specialized capabilities that permit them to execute certain tasks more efficiently than others.An example of this might be in a distributed system where the time requirement of a task on a processor may depend on communication costs.The decision problem of determining whether a given set of tasks can be assigned with finishing time smaller than a given bound is NP-complete [6].As a result, it seems unlikely that an algorithm can be found which runs m polynomial time and always produces the optimal assignment [3].It is thus worthwhile to investigate approximation algorithms.

Flow control is proposed as a means of obtaining an "optimal tradeoff" between low delay and high throughput in computer networks. Several versions of "optimal tradeoff" are defined based on network power. A class of algorithms which attempt to optimize network performance are investigated. These algorithms operate on the design principles of dynamic, distributed execution and use of local information. These design principles force the algorithms to be suboptimal, and we thus investigate the relative performance of each in different network configurations. Several properties of power as a network performance objective function are examined. In certain configurations, two variations of network power are unfair to certain users by not permitting them to send any messages. A version of network power ("product of powers") corrects this deficiency. Other properties discussed include the nonconvexity of the generalized power function.

The problem of optimally choosing message rates for users of a store-and-forward network is analyzed. Multiple users sharing the links of the network each attempt to adjust their message rates to achieve an ideal network operating point or an "ideal tradeoff point between high throughput and low delay." Each user has a fixed path or virtual circuit. In this environment, a basic definition of "ideal delay-throughput tradeoff" is given and motivated. This definition concentrates on a fair allocation of network resources at network bottlenecks. This "ideal policy" is implemented via a decentralized algorithm that achieves the unique set of optimal throughputs. All sharers constrained by the same bottleneck are treated fairly by being assigned equal throughputs. A generalized definition of ideal tradeoff is then introduced to provide more flexibility in the choice of message rates. With this definition, the network may accommodate users with different types of message traffic. A transformation technique reduces the problem of optimizing this performance measure to the problem of optimizing the basic measure.

Flow control in store-and-forward computer networks is appropriate for decentralized execution. A formal description of a class of "decentralized flow control algorithms" is given. The feasibility of maximizing power with such algorithms is investigated. On the assumption that communication links behave likeM/M/1servers it is shown that no "decentralized flow control algorithm" can maximize network power. Power has been suggested in the literature as a network performance objective. It is also shown that no objective based only on the users' throughputs and average delay is decentralizable. Finally, a restricted class of algorithms cannot even approximate power.

We study the scheduling of different types of tasks on different types of processors. If there are k types of tasks and $m_i $, identical processors for tasks of type i, the finishing time of any list schedule is at most $k + 1 - (1/ \max (m_1 , \cdots ,m_k ))$ times worse than the optimal schedule. This bound is best possible. If the processors execute at different speeds then the performance of any list schedule (relative to the optimal schedule) is bounded by k plus the maximum ratio between the speeds of any two processors of the same type.