We prove a previously stated but incorrectly proved theorem: there is a diameter-3 graph in which replacing any edge $\{v, w\}$ of the graph with $\{v, w'\}$, for any vertex $w'$, does not decrease the total sum of distances from $v$ to all other nodes (a property called sum equilibrium).

We study a natural network creation game, in which each node locally tries to minimize its local diameter or its local average distance to other nodes by swapping one incident edge at a time. The central question is what structure the resulting equilibrium graphs have, in particular, how well they globally minimize diameter. For the local-average-distance version, we prove an upper bound of $2^{O(\sqrt{\lg n})}$, a lower bound of 3, and a tight bound of exactly 2 for trees, and give evidence of a general polylogarithmic upper bound. For the local-diameter version, we prove a lower bound of $\Omega(\sqrt{n})$ and a tight upper bound of 3 for trees. The same bounds apply, up to constant factors, to the price of anarchy. Our network creation games are closely related to the previously studied unilateral network creation game. The main difference is that our model has no parameter $\alpha$ for the link creation cost, so our results effectively apply for all values of $\alpha$ without additional effort; furthermore, equilibrium can be checked in polynomial time in our model, unlike in previous models. Our perspective enables simpler proofs that get at the heart of network creation games.

The notion of vertex sparsification (in particular cut-sparsification) is introduced in, where it was shown that for any graph G = (V, E) and any subset of k terminals K ⊂ V, there is a polynomial time algorithm to construct a graph H = (K, EH) on just the terminal set so that simultaneously for all cuts (A,K-A), the value of the minimum cut in G separating A from K-A is approximately the same as the value of the corresponding cut in H. Then approximation algorithms can be run directly on H as a proxy for running on G. We give the first super-constant lower bounds for how well a cut-sparsifier H can simultaneously approximate all minimum cuts in G. We prove a lower bound of Ω(log1/4k) this is polynomially-related to the known upper bound of O(log k/log log k). Independently, a similar lower bound is given in. This is an exponential improvement on the Ω(log log k) bound given in which in fact was for a stronger vertex sparsification guarantee, and did not apply to cut sparsifiers. Despite this negative result, we show that for many natural optimization problems, we do not need to incur a multiplicative penalty for our reduction. Roughly, we show that any rounding algorithm which also works for the O-extension relaxation can be used to construct good vertex-sparsifiers for which the optimization problem is easy. Using this, we obtain optimal O(log k)-competitive Steiner oblivious routing schemes, which generalize the results in. We also demonstrate that for a wide range of graph packing problems (which includes maximum concurrent flow, maximum multiflow and multicast routing, among others, as a special case), the integrality gap of the linear program is always at most O(log k) times the integrality gap restricted to trees. Lastly, we use our ideas to give an efficient construction for vertex-sparsifiers that match the current best existential results - this was previously open. Our algorithm makes novel use of Earth-mover constraints.

We study a natural network creation game, in which each node locally tries to minimize its local diameter or its local average distance to other nodes, by swapping one incident edge at a time. The central question is what structure the resulting equilibrium graphs have, in particular, how well they globally minimize diameter. For the local-average-distance version, we prove an upper bound of 2O(√ lg n), a lower bound of 3, a tight bound of exactly 2 for trees, and give evidence of a general polylogarithmic upper bound. For the local-diameter version, we prove a lower bound of Ω(√ n), and a tight upper bound of 3 for trees. All of our upper bounds apply equally well to previously extensively studied network creation games, both in terms of the diameter metric described above and the previously studied price of anarchy (which are related by constant factors). In surprising contrast, our model has no parameter α for the link creation cost, so our results automatically apply for all values of alpha without additional effort; furthermore, equilibrium can be checked in polynomial time in our model, unlike previous models. Our perspective enables simpler and more general proofs that get at the heart of network creation games.

Suppose we are given a graph G = (V, E) and a set of terminals K ⊂ V. We consider the problem of constructing a graph H = (K, EH) that approximately preserves the congestion of every multicommodity flow with endpoints supported in K. We refer to such a graph as a flow sparsifier. We prove that there exist flow sparsifiers that simultaneously preserve the congestion of all multicommodity flows within an O(log k / log log k)-factor where |K| = k. This bound improves to O(1) if G excludes any fixed minor. This is a strengthening of previous results, which consider the problem of finding a graph H = (K, EH) (a cut sparsifier) that approximately preserves the value of minimum cuts separating any partition of the terminals. Indirectly our result also allows us to give a construction for better quality cut sparsifiers (and flow sparsifiers). Thereby, we immediately improve all approximation ratios derived using vertex sparsification in [14].

Geographic routing is a family of routing algorithms that uses geographic point locations as addresses for the purposes of routing. Such routing algorithms have proven to be both simple to implement and heuristically effective when applied to wireless sensor networks. Greedy routing is a natural abstraction of this model in which nodes are assigned virtual coordinates in a metric space, and these coordinates are used to perform point-to-point routing. Here we resolve a conjecture of Papadimitriou and Ratajczak that every 3-connected planar graph admits a greedy embedding into the Euclidean plane. This immediately implies that all 3-connected graphs that exclude K3.3as a minor admit a greedy embedding into the Euclidean plane. Additionally, we provide the first non-trivial examples of graphs that admit no such embedding. These structural results provide efficiently verifiable certificates that a graph admits a greedy embedding or that a graph admits no greedy embedding into the Euclidean plane.

Hat problems have become a popular topic in recreational mathematics. In a typical hat problem, each of n players tries to guess the color of the hat he or she is wearing by looking at the colors of the hats worn by some of the other players. In this paper we consider several variants of the problem, united by the common theme that the guessing strategies are required to be deterministic and the objective is to maximize the number of correct answers in the worst case. We also summarize what is currently known about the worst-case analysis of deterministic hat guessing problems with a finite number of players.

In this talk, we will describe several issues that impact the performance, reliability, and security of dynamic applications running over the Internet. We will then describe some of the techniques used by Akamai to overcome these problems, as well as six basic design principles for achieving reliability in a large-scale, distributed, real-time system operating in an unreliable environment such as the Internet. The talk will be introductory in nature.

In this paper, we devise a special 1-error-correcting code that enables us to embed the graph product of an $N/\log N$-node hypercube and a $\log N$-node complete graph into in an N-node hypercube with constant load, dilation, and congestion. We apply the result to construct improved embeddings of trees and other structures in a hypercube, and to design more efficient and robust algorithms for reconfiguring a hypercube around random or worst-case faults. The result has also been used subsequently by others to show that the N-node hypercube can emulate all N-node planar graphs with constant slowdown.

We consider distributed algorithms for maximizing throughput in a network of clients and servers, modeled as a bipartite graph. We seek algorithms and lower bounds for decentralized algorithms in which each participant has only local knowledge about the state of itself and its neighbors. Our problem is analogous to recent work on oblivious routing [M. Bienkowski, M. Korzeniowski, and H. Räcke, Proceedings of the $15$th Annual ACM Symposium on Parallel Algorithms and Architectures, 2003, pp. 24–33, C. Harrelson, K. Hildrum, and S. Rao, Proceedings of the $15$th Annual ACM Symposium on Parallel Algorithms and Architectures, 2003, pp. 34–43, H. Räcke, Proceedings of the $43$rd Annual IEEE Symposium on Foundations of Computer Science, 2002, pp. 43–52] but with the objective of maximizing throughput rather than minimizing congestion. In contrast to that work, we prove a strong lower bound (polynomial in n, the size of the graph) on the competitive ratio of any oblivious algorithm. This is accompanied by simple algorithms achieving upper bounds which are tight in terms of $\OPT$, the maximum throughput achievable by an omniscient algorithm, and are also tight in terms of m, the number of servers. Finally, we investigate an online version of the problem, in a restricted model which requires that clients, upon becoming active, must remain so for at least $log(n)$ time steps. In contrast to our primarily negative results in the oblivious case, here we present an algorithm which is constant-competitive. Our lower bounds justify the intuition, implicit in earlier work on the subject [B. Awerbuch and Y. Azar, Proceedings of the $35$th Annual IEEE Symposium on Foundations of Computer Science, 1994, pp. 240–249], that some such restriction (i.e., requiring some stability in the demand pattern over time) is necessary in order to achieve a constant—or even polylogarithmic—competitive ratio.

Oblivious routing algorithms for general undirected networks were introduced by Räcke [2002], and this work has led to many subsequent improvements and applications. Comparatively little is known about oblivious routing in general directed networks, or even in undirected networks with node capacities. We present the first nontrivial upper bounds for both these cases, providing algorithms for k -commodity oblivious routing problems with competitive ratio O (√ k log( n )) for undirected node-capacitated graphs and O (√ k n 1/4 log( n )) for directed graphs. In the special case that all commodities have a common source or sink, our upper bound becomes O (√ n log( n )) in both cases, matching the lower bound up to a factor of log( n ). The lower bound (which first appeared in Azar et al. [2003]) is obtained on a graph with very high degree. We show that, in fact, the degree of a graph is a crucial parameter for node-capacitated oblivious routing in undirected graphs, by providing an O (Δ polylog( n ))-competitive oblivious routing scheme for graphs of degree Δ. For the directed case, however, we show that the lower bound of Ω(√ n ) still holds in low-degree graphs. Finally, we settle an open question about routing problems in which all commodities share a common source or sink. We show that even in this simplified scenario there are networks in which no oblivious routing algorithm can achieve a competitive ratio better than Ω(log n ).

We introduce semi-oblivious routing, a generalization of oblivious routing in which multicommodity flows must be routed using a polynomial-sized set of paths which is predefined by the algorithm before the demand matrix for the flow problem is revealed. Our results, which are primarily negative, exclude the possibility of constant-competitive semi-oblivious routing schemes, even when the network is a grid or a seriesparallel graph. We provide an even stronger lower bound on the congestion of constant-bend routing schemes in the grid.

Oblivious routing algorithms for general undirected networks were introduced by Räcke, and this work has led to many subsequent improvements and applications. More precisely, Räcke showed that there is an oblivious routing algorithm with polylogarithmic competitive ratio (w.r.t. edge congestion) for any undirected graph. Comparatively little positive results are known about oblivious routing in general directed networks. Using a novel approach, we present the first oblivious routing algorithm which is O(log2 n) competitive with high probability in directed graphs given that the demands are chosen randomly from a known demand-distribution. On the other hand, we show that no oblivious routing algorithm can be o(logn/log log n) competitive even with constant probability in general directed graphs.Our routing algorithms are not oblivious in the traditional definition, but we add the concept of demand-dependence, i.e., the path chosen for an s-t pair may depend on the demand between s and t. This concept that still preserves that routing decisions are only based on local information proves very powerful in our randomized demand model.Finally, we show that our approach for designing competitive oblivious routing algorithms is quite general and has applications in other contexts like stochastic scheduling.

We consider price-setting algorithms for a simple market in which a seller has an unlimited supply of identical copies of some good, and interacts sequentially with a pool of n buyers, each of whom wants at most one copy of the good. In each transaction, the seller offers a price between 0 and 1, and the buyer decides whether or not to buy, by comparing the offered price to his privately-held valuation for the good. The price offered to a given buyer may be influenced by the outcomes of prior transactions, but each individual buyer participates only once. In this setting, what is the value of knowing the demand curve? In other words, how much revenue can an uninformed seller expect to obtain, relative to a seller with prior information about the buyers' valuations? The answer depends on how the buyers' valuations are modeled. We analyze three cases - identical, random, and worst-case valuations - in each case deriving upper and lower bounds which match within a sublogarithmic factor.

Motivated by applications to web caching and other distributed server architectures, we analyze load balancing algorithms from the standpoint of spread, which measures the number of different assignments an item receives across multiple iterations of the algorithm on varying load distributions. Minimizing spread while balancing load is important in order to make efficient use of server resources such as memory and in order to minimize service latency. In the paper, we consider both on-line and off-line versions of the problem. Most importantly, we describe on-line load balancing algorithms with very low spread, which means that the assignments made for most items do not change even when the loads associated with the items do change. This means that load balancing is an example of a problem for which it is possible to find highly stable (or, consistent) on-line algorithms --- i.e. algorithms for which the output changes only slightly (with high probability) even if the inputs change dramatically.This paper is dedicated to the memory of Danny Lewin, who pioneered the notion of consistent hashing and its applications to load balancing and content distribution on the Internet. Danny's ideas furnished many of the underpinnings for the problem and algorithms studied herein.

No abstract available.

In this talk, we will give an overview of how content is distributed on the internet, with an emphasis on the approach being used by Akamai. We will describe some of the technical challenges involved in operating a network of thousands of content servers across multiple geographies on behalf of thousands of customers. The talk will be introductory in nature and should be accessible to a broad audience.

In this paper, we analyze the behavior of packet-switched communication networks in which packets arrive dynamically at the nodes and are routed in discrete time steps across the edges. We focus on a basic adversarial model of packet arrival and path determination for which the time-averaged arrival rate of packets requiring the use of any edge is limited to be less than 1. This model can reflect the behavior of connection-oriented networks with transient connections (such as ATM networks) as well as connectionless networks (such as the Internet). We concentrate on greedy (also known as work-conserving) contention-resolution protocols. A crucial issue that arises in such a setting is that of stability —will the number of packets in the system remain bounded, as the system runs for an arbitrarily long period of time? We study the universal stability of network (i.e., stability under all greedy protocols) and universal stability of protocols (i.e., stability in all networks). Once the stability of a system is granted, we focus on the two main parameters that characterize its performance: maximum queue size required and maximum end-to-end delay experienced by any packet. Among other things, we show: (i) There exist simple greedy protocols that are stable for all networks. (ii) There exist other commonly used protocols (such as FIFO) and networks (such as arrays and hypercubes) that are not stable. (iii) The n -node ring is stable for all greedy routing protocols (with maximum queue-size and packet delay that is linear in n ). (iv) There exists a simple distributed randomized greedy protocol that is stable for all networks and requires only polynomial queue size and polynomial delay. Our results resolve several questions posed by Borodin et al., and provide the first examples of (i) a protocol that is stable for all networks, and (ii) a protocol that is not stable for all networks.

The Lovász local lemma (LLL) is a powerful tool that is increasingly playing a valuable role in computer science. The original lemma was nonconstructive; a breakthrough of Beck and its generalizations (due to Alon and Molloy and Reed) have led to constructive versions. However, these methods do not capture some classes of applications of the LLL. We make progress on this by providing algorithmic approaches to two families of applications of the LLL. The first provides constructive versions of certain applications of an extension of the LLL (modeling, e.g., hypergraph-partitioning and low-congestion routing problems); the second provides new algorithmic results on constructing disjoint paths in graphs. Our results can also be seen as constructive upper bounds on the integrality gap of certain packing problems. One common theme of our work is a "gradual rounding" approach.

Many multiprocessor systems have the ability to broadcast and/or multicast information efficiently.However, this ability is often overlooked when designing algorithms for these systems.In this paper, we introduce a new compression technique that uses efficient multicasting to significantly reduce the amount of information communicated during parallel and distributed computation, resulting in significantly faster algorithms for Fast Fourier Transforms and sorting on shared memory parallel models with limited bandwidth.These algorithms demonstrate the importance of taking advantage of efficient multicasting.The compression technique uses a new, natural variant of Ramsey theory, which may be of independent interest. gle point-to-point message must on average traverse p/2edges, but a data item can be multicast to any subset *A portion of this research was performed while the first author

A central issue in the design of modern communication networks is that of providing performance guarantees. This issue is particularly important if the networks support real-time traffic such as voice and video. The most critical performance parameter to bound is the delay experienced by a packet as it travels from its source to its destination. We study dynamic routing in a connection-oriented packet-switching network. We consider a network with arbitrary topology on which a set of sessions is defined. For each session i, packets are injected at a rate r i to follow a predetermined path of length d i . Due to limited bandwidth, only one packet at a time may advance on an edge (link). Session paths may overlap subject to the constraint that the total rate of sessions using any particular edge is at most $1-\varepsilon$ for any constant $\varepsilon \in (0,1)$. We address the problem of scheduling the sessions at each switch, so as to minimize worst-case packet delay and queue buildup at the switches. We show the existence of a periodic schedule that achieves a delay bound of O(1/r i +d i ) with only constant-size queues at the switches. This bound is asymptotically optimal for periodic schedules. A consequence of this result is an asymptotically optimal schedule for the static routing problem, wherein all packets are present at the outset. We obtain a delay bound of O(c i + d i ) for packets on path P i , where d i is the number of edges in P i and c i is the maximum congestion along edges in P i . This improves upon the previous known bound of O(c + d), where d = max i d i and c = max i c i . We also present a simple distributed algorithm that, with high probability, delivers every session-i packet to its destination within O(1/r i +d i \log(m/r min )) steps of its injection, where r min is the minimum session rate and m is the number of edges in the network. Our results can be generalized to (leaky-bucket constrained) bursty traffic, where session i tolerates a burst size of b i . In this case, our delay bounds become O(b i /r i + d i ) and O(b i /r i +d i \log(m/r min )), respectively.

In large distributed networks of computers, it is often the case that a subset of machines wants to cooperate to perform a task. Before they can do so, these machines need to learn of the existence of each other. In this paper we are interested in distributed algorithms whereby machines in a network learn of other machines in the network by making queries to machines they already know. The algorithms should be efficient both in terms of the time required and in terms of the total network communication required until all machines have discovered all other machines. We propose a very simple algorithm called Name-Dropper whereby all machines learn about each other within O(log 2 n) rounds, where n is the number of machines in the network. The total number of connections required is O(n log 2 n), and the total number of pointers which must be communicated is O(n 2 log 2 n). Each of the preceding bounds is optimal to within polylogarithmic factors. Contact author: Mor Harc...

A number of current technologies allow for the determination of interatomic distance information in structures such as proteins and RNA. Thus, the reconstruction of a three-dimensional set of points using information about its interpoint distances has become a task of basic importance in determining molecular structure. The distance measurements one obtains from techniques such as NMR are typically sparse and error-prone, greatly complicating the reconstruction task. Many of these errors result in distance measurements that can be safely assumed to lie within certain fixed tolerances. But a number of sources of systematic error in these experiments lead to inaccuracies in the data that are very hard to quantify; in effect, one must treat certain entries of the measured distance matrix as being arbitrarily “corrupted.” The existence of arbitrary errors leads to an interesting sort of error-correction problem—how many corrupted entries in a distance matrix can be efficiently corrected to produce a consistent three-dimensional structure? For the case of an n × n matrix in which every entry is specified, we provide a randomized algorithm running in time O(n log n) that enumerates all structures consistent with at most (1/2-ε)n errors per row, with high probability. In the case of randomly located errors, we can correct errors of the same density in a sparse matrix-one in which only a β fraction of the entries in each row are given, for any constant βgt;0.

In this paper, we establish max-flow min-cut theorems for several important classes of multicommodity flow problems.In particular, we show that for any n-node multicommodity flow problem with uniform demands, the max-flow for the problem is within an O(log n) factor of the upper bound implied by the min-cut.The result (which is existentially optimal) establishes an important analogue of the famous 1-commodity max-flow min-cut theorem for problems with multiple commodities.The result also has substantial applications to the field of approximation algorithms.For example, we use the flow result to design the first polynomial-time (polylog n-times-optimal) approximation algorithms for well-known NP-hard optimization problems such as graph partitioning, min-cut linear arrangement, crossing number, VLSI layout, and minimum feedback arc set.Applications of the flow results to path routing problems, network reconfiguration, communication in distributed networks, scientific computing and rapidly mixing Markov chains are also described in the paper.

In this paper we describe methods for mitigating the degradation in performance caused by high latencies in parallel and distributed networks. For example, given any "dataflow" type of algorithm that runs in T steps on an n-node ring with unit link delays, we show how to run the algorithm in O(T) steps on any n-node bounded-degree connected network with average link delay O(1). This is a significant improvement over prior approaches to latency hiding, which require slowdowns proportional to the maximum link delay. In the case when the network has average link delay $\dave$, our simulation runs in $O(\sqrt{\dave} T)$ steps using $n/\sqrt{\dave}$ processors, thereby preserving efficiency. We also show how to efficiently simulate an n X n array with unit link delays using slowdown $\tilde O(\dave^{2/3})$ on a two-dimensional array with average link delay $\dave$. Last, we present results for the case in which large local databases are involved in the computation.

Tree-structured computations are relatively easy to process in parallel. As leaf processes are recursively spawned they can be assigned to independent processors in a multicomputer network. However, to achieve good performance the on-line mapping algorithm must maintain load balance, i.e., distribute processes equitably among processors. Additionally, the algorithm itself must be distributed in nature, and process allocation must be completed via message-passing with minimal communication overhead. This paper investigates bounds on the performance of deterministic and randomized algorithms for on-line tree embeddings. In particular, we study trade-offs between computation overhead (load imbalance) and communication overhead (message congestion). We give a simple technique to derive lower bounds on the congestion that any on-line allocation algorithm must incur in order to guarantee load balance. This technique works for both randomized and deterministic algorithms. We prove that the advantage of randomization is limited. Optimal bounds are achieved for several networks, including multidimensional grids and butterflies.

This paper presents an analysis of the following load balancing algorithm. At each step, each node in a network examines the number of tokens at each of its neighbors and sends a token to each neighbor with at least 2d+1 fewer tokens, where d is the maximum degree of any node in the network. We show that within $O(\Delta / \alpha)$ steps, the algorithm reduces the maximum difference in tokens between any two nodes to at most $O((d^2 \log n)/\alpha)$, where $\Delta$ is the global imbalance in tokens (i.e., the maximum difference between the number of tokens at any node initially and the average number of tokens), n is the number of nodes in the network, and $\alpha$ is the edge expansion of the network. The time bound is tight in the sense that for any graph with edge expansion $\alpha$, and for any value $\Delta$, there exists an initial distribution of tokens with imbalance $\Delta$ for which the time to reduce the imbalance to even $\Delta/2$ is at least $\Omega(\Delta/\alpha)$. The bound on the final imbalance is tight in the sense that there exists a class of networks that can be locally balanced everywhere (i.e., the maximum difference in tokens between any two neighbors is at most 2d), while the global imbalance remains $\Omega((d^2 \log n) / \alpha)$. Furthermore, we show that upon reaching a state with a global imbalance of $O((d^2 \log n)/\alpha)$, the time for this algorithm to locally balance the network can be as large as $\Omega(n^{1/2})$. We extend our analysis to a variant of this algorithm for dynamic and asynchronous networks. We also present tight bounds for a randomized algorithm in which each node sends at most one token in each step.

We study networks that can sort n, items even when a large number of the comparators in the network are faulty. We restrict our attention to networks that consist of registers, comparators, and replicators. ( Replicators are used to copy an item from one register to another, and they are assumed to be fault free.) We consider the scenario of both random and worst-case comparator faults, and we follow the general model of destructive comparator failure proposed by Assaf and Upfal [ Proc. 31st IEEE Symposium on Foundations of Computer Science, St. Louis, MO, 1990, pp. 275--284] in which the two outputs of a faulty comparator can fail independently of each other. In the case of random faults, Assaf and Upfal showed how to construct a network with O(n log 2 n ) comparators that (with high probability) can sort n items even if a constant fraction of the comparators are faulty. Whether the bound on the number of comparators can be improved (to, say, O(n log n)) for sorting (or merging) has remained an interesting open question. We resolve this question in this paper by proving that any n-item sorting or merging network which can tolerate a constant fraction of random failures has $\Omega(n \log^2 n)$ comparators. In the case of worst-case faults, we show that $\Omega(kn \log n)$ comparators are necessary to construct a sorting or merging network that can tolerate up to k worst-case faults. We also show that this bound is tight for k = O(log n). The lower bound is particularly significant since it formally proves that the cost of being tolerant to worst-case failures is very high. Both the lower bound for random faults and the lower bound for worst-case faults are the first nontrivial lower bounds on the size of a fault-tolerant sorting or merging network.

Article Free Access Share on Protein folding in the hydrophobic-hydrophilic (HP) is NP-complete Authors: Bonnie Berger 2-389, Mathematics Dept. and Lab. for Computer Science, MIT, Cambridge, MA 2-389, Mathematics Dept. and Lab. for Computer Science, MIT, Cambridge, MAView Profile , Tom Leighton 2-377, Mathematics Dept. and Lab. for Computer Science, MIT, Cambridge, MA 2-377, Mathematics Dept. and Lab. for Computer Science, MIT, Cambridge, MAView Profile Authors Info & Claims RECOMB '98: Proceedings of the second annual international conference on Computational molecular biologyMarch 1998 Pages 30–39https://doi.org/10.1145/279069.279080Published:01 March 1998Publication History 51citation1,897DownloadsMetricsTotal Citations51Total Downloads1,897Last 12 Months157Last 6 weeks14 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

We consider N processors communicating unidirectionally over a closed transmission channel, or ring. Each message is assembled into a fixed-length packet. Packets to be sent are generated at random times by the processors, and the transit times spent by packets on the ring are also random. Packets being forwarded, i.e., packets already on the ring, have priority over waiting packets. The objective of this paper is to analyze packet waiting times under a greedy policy within a discrete Markov model that retains the overall structure of a practical system but is simple enough so that explicit results can be proved. Independent, identical Bernoulli processes model message generation at the processors, and independently and identically distributed (i.i.d.) geometric random variables model the transit times. Our emphasis is on asymptotic behavior for large ring sizes, N, when the respective rate parameters have the scaling $\lambda /N$ and $\mu /N$. Our main result shows that, if the traffic intensity is fixed at $\rho = \lambda / \mu < 1$, then as $N \to \infty$ the expected time a message waits to be put on the ring is bounded by a constant. This result verifies that the expected waiting time under the greedy policy is within a constant factor of that under an optimal policy.

In this paper, we analyze the fault tolerance of several bounded-degree networks that are commonly used for parallel computation. Among other things, we show that an N-node butterfly network containing $N^{1-\epsilon}$ worst-case faults (for any constant $\epsilon > 0$) can emulate a fault-free butterfly of the same size with only constant slowdown. The same result is proved for the shuffle-exchange network. Hence, these networks become the first connected bounded-degree networks known to be able to sustain more than a constant number of worst-case faults without suffering more than a constant-factor slowdown in performance. We also show that an N-node butterfly whose nodes fail with some constant probability p can emulate a fault-free network of the same type and size with a slowdown of 2 O(log * N) . These emulation schemes combine the technique of redundant computation with new algorithms for routing packets around faults in hypercubic networks. We also present techniques for tolerating faults that do not rely on redundant computation. These techniques tolerate fewer faults but are more widely applicable because they can be used with other networks such as binary trees and meshes of trees.

This paper provides an analysis of a natural d-round tournament over n = 2 d players and demonstrates that the tournament possesses a surprisingly strong ranking property. The ranking property of this tournament is used to design efficient sorting algorithms for several models of parallel computation: a comparator network of depth $c\\cdot\lg n$, $c\approx 7.44$, that sorts the vast majority of the n! possible input permutations; an $O(\lg n)$-depth hypercubic comparator network that sorts the vast majority of permutations; a hypercubic sorting network with nearly logarithmic depth; an $O(\lg n)$-time randomized sorting algorithm for any hypercubic machine (other such algorithms have been previously discovered, but this algorithm has a significantly smaller failure probability than any previously known algorithm); and a randomized algorithm for sorting nO (m)-bit records on an $(n\lg n)$-node omega machine in $O(m+\lg n)$ bit steps.

A central issue in the design of modern communication networks is that of providing performance guarantees. This issue is particularly important if the networks support read-time traffic such as voice and video. The most critical performance parameter to bound is the delay experienced by a packet as it travels from its source to its destination. We study dynamic routing in a connection-oriented packet-switching network. We consider a network with arbitrary topology on which a set of sessions is defined. For each session i, packets are injected at a rate r/sub i/ to follow a predetermined path of length d/sub i/. Due to limited bandwidth, only one packet at a time may advance on an edge. Session paths may overlap subject to the constraint that the total rate of sessions using any particular edge is less than 1. We address the problem of scheduling the sessions at each switch, so as to minimize worst-case packet delay and queue buildup at the switches. We show the existence of an asymptotically-optimal schedule that achieves a delay bound of O(1/r/sub i/+d/sub i/) with only constant-size queues at the switches. We also present a simple distributed algorithm that, with high probability, delivers every session-i packet to its destination within O(1/r/sub i/+d/sub i/ log(m/r/sub min/)) steps of its injection, where r/sub min/ is the minimum session rate, and m is the number of edges in the network. Our results can be generalized to (leaky-bucket constrained) bursty traffic, where session i tolerates a burst size of b/sub i/. In this case, our delay bounds become O(b/sub i//r/sub i/+d/sub i/) and O(b/sub i//r/sub i/+d/sub i/ log(m/r/sub min/)), respectively.

We describe a family of caching protocols for distrib-uted networks that can be used to decrease or eliminate the occurrence of hot spots in the network. Our protocols are particularly designed for use with very large networks such as the Internet, where delays caused by hot spots can be severe, and where it is not feasible for every server to have complete information about the current state of the entire network. The protocols are easy to implement using existing network protocols such as TCP/IP, and require very little overhead. The protocols work with local control, make efficient use of existing resources, and scale gracefully as the network grows. Our caching protocols are based on a special kind of hashing that we call consistent hashing. Roughly speaking, a consistent hash function is one which changes minimally as the range of the function changes. Through the development of good consistent hash functions, we are able to develop caching protocols which do not require users to have a current or even consistent view of the network. We believe that consistent hash functions may eventually prove to be useful in other applications such as distributed name servers and/or quorum systems.

In this paper, we study the problem of emulating T G steps of an N G -node guest network, G, on an N H -node host network, H.We call an emulation work-preserving if the time required by the host, T H , is O(T G N G /N H ), because then both the guest and host networks perform the same total work (i.e., processor-time product), ⌰(T G N G ), to within a constant factor.We say that an emulation occurs in real-time if T H ϭ O(T G ), because then the host emulates the guest with constant slowdown.In addition to describing several work-preserving and real-time emulations, we also provide a general model in which lower bounds can be proved.Some of the more interesting and diverse consequences of this work include:(1) a proof that a linear array can emulate a (much larger) butterfly in a work-preserving fashion, but that a butterfly cannot emulate an expander (of any size) in a work-preserving fashion,(2) a proof that a butterfly can emulate a shuffle-exchange network in a real-time work-preserving fashion, and vice versa,(3) a proof that a butterfly can emulate a mesh (or an array of higher, but fixed, dimension) in a real-time work-preserving fashion, even though any O(1)-to-1 embedding of an N-node mesh in an N-node butterfly has dilation ⍀(log N), and (4) simple O(N 2 /log 2 N)-area and O(N 3/ 2 /log 3/2 N)-volume layouts for the N-node shuffle-exchange network.

In this paper, we consider the problem of interprocessor communication on parallel computers that have optical communication networks. We consider the completely connected optical-communication parallel computer (OCPC), which has a completely connected optical network, and also the mesh-of-optical-buses parallel computer (MOB-PC), which has a mesh of optical buses as its communication network. The particular communication problem that we study is that of realizing an h-relation. In this problem, each processor has at most h messages to send and at most h messages to receive. It is clear that any 1-relation can be realized in one communication step on an OCPC. However, the best previously known p-processor OCPC algorithm for realizing an arbitrary h-relation for h > 1 requires $\Theta(h + \log p)$ expected communication steps. (This algorithm is due to Valiant and is based on earlier work of Anderson and Miller.) Valiant's algorithm is optimal only for $h=\Omega(\log p)$, and it is an open question of Geréb-Graus and Tsantilas whether there is a faster algorithm for h=o(log p). In this paper, we answer this question in the affirmative and we extend the range of optimality by considering the case in which $h\leq \log p$. In particular, we present a $\Theta(h + \log\log p)$-communication-step randomized algorithm that realizes an arbitrary h-relation on a p-processor OCPC. We show that if $h\leq \log p$, then the failure probability can be made as small as $p^{-\alpha}$ for any positive constant $\alpha$. We use the OCPC algorithm as a subroutine in a $\Theta(h + \log\log p)$-communication-step randomized algorithm that realizes an arbitrary h-relation on a $p\times p$-processor MOB-PC. Once again, we show that if $h\leq \log p$, then the failure probability can be made as small as $p^{-\alpha}$ for any positive constant $\alpha$.

We study the parallel scheduling problem for a new modality of parallel computing: having one workstation "steal cycles" from another. We focus on a draconian mode of cycle-stealing, in which the owner of workstation B allows workstation A to take control of B's processor whenever it is idle, with the promise of relinquishing control immediately upon demand. The typically high communication overhead for supplying workstation B with work and receiving its results militates in favor of supplying B with large amounts of work at a time; the risk of losing work in progress when the owner of B reclaims the workstation militates in favor of supplying B with a sequence of small packets of work. The challenge is to balance these two pressures in a way that maximizes the amount of work accomplished. We formulate two models of cycle-stealing. The first attempts to maximize the expected work accomplished during a single episode, when one knows the probability distribution of the return of B's owner. The second attempts to match the productivity of an omniscient cycle-stealer, when one knows how much work that stealer can accomplish. We derive optimal scheduling strategies for sample scenarios within each of these models.

This paper presents a secure (tamper-resistant) algorithm for watermarking images, and a methodology for digital watermarking that may be generalized to audio, video, and multimedia data. We advocate that a watermark should be constructed as an independent and identically distributed (i.i.d.) Gaussian random vector that is imperceptibly inserted in a spread-spectrum-like fashion into the perceptually most significant spectral components of the data. We argue that insertion of a watermark under this regime makes the watermark robust to signal processing operations (such as lossy compression, filtering, digital-analog and analog-digital conversion, requantization, etc.), and common geometric transformations (such as cropping, scaling, translation, and rotation) provided that the original image is available and that it can be successfully registered against the transformed watermarked image. In these cases, the watermark detector unambiguously identifies the owner. Further, the use of Gaussian noise, ensures strong resilience to multiple-document, or collusional, attacks. Experimental results are provided to support these claims, along with an exposition of pending open problems.

In this paper we analyze the behavior of communication networks in which packets are generated dynamically at the nodes and routed in discrete time steps across the edges. We focus on a basic adversarial model of packet generation and path determination for which the time-averaged injection rate of packets requiring the use of any edge is limited to be less than 1. A crucial issue that arises in such a setting is that of stability-will the number of packets in the system remain bounded, as the system runs for an arbitrarily long period of time? Among other things, we show: (i) There exist simple greedy protocols that are stable for all networks. (ii) There exist other commonly-used protocols (such as FIFO) and networks (such as arrays and hypercubes) that are not stable. (iii) The n-node ring is stable for all greedy routing protocols (with maximum queue-size and packet delay that is linear in n). (iv) There exists a simple distributed randomized greedy protocol that is stable for all networks and requires only polynomial queue size. Our results resolve several questions posed by Borodin et al. and provide the first examples of (i) a protocol that is stable for all networks, and (ii) a protocol that is not stable for all networks.

We describe a digital watermarking method for use in audio, image, video and multimedia data. We argue that a watermark must be placed in perceptually significant components of a signal if it is to be robust to common signal distortions and malicious attack. However, it is well known that modification of these components can lead to perceptual degradation of the signal. To avoid this, we propose to insert a watermark into the spectral components of the data using techniques analogous to spread spectrum communications, hiding a narrow band signal in a wideband channel that is the data. The watermark is difficult for an attacker to remove, even when several individuals conspire together with independently watermarked copies of the data. It is also robust to common signal and geometric distortions such as digital-to-analog and analog-to-digital conversion, resampling, quantization, dithering, compression, rotation, translation, cropping and scaling. The same digital watermarking algorithm can be applied to all three media under consideration with only minor modifications, making it especially appropriate for multimedia products. Retrieval of the watermark unambiguously identifies the owner, and the watermark can be constructed to make counterfeiting almost impossible. We present experimental results to support these claims.

) Matthew Andrews Tom Leighton y P. Takis Metaxas z Lisa Zhang x Abstract In this paper we describe methods for mitigating the degradation in performance caused by high latencies in parallel and distributed networks. Our approach is similar in spirit to the "complementary slackness" method of latency hiding, but has the advantage that the slackness does not need to be provided by the programmer, and that large slowdowns are not needed in order to hide the latency. Our approach is also similar in spirit to the latency hiding methods of [2], but is not restricted to memoryless dataflow types of programs. Most of our analysis is centered on the simulation of unit-delay rings on networks of workstations (NOWs) with arbitrary delays on the links. For example, given any collection of operations (including updates of large local memories or databases) that runs in t steps on a ring of n workstations with unit link delays, we show how to perform the same collection of operations in ...

In this paper we describe methods for mitigating the degradation in performance caused by high latencies in parallel and distributed networks.Our approach is similar in spirit to the "complementary slackness" technique for latency hiding but has the advantage that the slackness does not need to be provided by the programmer and that large slowdowns are not needed in order to hide the latency.For example, given any algorithm that runs in T steps on an n-node ring with unit link delays, we show how to run the algorithm in O(T) steps on any n-node bounded-degree connected network with average link delay 0(1 ).This is a significant improvement over prior approaches to latency hiding, which require slowdowns proportional to the maximum link delay (which can be quite large in comparison to the average delay).In the case when the network has average link delay L&, our simulation runs in O(&Z') steps using n/G processors, thereby preserving efficiency.We also show how to simulate an n x n array with unit link delays using slowdown O(df& log513 n) Q '2/3 log-sla n)-nodearray with average link on an (n dave delay d~ve.We anticipate that our results wilf be of interest in the context of parallel and distributed computing on networks of workstations (N OWS).NOWS typically

Article Free Access Share on Making commitments in the face of uncertainty: how to pick a winner almost every time (extended abstract) Authors: Baruch Awerbuch Johns Hopkins University and Lab. for Computer Science, MIT Johns Hopkins University and Lab. for Computer Science, MITView Profile , Yossi Azar Department of Computer Science, Tel-Aviv University, Israel Department of Computer Science, Tel-Aviv University, IsraelView Profile , Amos Fiat Department of Computer Science, Tel-Aviv University, Israel Department of Computer Science, Tel-Aviv University, IsraelView Profile , Tom Leighton Mathematics Department and Lab for Computer Science, MIT Mathematics Department and Lab for Computer Science, MITView Profile Authors Info & Claims STOC '96: Proceedings of the twenty-eighth annual ACM symposium on Theory of ComputingJuly 1996 Pages 519–530https://doi.org/10.1145/237814.238000Published:01 July 1996Publication History 54citation583DownloadsMetricsTotal Citations54Total Downloads583Last 12 Months24Last 6 weeks3 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

A number of current technologies allow for the determination of inter-atomic distance information three-dimensional structure?For the case of an n x n matrix in which every entry is specified, we provide a randomized algorithm running in time O(n log n) that enumerates all structures consistent wit h at most (~-s) n errors per row, with high probability y.In the case of randomly located errors, we can correct errors of the same density in a sparse matrix -one in which only a ,6 fraction of the entries in each row are given, for any constant ~>0.

Have1 and Liebl [1973], and Leighton 119841.' The networks of interest are defined in section 1.3.' For any graph 53, we denote by (%I the number of nodes in %.

We study a combinatorial problem that is motivated by “client–server” schedulers for parallel computations. Such schedulers are often used, for instance, when computations are being done by a cooperating network of workstations. Our results expose and quantify a control–memory trade-off for such schedulers, when the computation being scheduled has the structure of a binary tree, with all arcs oriented either root-toward-leaves or leaves-toward-root. The combinatorial problem for the root-toward-leaves case takes the following form. (The leaves-toward-root case gives rise to a dual formulation, which yields the same trade-offs.) Consider, for integersk,N> 0, an algorithm that employskFIFO queues in order to schedule anN-leaf binary tree in such a way that each nonleaf node of the tree is executed before its children. We establish a trade-off between the number of queues used by the algorithm—which we view as measuring thecontrol complexityof the algorithm—and thememory requirementsof the algorithm, as embodied in the required capacity of the largest-capacity queue. Specifically, for each integerk∈ {1, 2, ..., log2N}, letQk(N) denote the minimax per-queue capacity for ak-queue algorithm that schedules allN-leaf binary trees; letQ*k(N) denote the analogous quantity forcompletebinary trees. We establish the following bounds: For generalN-leaf binary trees, for allk, [formula]≤Qk(N) ≤ 2N1/k+ 1. For complete binary trees, we derive tighter bounds. We prove that for all constantk, Q*k(N) = Θ[formula]. For generalk, we obtain the following bounds: [formula]≤Q*k(N) ≤ (4k)1−1/k[formula]. Similar trade-offs are readily established for trees of any fixed branching factor.

This paper presents the first optimal-time algorithms for path selection in an optimal-size nonblocking network. In particular, we describe an N-input, N-output, nonblocking network with $O(N\log N)$ bounded-degree nodes, and an algorithm that can satisfy any request for a connection or disconnection between an input and an output in $O(\log N)$ bit steps, even if many requests are made at once. Viewed in a telephone switching context, the algorithm can put through any set of calls among N parties in $O(\log N)$ bit steps, even if many calls are placed simultaneously. Parties can hang up and call again whenever they like; every call is still put through $O(\log N)$ bit steps after being placed. Viewed in a distributed memory machine context, our algorithm allows any processor to access any idle block of memory within $O(\log N)$ bit steps, no matter what other connections have been made previously or are being made simultaneously.

In this paper, we analyze the stochastic behavior of backoff protocols for multiple access channels such as the Ethernet. In particular, we prove that binary exponential backoff is unstable if the arrival rate of new messages at each station is $\tfrac{\lambda }{N}$ for any $\lambda > \frac{1}{2}$ and the number of stations N is sufficiently large. For small N, we prove that $\lambda \geqslant \lambda _0 + \frac{1}{{4N - 2}}$` implies instability, where $\lambda _0 \approx .567$. More importantly, we also prove that any superlinear polynomial backoff protocol (e.g., quadratic backoff) is stable for any set of arrival rates that sum to less than one and any number of stations. The results significantly extend the previous work in the area and provide the first examples of acknowledgment-based protocols known to be stable for a nonnegligible overall arrival rate distributed over an arbitrarily large number of stations. The results also disprove a popular assumption that exponential backoff is the best choice among acknowledgment-based protocols for systems with large overall arrival rates. Finally, we prove that any linear or sublinear backoff protocol is unstable if the arrival rate at each station is $\frac{\lambda }{N}$ for any fixed $\lambda $ and sufficiently large N.

We study comparator networks for selection, merging, and sorting that output the correct result with high probability given a random input permutation. We prove tight bounds, up to constant factors, on the size and depth of probabilistic (n; k)-selection networks. In the case of (n; n=2)-selection, our result gives a somewhat surprising bound of \\Theta(n log log n) on the size of networks of success probability in [ffi; 1 \\Gamma 1=poly(n)], where ffi is an arbitrarily small positive constant, thus comparing favorably with the best previously known solutions, which have size \\Theta(n log n). We also prove tight bounds, up to lower order terms, on the size and depth of probabilistic merging networks of success probability in [ffi; 1 \\Gamma 1=poly(n)], where ffi is an arbitrarily small positive constant. Finally, we describe two fairly simple probabilistic sorting networks of success probability at least 1 \\Gamma 1=poly(n) and nearly logarithmic depth. 1 Department of Mathematics and Lab...

. This paper presents an analysis of the following load balancing algorithm. At each step, each node in a network examines the number of tokens at each of its neighbors and sends a token to each neighbor with at least 2d + 1 fewer tokens, where d is the maximum degree of any node in the network. We show that within O(\\Delta=ff) steps, the algorithm reduces the maximum difference in tokens between any two nodes to at most O((d 2 log n)=ff), where \\Delta is the maximum difference between the number tokens at any node initially and the average number of tokens, n is the number of nodes in the network, and ff is the edge expansion of the network. The time bound is tight in the sense that for any graph with edge expansion ff, and for any value \\Delta, there exists an initial distribution of tokens with imbalance \\Delta for which the time to reduce the imbalance to even \\Delta=2 is at least \\Omega\\Gammaa =ff). The bound on the final imbalance is tight in the sense that there exists a cl...

We establish a lower bound of (1:12 \\Gamma o(1)) n log n on the size of any n-input sorting network; this is the first lower bound that improves upon the trivial information-theoretic bound by more than a lower order term. We then extend the lower bound to comparator networks that approximately sort a certain fraction of all input permutations. We also prove a lower bound of (c \\Gamma o(1)) log n, where c ß 3:27, on the depth of any sorting network; the best previous result of approximately (2:41 \\Gamma o(1)) log n was established by Yao in 1980. Our result for size is based on a new technique that lower bounds the number of "0--1 collisions " in the network; we provide strong evidence that the technique will lead to even better lower bounds. 1 Part of this work was done while the author was at DIMACS. 2 XEROX Palo Alto Research Center, 3333 Coyote Hill Road, Palo Alto, CA 94304. Partially supported by the NSF under grant CCR-9404113. Email: [email protected]. 3 Department o...

This paper presents algorithms for routing channels with L ≥2 layers. For the unit vertical overlap model, we describe a two-layer channel routing algorithm that uses at most d + O(√d) tracks to route two-terminal net problems and 2d + O(√d) tracks to route multiterminal nets. We also show that d + Ω(log d) tracks are required to route two-terminal net problems in the worst case even if arbitrary vertical overlap is allowed. We generalize the algorithm to unrestricted multilayer routing and use only d/(L -1) + O(√d/L + 1)> tracks for two-terminal net problems (within O(√d/L + 1) tracks of optimal) and d/(L-2) +O(√d/L + 1) tracks for multiterminal net problems (within a factor of(L-1)/(L-2) times optimal). We demonstrate the generality of our routing strategy by showing that it can be used to duplicate some of the best previous upper bounds for other models (two-layer Manhattan routing and two and three-layer knock-knee routing of two-terminal, two-sided nets), and gives a new upper bound for rotuing with 45-degree diagonal wires.

All previously known algorithms for solving the multicommodity flow problem with capacities are based on linear programming. The best of these algorithms uses a fast matrix multiplication algorithm and takes O(k3.5n3m0.5 log(nDU)) time for the multicommodity flow problem with integer demands and at least O(k2.5n2m0.5 log(nϵ−1DU)) time to find an approximate solution, where k is the number of commodities, n and m denote the number of nodes and edges in the network, D is the largest demand, and U is the largest edge capacity. As a consequence, even multicommodity flow problems with just a few commodities are believed to be much harder than single-commodity maximum-flow or minimum-cost flow problems. In this paper, we describe the first polynomial-time combinatorial algorithms for approximately solving the multicommodity flow problem. The running time of our randomized algorithm is (up to log factors) the same as the time needed to solve k single-commodity flow problems, thus giving the surprising result that approximately computing a k-commodity maximum-flow is not much harder than computing about k single-commodity maximum-flows in isolation. In fact, we prove that a (simple) k-commodity flow problem can be approximately solved by approximately solving O(k log2n) single-commodity minimum-cost flow problems. Our k-commodity algorithm runs in O (knm log4n) time with high probability. We also describe a deterministic algorithm that uses an O(k)-factor more time. Given any multicommodity flow problem as input, both algorithms are guaranteed to provide a feasible solution to a modified flow problem in which all capacities are increased by a (1 + ϵ)-factor, or to provide a proof that there is no feasible solution to the original problem. We also describe faster approximation algorithms for multicommodity flow problems with a special structure, such as those that arise in "sparsest cut" problems and uniform concurrent flow problems.

A salvage-embedding (S-embedding) maps an M-leaf complete binary tree into $\mathcal{G}$ an ($N > M$)-leaf complete binary tree $\mathcal{H}$, the fraction G of whose leaves have been labeled GOOD. The S-embedding maps leaves of $\mathcal{G}$ one-to-one to GOOD leaves of $\mathcal{H}$; it may be many-to-one on internal nodes. The quality of an S-embedding depends on its harvest, the ratio $H\mathop = \limits^{def} M/GN$, and its congestion, the largest number of edges $\mathcal{G}$ that get “routed” across the same edge of $\mathcal{H}$. We study three scenarios. In the worst-case scenario, given any target harvest $H \leq \frac{1}{2}$, one can S-embed a $2^{\lfloor {\log ( HGN )} \rfloor }$-leaf $\mathcal{G}$ in $\mathcal{H}$ with congestion $\log \log N + $ a constant depending only on G and H, no matter how the GOOD leaves are distributed; this congestion cannot be lowered by more than a small constant factor. In the expected-case scenario—where leaves of $\mathcal{H}$ are labeled GOOD or not, independently, with fixed probability—with probability exceeding $1 - N^{ - \Omega ( 1 )} $, for any target harvest $H \leq 1/8$, one can S-embed a $2^{\lfloor {HN} \rfloor } $-leaf $\mathcal{G}$ in $\mathcal{H}$ with congestion $O( \log \log \log N )$. In the salvaging scenario, we present an algorithm that, in time $O( CN ( \log N )^{3C + 2} )$, S-embeds in a given a leaf-labeled $\mathcal{H}$ the largest possible $\mathcal{G}$, subject to the prespecified bound C on congestion. This work is inspired by the problem of salvaging a fault-free subnetwork of a leaf-tree machine—a tree architecture whose leaves hold “full-power” processors and whose nonleaf nodes hold “rudimentary” processors that route messages and perform simple combining tasks.

This paper considers the problems of admission control and virtual circuit routing in high performance computing and communication systems. Admission control and virtual circuit routing problems arise in numerous applications, including video-servers, real-lime database servers, and the provision of permanent virtual channel in large-scale communications networks. The paper describes both upper and lower bounds on the competitive ratio of algorithms for admission control and virtual circuit routing in trees, arrays, and hypercubes (the networks most commonly used in conjunction with nigh performance computing and communication). Our results include optimal algorithms for admission control and virtual circuit routing in trees, as well as the first competitive algorithms for these problems on non-tree networks. A key result of our research is the development of on-line algorithms that substantially outperform the greedy-based approaches that are used in practice.>

We investigate a model of gate failure for Boolean circuits in which a faulty gate is restricted to output one of its input values. For some types of gates, the model (which we call the short-circuit model of gate failure) is weaker than the traditional von Neumann model where faulty gates always output precisely the wrong value. Our model has the advantage that it allows us to design Boolean circuits that can tolerate worst-case faults, as well as circuits that have arbitrarily high success probability in the case of random faults. Moreover, the short-circuit model captures a particular type of fault that commonly appears in practice, and it suggests a simple method for performing post-test alterations to circuits that have more severe types of faults. A variety of bounds on the size of fault-tolerant circuits are proved in the paper. Perhaps, the most important is a proof that any k-fault-tolerant circuit for any input-sensitive function using any type of gates (even arbitrarily powerful, multiple-input gates) must have size at least /spl Omega/(k log k/log log k). Obtaining a tight bound on the size of a circuit for computing the AND of two values if up to k of the gates are faulty is one of the central questions left open in the paper.>

We study a combinatorial problem that is motivated by '(client-server" schedulers for networks of

An adaptive routing algorithm is one in which the path a packet takes from its source to its destination may depend on other packets it encounters. Such algorithms potentially avoid network bottlenecks by routing packets around “hot spots.” Minimal adaptive routing algorithms have the additional advantage that the path each packet takes is a shortest one.

In this paper, we describe a very simple boundedqueuesize local-control algorithm for routing multicommodity flows in a dynamically-changing distributed network. The algorithm is based on the edge-balancing approach described in [AL93], but has the added benefits of: 1. a much improved running time, and 2. working even in networks where edge capacities can vary in an unpredictable and unknown fashion. In fact, the sequential running time of the algorithm is now comparable to (and, in some cases, better than) the time of the best previously known approximation algorithms for the multi-commodity flow problem in a fixed network [LMP + 91]. The fact that the new algorithm works well in dynamically changing networks means that problems such as end-to-end communication and load balancing [AMS89, AGR92, AAMR93] can now be solved in Johns Hopkins University, Baltimore, MD 21218-2694, and MIT Laboratory for Computer Science, Cambridge MA 02139. Email: [email protected]. Supported by...

Recent work has shown marry advantages to randomly wired expander-based networks.Unfortunately, the win"ng complexity of such networks becomes physically problematic as they become large.This paper introduces a technique for sca3ing expanders that avoids this wirr"ng complexity.Specifically, we make the following contributions:1. We introduce hierarchical expanders, which use a method of scaling small expanders to larger ones while ma"nta"m"ng practical physical construction.We present an example of such a scalable network, called the metabutterjly, which is scaled from the randomJy wired multibutterfly.2. We present a proof that we can scale any (cY,/?, M, N)exprmder with dbf > 1 into an (a',,@, kM, kN) -expander with probability at least 1 -2e-a M, where a' = ~2e~~4= arrd/3' =/3-2.3. Wepresent empirical evidence that the performance and fault tolerance of metabuttertlies equals that of traditionid randomly wired multibutterflies, despite the greatly simplified wiring of the metabuttertly

This paper describes a two-point net channel routing problem with density d that requires channel width $2d - 1$ in the two-layer knock-knee channel routing model. This means that the $( 2d - 1 )$-track algorithms of Rivest, Baratz, and Miller [1981 CMU Conference on VLSI Systems and Computations, Oct. 1981, pp. 153–159], Bolognesi and Brown [unpublished manuscript, Coordinated Science Laboratory, University of Illinois at Urbanna-Champaign, 1982], Frank [Combinatorica, 2 (1982), pp. 361–371], Mehlhorn, Preparata, and Sarrafzadeh [University of Saarbrucken Tech. Rep., Saarbrucken, Germany, Nov. 1984], and Berger et al. [J. Assoc. Comput. Mach., 1994, to appear], are, in some cases, optimal. Thus, any improvement of these algorithmsmust rely on problem features other than density (such as flux [Advances in Computing Research 2 (VLSI Theory), F. P. Preparata, ed., JAI Press, Greenwich, CT, 1984, pp. 205–229]) or must make fundamental changes in the wiring model (such as increasing the number of layers [IEEE Trans. Comput., C-33 (1984), pp. 427–437] or allowing wires to overlap [see Berger et al., above], [Algorithmica, 1 (1986), pp. 223–232]).

In this paper, we describe a very simple (1+/spl epsi/)-approximation algorithm for the multicommodity flow problem. The algorithm runs in time that is polynomial in N (the number of nodes in the network) and /spl epsiv//sup -1/ (the closeness of the approximation to optimal). The algorithm is remarkable in that it is much simpler than all known polynomial time flow algorithms (including algorithms for the special case of one-commodity flow). In particular, the algorithm does not rely on augmenting paths, shortest paths, min-cost paths, or similar techniques to push flow through a network. In fact, no explicit attempt is ever made to push flow towards a sink during the algorithm. Because the algorithm is so simple, it can be applied to a variety of problems for which centralized decision making and flow planning is not possible. For example, the algorithm can be easily implemented with local control in a distributed network and it can be made tolerant to link failures. In addition, the algorithm appears to perform well in practice. Initial experiments using the DIMACS generator of test problems indicate that the algorithm performs as well as or better than previously known algorithms, at least for certain test problems.>

We study the problem of constructing a sorting circuit, network, or PRAM algorithm that is tolerant to faults. For the most part, we focus on fault patterns that are random, e.g., where the result of each comparison is independently faulty with probability upper-bounded by some constant. All previous fault-tolerant sorting circuits, networks, and parallel algorithms require /spl Omega/(log/sup 2/ n) depth (time) and/or /spl Omega/(nlog/sup 2/ n) comparisons to sort n items. In this paper, we construct a passive-fault-tolerant sorting circuit with O(nlog nloglog n) comparators, a reversal-fault-tolerant sorting network with O(n log/sup log(2)/ /sup 3/ n) comparators, and a deterministic O(log n)-step O(n)-processor EREW PRAM fault-tolerant sorting algorithm. The results are based on a new analysis of the AKS circuit, which uses a much weaker notion of expansion that can be preserved in the presence of faults. Previously, the AKS circuit was not believed to be fault-tolerant because the expansion properties that were believed to be crucial for the performance of the circuit are destroyed by random faults. Extensions of our results for worst-case faults are also presented.>

paper we consider the probcommunication on a Compltd ely Connected Optical Communication Parallel Computer (OCPC).The particular problem we study is that of realizing an h-r-elation.In this problem, each processor has at most h messages to send and at most h messages to receive.It is clear that any 1-relation can be realized in one communication step on an OCPC.However, the best known p-processor OCPC algorithm for realizing an arbitrary h-relation for h > 1 requires @(h + logp) expected communication steps.(This algorithm is due to Valiant and is based on earlier work of Anderson and Miller.) Valiant's algorithm is optimal only for h = f2(log p) and it is an open question of Ger6b-Graus and Tsantilas whether there is a faster algorithm for h = o(logp).In this paper we answer this question in the affirmative by presenting 1

We study networks that can sort n items even sorting or merging network.

This paper presents the problem of drawing a graph in the plane so that edges appear as straight lines and the minimum angle formed by any pair of incident edges is maximized. The resolution of a layout is defined to be the size of the minimum angle formed by incident edges of the graph, and the resolution of a graph to be the maximum resolution of any layout of the graph. The resolution R of a graph is characterized in terms of the maximum node degree d of the graph by proving that $\Omega (\frac{1}{{d^2 }}) \leqslant R \leqslant \frac{{2\pi }}{d}$ for any graph. Moreover, it is proved that $R = \Theta (\frac{1}{d})$ for many graphs including planar graphs, complete graphs, hypercubes, multidimensional meshes and tori, and other special networks. It is also shown that the problem of deciding if $R = \frac{{2\pi }}{d}$ for a graph is NP-hard for $d = 4$, and by using a counting argument that $R = O(\frac{{\log d}}{{d^2 }})$ for many graphs.

The authors analyze the fault-tolerance properties of several bounded-degree networks that are commonly used for parallel computation. Among other things, they show that an N-node butterfly containing N/sup 1- epsilon / worst-case faults (for any constant epsilon >0) can emulate a fault-free butterfly of the same size with only constant slowdown. Similar results are proved for the shuffle-exchange graph. Hence, these networks become the first connected bounded-degree networks known to be able to sustain more than a constant number of worst-case faults without suffering more than a constant-factor slowdown in performance. They also show that an N-node butterfly whose nodes fail with some constant probability p can emulate a fault-free version of itself with a slowdown of 2/sup O(log* N)/, which is a very slowly increasing function of N. The proofs of these results combine the technique of redundant computation with new algorithms for routing packets around faults in hypercubic networks. Techniques for reconfiguring hypercubic networks around faults that do not rely on redundant computation are also presented. These techniques tolerate fewer faults but are more widely applicable since they can be used with other networks such as binary trees and meshes of trees.>

Article Free Access Share on Methods for message routing in parallel machines Author: Tom Leighton Mathematics Department and Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA Mathematics Department and Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MAView Profile Authors Info & Claims STOC '92: Proceedings of the twenty-fourth annual ACM symposium on Theory of ComputingJuly 1992 Pages 77–96https://doi.org/10.1145/129712.129721Online:01 July 1992Publication History 43citation550DownloadsMetricsTotal Citations43Total Downloads550Last 12 Months6Last 6 weeks5 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

The boolean hypercube is a particularly versatile network for parallel computing. It is well known that multidimensional grid machines can be simulated on a hypercube with no communications overhead. In this paper it is shown that every bounded-degree tree can be simulated on the hypercube with constant communications overhead. In fact, the proof shows that every bounded-degree graph with an $O(1)$-separator can be embedded in a hypercube of the same size with dilation and congestion both $O(1)$. It is also proved that not all bounded-degree graphs can be efficiently embedded within the hypercube.

This paper presents simple randomized algorithms for dynamically embedding M-node binary trees in either a butterfly or a hypercube network of N processors. These algorithms are dynamic in the sense that the tree to be embedded may start as one node and grow by dynamically spawning children. The nodes are incrementally embedded as they are spawned. Thus, the algorithm is especially suited for maintaining dynamic tree structures like those in divide-and-conquer and branch-and-bound algorithms. In the embeddings, the paper seeks to optimize the load on the processors of the network, the dilation of the tree edges, and the congestion on the network edges, in order to satisfy the demands of load balancing, process locality, and communication efficiency. The paper begins by presenting a simple level-by-level scheme for dynamically embedding trees in a butterfly network, and by successive modifications. The following results are obtained: 1. An embedding algorithm for the hypercube that achieves dilation 1 and, with high probability, load $O((M /N) + \log N)$. 2. An embedding algorithm for the butterfly that achieves dilation 2 and, with high probability, load $O((M/ N) + \log N)$. 3. An embedding algorithm for the hypercube that achieves dilation $O(1)$ and, with high probability, load $O((M/N) + 1)$ and congestion $O((M/ N) + 1)$. The third embedding simultaneously optimizes load and dilation to within constant factors, optimizing congestion as well when $M = O(N)$. The first two embeddings are also optimal to within constant factors when the tree to be embedded is large (i.e., $M = \Omega (N\log N)$. In addition, this paper proves a lower bound of $\Omega (\sqrt {\log N} )$ dilation for deterministic embedding algorithms that achieve load $O((M/ N) + 1)$, which implies that any embedding algorithm that simultaneously optimizes load and dilation must be randomized.

The relative powers of queues and stacks are compared as mechanisms for laying out the edges of a graph. In a k-queue layout, vertices of the graph are placed in some linear order (also called a linear arrangement), and each edge is assigned to exactly one of the k queues, so that the edges assigned to each queue obey a first-in/first-out (FIFO) discipline. As the vertices are scanned left to right, an edge is enqueued on its assigned queue when its left endpoint is encountered and is dequeued from its queue when its right endpoint is encountered. In a k-stack layout, vertices of the graph are placed in some linear order, and each edge is assigned to exactly one of the k stacks so that the edges assigned to each stack obey a last-in/first-out discipline. As the vertices are scanned left to right, an edge is pushed on its assigned stack when its left endpoint is encountered and is popped from its stack when its right endpoint is encountered. The paper has three main results. First, a tradeoff between queuenumber and stacknumber is shown for a fixed linear order of the vertices of G. In particular, for a fixed-order layout of a graph G, \[ {\text{queuenumber }} \times {\text{ stacknumber }} \geq {\text{ cutwidth/valence }}( G ).\] Second, it is shown that every 1-queue graph has a 2-stack layout and that every 1-stack graph has a 2-queue layout. Third, in a surprising display of the power of queues, it is shown that the ternary hypercube requires exponentially more stacks than queues. More precisely, an N-vertex ternary hypercube has a $( 2\log _3 N )$-queue layout but requires $\Omega ( N^{1/9 - \epsilon } )$ stacks, $\epsilon > 0$, in any stack layout. Also, some asymptotic bounds for the queuenumber of bounded-valence graphs are derived.

A tight lower bound is proved on the minimum number of vertices in a planar graph in which any permutation between t distinguished vertices can be realized by vertex disjoint paths.

Simple deterministic O(log N)-step algorithms for routing permutations of packets in multibutterflies and randomly wired splitter networks are described. The algorithms are robust against faults (even in the worst case), and are efficient from a practical point of view. As a consequence, it is found that the multibutterfly is an excellent candidate for a high-bandwidth low-diameter switching network underlying a shared-memory machine.>

The problem of constructing a sorting circuit that will work well even if a constant fraction of its comparators fail at random is addressed. Two types of comparator failure are considered: passive failures, which result in no comparison being made (i.e., the items being compared are output in the same order that they are input), and destructive failures, which result in the items being output in the reverse of the correct order. In either scenario, it is assumed that each comparator is faulty with some constant probability rho , and a circuit is said to be fault-tolerant if it performs some desired function with high probability given that each comparator fails with probability rho . One passive and two destructive circuits are constructed.>

The problem of dynamically allocating and deallocating local memory resources among multiple users in a parallel or distributed system is considered. The goal is to devise an online allocation algorithm that minimizes both the fraction of unused space due to fragmentation of the memory and the slowdown needed by the system to service user requests. The problem is solved in near-optimal fashion by devising an algorithm that allows the memory to be used to 100% of capacity despite the fragmentation and guarantees that service delays will always be within a constant factor of optimal. The algorithm is completely online (no foreknowledge of user activity is assumed) and can accommodate any sequence of insertions and deletions by the users which does not violate global memory bounds. The results have applications in the domain of parallel disk allocation.>

Article Coding theory, hypercube embeddings, and fault tolerance Share on Authors: Bill Aiello Bellcore, Morristown, NJ Bellcore, Morristown, NJView Profile , Tom Leighton Mathematics Department and Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA Mathematics Department and Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MAView Profile Authors Info & Claims SPAA '91: Proceedings of the third annual ACM symposium on Parallel algorithms and architecturesJune 1991 Pages 125–136https://doi.org/10.1145/113379.113391Online:01 June 1991Publication History 51citation402DownloadsMetricsTotal Citations51Total Downloads402Last 12 Months2Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

All previously known algorithms for solving the multicommodity flow problem with capacities are based on linear programming.The best of these algorithms [14] uses a fast matrix multiplication algorithm and takes O(k25n2m5 log(nDU))time to find an approximate solution, where k is the number of commodities, n and m denote the number of nodes and edges in the network, D is the largest demand, and U is the largest edge capacity.Substantially more time is needed to find an exact solution.As a consequence, even multicommodit y flow problems with jnst a few commodities are believed to be much harder than single-commodity maximum-flow or minimum-cost flow problems.In thk paper, we describe the first polynomial-time combinatorial algorithms for approximately solving the multicommodity flow problem.The running time of our randomized algorithm is (up to ,log factors) the same as the time needed to solve k single-commodity flow problems, thus giving the surprising result that approximately computing a k-commodity maximum-flow is not much harder than computing about k single-commodity maximum-flows in isolation.In fact, we prove that a (simple) k-commodity flow problem can be approximately solved by approximately solving O(k log2 n) single-commodity minimum-cost flow problems.Our k-commodity algorithm runs in O(knm log4 n) time with high probability.We also describe a deterministic algorithm that uses an O(k)-factor more time.Given any multicommodit y flow problem as input, both rdgorithms are guaranteed to provide a feasible solution to a modified @ 1991

The problem of drawing a graph in the plane so that edges appear as straight lines and the minimum angle formed by any pair of incident edges is maximized is studied. The resolution of a layout is defined to be the size of the minimum angle formed by incident edges of the graph, and the resolution of a graph is defined to be the maximum resolution of any layout of the graph. The resolution R of a graph is characterized in terms of the maximum node degree d of the graph by proving that Omega (1/d/sup 2/)>

The computational power of 2-D and 3-D processor arrays that contain a potentially large number of faults is analyzed. Both a random and a worst-case fault model are considered, and it is proved that in either scenario low-dimensional arrays are surprisingly fault tolerant. It is also shown how to route, sort, and perform systolic algorithms for problems such as matrix multiplication in optimal time on faulty arrays. In many cases, the running time is the same as if there were no faults in the array (up to constant factors). On the negative side, it is shown that any constant congestion embedding of an n*n fault-free array on an n*n array with Theta (n/sup 2/) random faults (or Theta (log n) worst-case faults) requires dilation Theta (log n). For 3-D arrays, knot theory is used to prove that the required dilation is Omega ( square root log n).>

A natural k-round tournament over n=2/sup k/ players is analyzed, and it is demonstrated that the tournament possesses a surprisingly strong ranking property. The ranking property of this tournament is exploited by being used as a building block for efficient parallel sorting algorithms under a variety of different models of computation. Three important applications are provided. First, a sorting circuit of depth 7.44 log n, which sorts all but a superpolynomially small fraction of the n-factorial possible input permutations, is defined. Secondly, a randomized sorting algorithm that runs in O(log n) word steps with very high probability is given for the hypercube and related parallel computers (the butterfly, cube-connected cycles, and shuffle-exchange). Thirdly, a randomized algorithm that runs in O(m+log n)-bit steps with very high probability is given for sorting n O(m)-bit records on an n log n-node butterfly.>

Experimental data are presented indicating that multistage interconnection networks with randomly positioned wires are likely to be substantially better for message routing applications than traditional multistage networks, such as the butterfly. The data are presented for a variety of routing models, including store-and-forward routing, cut-through routing, and circuit switching, as well as for scenarios in which a potentially large number of switches are faulty. In most cases, the differences are dramatic, particularly when several switches in the network are faulty. The data provide empirical confirmation of recent theoretical work.>

In this paper, we describe an O(log N) bit-step randomized algorithm for bit-serial message routing on a hypercube.The result is asymptotically optimal, and improves upon the best previously known algorithms by a logarithmic factor.The result also solves the problem of on-line circuit switching in an O(l)-dilated hypercube (i.e., partitioning the edges of a dilated hypercube so as to realize an arbitrary permutation of point-to-point connections between the nodes).Our algorithm is adaptive and we show that this is necessary to achieve the logarithmic speedup.We generalize the Borodin-Hopcroft lower bound on oblivious routing by proving that any oblivious randomized algorithm on a polylogarithmic degree network requires sZ(log' N/log log N) bit steps with high probability for almost all permutations.

In this paper, we analyze the average case behavior of greedy routing algorithms on arrays under a variety of assumptions.Overall, we find that certain greedy algorithms perform surprisingly well on average.For example, given an N x N array or torus where every node starts with one packet headed for a random destination, we show that some (but not all) greedy store-andforward algorithms route every packet to its destinrt, tion with only O(log N) delay per packet and maximum queuesize 4 with probability near 1.Moreover, the expected delay per packet is only a small constant, independent of N. We also extend the analysis to a steady state model of routing in which packets enter the network at random times.Provided that the overall arrival rate of packets to the network is less than 100% of the network capacity, we show that any packet encounters at most O(log N) delay with high probability.In addition, we show that the maximum size of a queue over a time span of T steps is O(e) with high probability.The results can also be extended to analyze the average case behavior of cut-through (or, flit-serial) routing under lighter loading.and NOO014-89-J-1988,

In this paper, we describe a new technique for solving a variety of query-retrieval problems in optimal time with optimal or near-optimal space.In particular, we use the technique to construct algorithms and data structures for circular range searching, half-space range searching, and computing k-nearest neighbors in a variety of metrics.For each problem and each query, the response to the query is provided in O(k) or O(k + log n) time where k is the size of the response and n is the size of the problem.(E.g., for the n-point k-nearest neighbors problem, the k-nearest neighbors of any query point are provided in O(k -4log n) steps.)Depending on the problem being solved, the space required for the data structure is either linear or O(n log n).Hence, the time bounds are optimal and the space bounds are optimal or near-optimal.Previously known data structures for these problems required a factor of ~(log n(log log n) 2) or ~(log n log log n) more space and/or more time to answer each query.Our compaction technique incorporates planar separators, filtering search, and the probabilistic method for discrepancy problems.The fundamental idea is that k'h-order Voronoi diagrams (and other suitable proximity diagrams) can be compacted from k°(1)n space to O(n) space and still retain all the information that is essential for solving query problems.This result is of independent interest and may be useful in improving the memory space requirement or the query-time bound for other query-retrieval problems.

Nonblocking networks arise in a variety of applications involving communications.The most well known examples include telephone networks, data networks, and distributed memory architectures.Although asymptotically optimal constructions are known for nonblocking networks in a variety of models, it is generally not known how to select paths for the desired network connections efficiently on-line.In this paper, we present the first optimal-time algorithms for path selection in an optimal-size nonblocking network.In particular, we describe a bounded-degree, O(N log N)-switch nonblocking network that can realize any sequence of connections and disconnections among N terminals with O(logN) bit-step delay.Viewed in the context of a telephone switching network, our network and algorithm can handle any sequence of calls among N parties with O(log N) bit-step delay per call (even if many calls are made at once).Parties can hang up and call again whenever they like, and multiparty calls can be made without affecting the performance of the algorithm --every call is still put through in O(logN) time.Viewed in the context of distributed memories for parallel machines, our algorithm allows any processor to access any idle block of memory within O(log N) bit-steps at any time --no matter what other connections have been made previously or are being made simultaneously.

In this paper, we compare the performance of two popular graph bisection algorithms. We also present an empirical study of a new heuristic, first proposed in [B87], that dramatically improves the performance of these bisection algorithms on graphs with small (≤ 4) average degree.

Simple deterministic O(log N)-step algorithms for routing packets on a multibutterfly are described. The algorithms are shown to be robust against faults, even in the worst case, and to be efficient from a practical point of view. As a consequence, the multibutterfly is shown to be an excellent candidate for a high-bandwidth, low-diameter switching network underlying a distributed-memory machine.>

Article Free Access Share on A 2n-2 step algorithm for routing in an nxn array with constant size queues Authors: T. Leighton Mathematics Department and Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA Mathematics Department and Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MAView Profile , F. Makedon Department of Computer Science, University of Texas at Dallas, Richardson, TX Department of Computer Science, University of Texas at Dallas, Richardson, TXView Profile , I. G. Tollis Department of Computer Science, University of Texas at Dallas, Richardson, TX Department of Computer Science, University of Texas at Dallas, Richardson, TXView Profile Authors Info & Claims SPAA '89: Proceedings of the first annual ACM symposium on Parallel algorithms and architecturesMarch 1989 Pages 328–335https://doi.org/10.1145/72935.72970Published:01 March 1989Publication History 64citation353DownloadsMetricsTotal Citations64Total Downloads353Last 12 Months19Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Article Dynamic tree embeddings in butterflies and hypercubes Share on Authors: T. Leighton M.I.T. Mathematics Department and Laboratory for Computer Science, Cambridge, MA M.I.T. Mathematics Department and Laboratory for Computer Science, Cambridge, MAView Profile , M. Newman M.I.T. Mathematics Department and Laboratory for Computer Science, Cambridge, MA M.I.T. Mathematics Department and Laboratory for Computer Science, Cambridge, MAView Profile , A. G. Ranade Department of EECS, University of California, Berkeley, CA Department of EECS, University of California, Berkeley, CAView Profile , E. Schwabe M.I.T. Mathematics Department and Laboratory for Computer Science, Cambridge, MA M.I.T. Mathematics Department and Laboratory for Computer Science, Cambridge, MAView Profile Authors Info & Claims SPAA '89: Proceedings of the first annual ACM symposium on Parallel algorithms and architecturesMarch 1989 Pages 224–234https://doi.org/10.1145/72935.72959Online:01 March 1989Publication History 23citation365DownloadsMetricsTotal Citations23Total Downloads365Last 12 Months1Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

We consider the computational power of a hypercube containing a potentially large number of randomly located faulty components. We describe a randomized algorithm which embeds an N-node hypercube in an N-node hypercube with faulty processors. Provided that the processors of the N-node hypercube are faulty with probability p < 1, and that the faults are independently distributed, we show that with high probability, the faulty hypercube can emulate the fault-free hypercube with only constant slowdown. In other words, an N-node hypercube with faults can simulate T steps of an N-node fault-free hypercube in O(T) steps. The embedding is easy to construct in polylogarithmic time using only local control. We also describe O(log N)-step routing algorithms which ensure the delivery of messages with high probability even when a constant fraction of the nodes and edges have failed. The routing results represent the first adaptive routing algorithms for which an effective theoretical analysis has been achieved.

In this paper, we study the problem of emulating TG steps of an NG-node guest network on an NH-node host network. We call an emulation work-preserving if the time required by the host, TH, is Ο(TGNG/NH) because then both the guest and host networks perform the same total work, Θ(TGNG), to within a constant factor. We say that an emulation is real-time if TH = Ο(TG), because then the host emulates the guest with constant delay. Although many isolated emulation results have been proved for specific networks in the past, and measures such as dilation and congestion were known to be important, the field has lacked a model within which general results and meaningful lower bounds can be proved. We attempt to provide such a model, along with corresponding general techniques and specific results in this paper. Some of the more interesting and diverse consequences of this work include:

How small can a graph be that contains as subgraphs all trees on n vertices with maximum degree d? In this paper, this question is answered by constructing such universal graphs that have n vertices and bounded degree (depending only on d). Universal graphs with n vertices and $O(n\log n)$ edges are also constructed that contain all bounded-degree planar graphs on n vertices as subgraphs. In general, it is shown that the minimum universal graph containing all bounded-degree graphs on n vertices with separators of size $n^\alpha $ has $O(n)$ edges if $\alpha < \frac{1}{2}$; $O(n\log n)$ edges if $\alpha = \frac{1}{2}$; $O(n^{2\alpha } )$ edges if $\alpha > \frac{1}{2}$.

The packet-routing problem is examined in a network-independent context. The goal is to devise a strategy for routing that works well for a wide variety of networks. To achieve this goal, the routing problem is partitioned into two stages: a path-selection stage and a scheduling stage. In the first stage, paths for the packets are found with small maximum distance and small maximum congestion. Once the paths are fixed, both are lower bounds on the time required to deliver the packets. In the second stage, a schedule is found for the movement of each packet along its path so that no two packets traverse the same edge at the same time and the total time and maximum queue size required to route all of the packets to their destinations are minimized. The second stage is more challenging and is the focus of this study.>

A multicommodity flow problem is considered where for each pair of vertices (u, v) it is required to send f half-units of commodity (u, v) from u to v and f half-units of commodity (v, u) from v to u without violating capacity constraints. The main result is an algorithm for performing the task provided that the capacity of each cut exceeds the demand across the cut by a Theta (log n) factor. The condition on cuts is required in the worst case, and is trivially within a Theta (log n) factor of optimal for any flow problem. The result can be used to construct the first polylog-times optimal approximation algorithms for a wide variety of problems, including minimum quotient separators, 1/3-2/3 separators, bifurcators, crossing number, and VLSI layout area. It can also be used to route packets efficiently in arbitrary distributed networks.>

Article Free Access Share on Optimal simulations by Butterfly Networks Authors: Sandeep Bhatt Department of Computer Science, Yale University, New Haven, CT Department of Computer Science, Yale University, New Haven, CTView Profile , Fan Chung Mathematics, Information Sciences and Operations Research Division, Bell Communications Research, Morristown, NJ Mathematics, Information Sciences and Operations Research Division, Bell Communications Research, Morristown, NJView Profile , Jia-Wei Hong Beijing Computer Institute, Beijing 10044, CHINA and Courant Institute of Mathematics, NYU, New York, NY Beijing Computer Institute, Beijing 10044, CHINA and Courant Institute of Mathematics, NYU, New York, NYView Profile , Arnold Rosenberg Department of Computer and Information Science, University of Massachusetts, Amherst, MA Department of Computer and Information Science, University of Massachusetts, Amherst, MAView Profile Authors Info & Claims STOC '88: Proceedings of the twentieth annual ACM symposium on Theory of computingJanuary 1988 Pages 192–204https://doi.org/10.1145/62212.62229Published:01 January 1988Publication History 24citation283DownloadsMetricsTotal Citations24Total Downloads283Last 12 Months20Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

We consider the computational power of a hypercube containing a potentially large number of randomly located faulty components. In particular, we describe algorithms for embedding an N/2-node hypercube in an N-node hypercube with faulty processors. Provided that the processors of the N-node hypercube are faulty with probability p < 1/2, and that the faults are independently distributed, we show that with high probability, adjacent cells in the N/2-node hypercube are mapped to functioning cells at distance 3 or less apart in the N-node hypercube. The algorithm is deterministic, easy to implement and runs in Ο(log N) steps using only local control. We also describe ways to produce embeddings which allow for low delay simulations, as well as ways to use a faulty hypercube to efficiently simulate a completely functioning hypercube of the same size.

In the paper, we analyze the stochastic behavior of backoff protocols for multiple access channels such as the Ethernet. In particular, we prove that binary exponential backoff is unstable if the arrival rate of new messages at each station is λ/N for any number of stations N exceeding 1 and any overall arrival rate λ exceeding .567 + 1/4N - 2. More importantly, we also prove that any superlinear polynomial backoff protocol (e.g., quadratic backoff) is stable for any set of arrival rates that sum to less than one, and any number of stations. The results significantly extend the previous work in the area, and provide the first examples of acknowledgement based protocols known to be stable for a nonnegligible overall arrival rate distributed over an arbitrarily large number of stations. The results also disprove a popular assumption that exponential backoff is the best choice among acknowledgement based protocols for systems with large overall arrival rates. Finally, we prove that any linear or sublinear backoff protocol is unstable if the arrival rate at each station is λ/N for any fixed λ and sufficiently large N.

Universal networks offer the advantage that they can execute programs written for simpler architectures without significant run-time overhead. In this paper we investigate simulations of tree machines; the fact that divide-and-conquer algorithms are programmed naturally on trees motivates our investigation. Among various proposals for parallel computing the boolean hypercube has emerged as a particularly versatile network. It is well known that programs for multidimensional grid machines, for example, can be executed on a hypercube with no communications overhead by embedding the grid as a subgraph of the hypercube. Our first result is that a program for any tree machine can be executed on the hypercube with constant overhead. More precisely, every cycle of a synchronous binary tree can be simulated in O(1) cycles on a hypercube, independent of the shape of the tree. The algorithm to embed the tree within the hypercube runs in polynomial time. We also give efficient simulations of arbitrary binary trees on the complete binary tree, the FFT and shuffle-exchange networks. It is natural to ask if any sparse network can simulate every binary tree efficiently. Somewhat surprisingly, we construct a universal bounded-degree network on N nodes for which every N node binary tree is a spanning tree. In other words, every binary tree can be simulated on our universal network with no overhead. This improves previous bounds on the sizes of universal graphs for trees.

The design and analysis of algorithms for on-line dynamic storage allocation has been a fundamental problem area in computer science for many years.In this paper we study the stochastic behavior of dynamic allocation algorithms under the natural assumption that files enter and leave the system according to a Poisson process.In particular, we prove that for any dynamic allocation algorithm and any distribution of file sizes, the expected wasted space (or fragmentation) in the system at any time is ~ (-v~'x/loglogN), where N is the expected number of items (or used space) in the system.This result is known to be tight in the special case when all files have the same size.More importantly, we also construct a dynamic allocation algorithm which for any distribution of file sizes wastes only O (x/~'log 3/4 N) space with very high probability.This bound is also shown to be tight for a wide variety of file-size distributions, including for example the uniform and normal distributions.

The minimax grid matching problem is a fundamental combinatorial problem associated with the average case analysis of algorithms.The problem has arisen in a number of interesting and seemingly unrelated areas, including wafer-scale integration of systolic arrays, twodimensional discrepancy problems, and testing pseudorandom number generators.However, the minimax grid matching problem is best known for its application to the maximum up-right matching problem.The maximum up-right matching problem was originally defined by Karp, Luby and Marchetti-Spaccamela in association with algorithms for 2dimensional bin packing.More recently, the up-right matching problem has arisen in the average case analysis of on-line algorithms for 1-dimensional bin packing and dynamic allocation.In this paper, we solve both the minimax grid matching problem and the maximum up-right matching problem.As a direct result, we obtain tight upper bounds on the average case behavior of the best algorithms known for 2-dimensional bin packing, 1-dimensional on-line packing and on-line dynamic allocation.The results also solve a long-open question in mathematical statistics.

Recent advances in fabrication technology have rendered imminent the fabrication of multilayer (i.e., three-dimensional) chips, wafers, and packages. In this paper, we examine the savings in material (as measured by Area in a two-dimensional medium and Volume in a three-dimensional one) and in communication time (as measured by the length of the longest uninterrupted run of wire) afforded by this developing technology. We derive close upper and lower bounds on the efficiency with which circuits can be realized in a multilayer medium, based on the sizes of the smallest bifurcators of the circuit. We find that the smallest Volume of any three-dimensional layout of an N-device circuit is no more than (roughly) $(NA)^{{1 / 2}} $, where A is the smallest Area of any two-dimensional layout of the circuit. We then refine our layout techniques so that we can deal with multilayer layouts having a fixed numberr of layers. We find that we can efficiently transform a two-dimensional layout of Area A and Maximum Wire Run R into a three-dimensional layout of Volume (roughly) $V = {A / H}$ and Maximum Wire Run $R^ * = {R / H}$ for moderate numbers of layers H. Two noteworthy features of the study are: (1) that, within logarithmic factors, the indicated savings can be realized with layouts that use the third dimension only for interconnect; and (2) that the indicated savings can be realized algorithmically: we present polynomial-time algorithms that transform a given two-dimensional layout into a more efficient three-dimensional one.

Let\{X_{i}\}_{i=1}^{\infty}be a sequence of independent Bernoulli random variables with probabilitypthatX_{i} = 1and probabilityq=1-pthatX_{i} = 0for alli \geq 1. Time-invariant finite-memory (i.e., finite-state) estimation procedures for the parameter p are considered which takeX_{1}, \cdotsas an input sequence. In particular, an n-state deterministic estimation procedure is described which can estimate p with mean-square errorO(\log n/n)and ann-state probabilistic estimation procedure which can estimatepwith mean-square errorO(1/n). It is proved that theO(1/n)bound is optimal to within a constant factor. In addition, it is shown that linear estimation procedures are just as powerful (up to the measure of mean-square error) as arbitrary estimation procedures. The proofs are based on an analog of the well-known matrix tree theorem that is called the Markov chain tree theorem.

In this paper, we prove tight upper and lower bounds on the number of processors, information transfer, wire area, and time needed to sort N numbers in a bounded-degree fixed-connection network. Our most important new results are: 1) the construction of an N-node degree-3 network capable of sorting N numbers in O(log N) word steps; 2) a proof that any network capable of sorting N (7 log N)-bit numbers in T bit steps requires area A where AT2= Ω(N2log2N); and 3) the construction of a ``small-constant-factor'' bounded-degree network that sorts N Θ(log N)-bit numbers in T = Θ(log N) bit steps with A = Θ(N2) area.

VLSI technologists are fast developing wafer-scale integration. Rather than partitioning a silicon wafer into chips as is usually done, the idea behind wafer-scale integration is to assemble an entire system (or network of chips) on a single wafer, thus avoiding the costs and performance loss associated with individual packaging of chips. A major problem with assembling a large system of microprocessors on a single wafer, however, is that some of the processors, or cells, on the wafer are likely to be defective. In the paper, we describe practical procedures for integrating "around" such faults. The procedures are designed to minimize the length of the longest wire in the system, thus minimizing the communication time between cells. Although the underlying network problems are NP-complete, we prove that the procedures are reliable by assuming a probabilistic model of cell failure. We also discuss applications of the work to problems in VLSI layout theory, graph theory, fault-tolerant systems, planar geometry, and the probabilistic analysis of algorithms.

We describe a polynomial time algorithm that, for every input graph, either outputs the minimum bisection of the graph or halts without output. More importantly, we show that the algorithm chooses the former course with high probability for many natural classes of graphs. In particular, for every fixed d⩾3, all suffciently large n and all b = o(n1-(1/[(d+1)/2]), the algorithm finds the minimum bisection for almost all d-regular labelled simple graphs with 2n nodes and bisection width b.

We study the asymptotic expected behavior of the First Fit and First Fit Decreasing bin packing algorithms applied to items chosen uniformly from the interval (0,u], u ≤ 1. Our results indicate that the algorithms perform even better than previously expected.

In this paper, we prove tight upper and lower bounds on the number or processors, information transfer, wire area and time needed to sort N numbers in a bounded-degree fixed-connection network. Our most important new results are:

We examine the problem of routing wires on a VLSI chip, where the pins to be connected are arranged in a regular rectangular array. We obtain tight bounds for the worst-case "channel-width" needed to route an n × n array, and develop provably good heuristics for the general case. An interesting "rounding algorithm" for obtaining integral approximations to solutions of linear equations is used to show the near-optimality of single-turn routings in the worst-case.

A linear-time approximation algorithm for routing multipoint net channels is presented. The algorithm uses at most a constant factor times the optimal number of tracks required. The notion of channel fluxis introduced and shown, like channel density, to be a lower bound for channel width. Every multipoint net channel having density d and flux f is routed within 2d+O(f) tracks, and every two-point net channel within d+O(f) tracks. Since the flux never exceeds θ(@@@@n), this proves a conjecture of Brown and Rivest [6] that every n-net channel can be routed in O(d+@@@@n) tracks.

This paper describes and analyzes several algorithms for constructing systolic array networks from cells on a silicon wafer. Some of the cells may be defective, and thus the networks must be configured to avoid them. We adopt a probabilistic model of cell failure, and attempt to construct networks whose maximum wire length is minimal Although the algorithms presented are designed principally for application to the wafer-scale integration of one and two-dimensional systolic arrays, they can also be used to construct networks in well studied models of geometric complexity. Some of the algorithms are of considerable practical interest.

In this paper, we introduce a new framework within which to study VLSI layout problems. The framework is based on a straightforward generalization of the Lipton-Tarjan notion of a planar separator and, unlike previous approaches, leads to universally close upper and lower bounds on the layout area and crossing number of an arbitrary network. In addition, the framework permits simple proofs of results previously thought to be difficult and is suitable for use with good bisection width heurisitcs.

In this paper, we use crossing number and wire area arguments to find lower bounds on the layout area and maximum edge length of a variety of computationally useful networks. In particular, we describe 1) an N-node planar graph which has layout area Θ(NlogN), and maximum edge length Θ(N1/2/log1/2N), 2) an N-node graph with an O(N1/2)-separator which has layout area Θ(Nlog2N) and maximum edge length Θ(N1/2logN/loglogN), and 3) an N-node graph with an O(N1-1/r)-separator which has maximum edge length Θ(N1-1/r) for any r ≥ 3.

In this extended abstract, we present several new layouts for the shuffle-exchange graph, including one which requires only 0(n2/log2n) area. The optimal layout is described and analyzed in section 3. The analysis is heavily dependent on several combinatorial results which we state in section 2 and prove in the appendix. The other layouts are described in section 4. Although these layouts are not asymptotically optimal (most require 0(n2/log3/2n) area), the theory behind their development is interesting and may eventually lead to good practical layouts as well as other asymptotically optimal layouts.