Bruce Maggs

Journal article ACM Transactions on Algorithms · March 9, 2023 This article presents universal algorithms for clustering problems, including the widely studied k-median, k-means, and k-center objectives. The input is a metric space containing all potential client locations. The algorithm must select k cluster centers ... Full text Cite

Foundations of Differentially Oblivious Algorithms

Journal article Journal of the ACM · August 26, 2022 It is well-known that a program's memory access pattern can leak information about its input. To thwart such leakage, most existing works adopt the technique of oblivious RAM (ORAM) simulation. Such an obliviousness notion has stimulated much debate. Altho ... Full text Cite

Message from the program chairs

Journal article SIGCOMM 2022 Proceedings of the ACM SIGCOMM 2022 Conference · August 22, 2022 Cite

Techniques for smart and secure 5G softwarized networks

Journal article Annales Des Telecommunications Annals of Telecommunications · October 1, 2019 Full text Cite

On mapping the interconnections in today's internet

Journal article IEEE ACM Transactions on Networking · October 1, 2019 Internet interconnections are the means by which networks exchange traffic between one another. These interconnections are typically established in facilities that have known geographic locations, and are owned and operated by so-called colocation and inte ... Full text Cite

On hierarchical routing in doubling metrics

Journal article ACM Transactions on Algorithms · August 1, 2016 We study the problem of routing in doubling metrics and show how to perform hierarchical routing in such metrics with small stretch and compact routing tables (i.e., with a small amount of routing information stored at each vertex). We say that a metric (X ... Full text Cite

Mutual Embeddings

Journal article Journal of Interconnection Networks · October 1, 2015 This paper introduces a type of graph embedding called a mutual embedding. A mutual embedding between two n-node graphs G1=(V1, E1) and G2=(V2,E2) is an identification of the vertices of V1 and V2, i.e., a bijection :V1aV 2, together with an embedding of G ... Full text Cite

Protecting Websites from Attack with Secure Delivery Networks

Journal article Computer · April 1, 2015 Secure delivery networks can help prevent or mitigate the most common attacks against mission-critical websites. A case study from a leading provider of content delivery services illustrates one such network's operation and effectiveness. ... Full text Cite

Peer-assisted content distribution in Akamai netsession

Journal article Proceedings of the ACM SIGCOMM Internet Measurement Conference IMC · December 16, 2013 Content distribution systems have traditionally adopted one of two architectures: infrastructure-based content delivery networks (CDNs), in which clients download content from dedicated, centrally managed servers, and peer-to-peer CDNs, in which clients do ... Full text Cite

Less pain, most of the gain: Incrementally deployable ICN

Journal article Computer Communication Review · December 1, 2013 Information-Centric Networking (ICN) has seen a significant resurgence in recent years. ICN promises benefits to users and service providers along several dimensions (e.g., performance, security, and mobility). These benefits, however, come at a non-trivia ... Full text Cite

Less pain, most of the gain: Incrementally deployable ICN

Journal article SIGCOMM 2013 Proceedings of the ACM SIGCOMM 2013 Conference on Applications Technologies Architectures and Protocols for Computer Communication · August 12, 2013 Information-Centric Networking (ICN) has seen a significant resurgence in recent years. ICN promises benefits to users and service providers along several dimensions (e.g., performance, security, and mobility). These benefits, however, come at a non-trivia ... Full text Cite

Pushing CDN-ISP collaboration to the limit

Journal article Computer Communication Review · July 1, 2013 Today a spectrum of solutions are available for istributing content over the Internet, ranging from commercial CDNs to ISP-operated CDNs to content-provider-operated CDNs to peer-to-peer CDNs. Some deploy servers in just a few large data centers while othe ... Full text Cite

Enabling content-aware traffic engineering

Journal article Computer Communication Review · October 1, 2012 Today, a large fraction of Internet traffic is originated by Content Delivery Networks (CDNs). To cope with increasing demand for content, CDNs have deployed massively distributed infrastructures. These deployments pose challenges for CDNs as they have to ... Full text Cite

Simultaneous source location

Journal article ACM Transactions on Algorithms · December 1, 2009 We consider the problem of simultaneous source location: selecting locations for sources in a capacitated graph such that a given set of demands can be satisfied simultaneously, with the goal of minimizing the number of locations chosen. For general direct ... Full text Cite

Cutting the electric bill for internet-scale systems

Journal article Computer Communication Review · August 16, 2009 Energy expenses are becoming an increasingly important fraction of data center operating costs. At the same time, the energy expense per unit of computation can vary significantly between two difierent locations. In this paper, we characterize the variatio ... Full text Cite

Holistic query transformations for dynamic web applications

Journal article Proceedings International Conference on Data Engineering · July 8, 2009 A promising approach to scaling Web applications is to distribute the server infrastructure on which they run. This approach, unfortunately, can introduce latency between the application and database servers, which in turn increases the network latency of ... Full text Cite

On the performance benefits of multihoming route control

Journal article IEEE ACM Transactions on Networking · February 1, 2008 Multihoming is increasingly being employed by large enterprises and data centers to extract good performance and reliability from their ISP connections. Multihomed end networks today can employ a variety of route control products to optimize their Internet ... Full text Cite

Erratum: "On the performance benefits of multihoming route control" (IEEE/ACM Transactions on Networking)

Journal article IEEE ACM Transactions on Networking · January 1, 2008 Full text Cite

Scalable query result caching for web applications

Journal article Proceedings of the VLDB Endowment · January 1, 2008 The backend database system is often the performance bottleneck when running web applications. A common approach to scale the database component is query result caching, but it faces the challenge of maintaining a high cache hit rate while effciently ensur ... Full text Cite

On the impact of route monitor selection

Journal article Proceedings of the ACM SIGCOMM Internet Measurement Conference IMC · December 1, 2007 Several route monitoring systems have been set up to help understand the Internet routing system. They operate by gathering realtime BGP updates from different networks. Many studies have relied on such data sources by assuming reasonably good coverage and ... Full text Cite

Portcullis: Protecting connection setup from denial-of-capability attacks

Journal article Computer Communication Review · October 1, 2007 Systems using capabilities to provide preferential service to selected flows have been proposed as a defense against large-scale network denial-of-service attacks. While these systems offer strong protection for established network flows, the Denial-of-Cap ... Full text Cite

Invalidation clues for database scalability services

Journal article Proceedings International Conference on Data Engineering · September 24, 2007 For their scalability needs, data-intensive Web applications can use a Database Scalability Service (DBSS), which caches applications' query results and answers queries on their behalf. One way for applications to address their security/privacy concerns wh ... Full text Cite

Portcullis: Protecting connection setup from denial-of-capability attacks

Journal article ACM SIGCOMM 2007 Conference on Computer Communications · August 27, 2007 Systems using capabilities to provide preferential service to selected flows have been proposed as a defense against large-scale network denial-of-service attacks. While these systems offer strong protection for established network flows, the Denial-of-Cap ... Full text Cite

Simultaneous scalability and security for data-intensive web applications

Journal article Proceedings of the ACM SIGMOD International Conference on Management of Data · December 1, 2006 For Web applications in which the database component is the bottleneck, scalability can be provided by a third-party Database Scalability Service Provider (DSSP) that caches application data and supplies query answers on behalf of the application. Cost-eff ... Full text Cite

A survey of congestion+dilation results for packet scheduling

Journal article 2006 IEEE Conference on Information Sciences and Systems Ciss 2006 Proceedings · January 1, 2006 This paper surveys a collection of theoretical results that relate the congestion and dilation of the paths taken by a set of packets in a network to the time required for their delivery, or to the rate at which they can be delivered, where the congestion ... Full text Cite

Finding effective support-tree preconditioned

Journal article Annual ACM Symposium on Parallelism in Algorithms and Architectures · December 1, 2005 In 1995, Gremban, Miller, and Zagha introduced support-tree preconditioners and a parallel algorithm called supporttree conjugate gradient (STCG) for solving linear systems of the form Ax = b, where A is an n × n Laplacian matrix. A Laplacian is a symmetri ... Full text Cite

A scalability service for dynamic Web applications

Journal article 2nd Biennial Conference on Innovative Data Systems Research Cidr 2005 · January 1, 2005 Providers of dynamicWeb applications are currently unable to accommodate heavy usage without significant investment in infrastructure and in-house management capability. Our goal is to develop technology to enable a third party to offer scalability as a su ... Cite

The feasibility of supporting large-scale live streaming applications with dynamic application end-points

Journal article Computer Communication Review · August 30, 2004 While application end-point architectures have proven to be viable solutions for large-scale distributed applications such as distributed computing and file-sharing, there is little known about its feasibility for more bandwidth-demanding applications such ... Full text Cite

Locating Internet routing instabilities

Journal article Computer Communication Review · August 30, 2004 This paper presents a methodology for identifying the autonomous system (or systems) responsible when a routing change is observed and propagated by BGP. The origin of such a routing instability is deduced by examining and correlating BGP updates for many ... Full text Cite

A comparison of overlay routing and multihoming route control

Journal article Computer Communication Review · August 30, 2004 The limitations of BGP routing in the Internet are often blamed for poor end-to-end performance and prolonged connectivity interruptions. Recent work advocates using overlays to effectively bypass BGP's path selection in order to improve performance and fa ... Full text Cite

Simultaneous source location

Journal article Lecture Notes in Computer Science Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics · January 1, 2004 We consider the problem of Simultaneous Source Location -selecting locations for sources in a capacitated graph such that a given set of demands can be satisfied. We give an exact algorithm for trees and show how this can be combined with a result of Räcke ... Full text Cite

An analysis of live streaming workloads on the internet

Journal article Proceedings of the 2004 ACM SIGCOMM Internet Measurement Conference IMC 2004 · January 1, 2004 In this paper, we study the live streaming workload from a large content delivery network. Our data, collected over a 3 month period, contains over 70 million requests for 5,000 distinct URLs from clients in over 200 countries. To our knowledge, this is th ... Full text Cite

Availability, usage, and deployment characteristics of the domain name system

Journal article Proceedings of the 2004 ACM SIGCOMM Internet Measurement Conference IMC 2004 · January 1, 2004 The Domain Name System (DNS) is a critical part of the Internet's infrastructure, and is one of the few examples of a robust, highly-scalable, and operational distributed system. Although a few studies have been devoted to characterizing its properties, su ... Full text Cite

A methodology for estimating interdomain Web traffic demand

Journal article Proceedings of the 2004 ACM SIGCOMM Internet Measurement Conference IMC 2004 · January 1, 2004 This paper introduces a methodology for estimating interdomain Web traffic flows between all clients worldwide and the servers belonging to over one thousand content providers. The idea is to use the server logs from a large Content Delivery Network (CDN) ... Full text Cite

Efficient content location using interest-based locality in peer-to-peer systems

Journal article Proceedings IEEE INFOCOM · December 1, 2003 Locating content in decentralized peer-to-peer systems is a challenging problem. Gnutella, a popular file-sharing application, relies on flooding queries to all peers. Although flooding is simple and robust, it is not scalable. We explore how to retain the ... Full text Cite

A Measurement-Based Analysis of Multihoming

Journal article Computer Communication Review · August 25, 2003 Multihoming has traditionally been employed by stub networks to enhance the reliability of their network connectivity. With the advent of commercial "intelligent route control" products, stubs now leverage multihoming to improve performance. Although multi ... Full text Cite

Space-efficient finger search on degree-balanced search trees

Journal article Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms · January 1, 2003 We show how to support the finger search operation on degree-balanced search trees in a space-efficient, manner that retains a worst-case time bound of O(logd), where d is the difference in rank between successive search targets. While most existing tree-b ... Cite

Designing overlay multicast networks for streaming

Journal article Annual ACM Symposium on Parallel Algorithms and Architectures · January 1, 2003 In this paper we present a polynomial time approximation algorithm for designing a multicast overlay network. The algorithm finds a solution that satisfies capacity and reliability constraints to within a constant factor of optimal, and cost to within a lo ... Full text Cite

COMMUNICATION-EFFICIENT PARALLEL ALGORITHMS FOR DISTRIBUTED RANDOM-ACCESS MACHINES.

Journal article Algorithmica New York · January 1, 2003 This paper introduces a model for parallel computation, called the distributed random-assess machine (DRAM), inwhich the communication requirements of parallel algorithms can be evaluated. A DRAM is an abstraction of a parallel computer in which memory acc ... Cite

Globally distributed content delivery

Journal article IEEE Internet Computing · September 1, 2002 A company, Akamai Technologies, evolved out of an MIT research effort aimed at solving a flash crowd problem. An approach based on the observation that serving Web content from a single location can present serious problems for site scalability, reliabilit ... Full text Cite

Preface

Journal article Aquatic Toxicology · January 1, 2002 Full text Cite

Enabling efficient content location and retrieval in peer-to-peer systems by exploiting locality in interests

Journal article Computer Communication Review · January 1, 2002 Full text Cite

On the bisection width and expansion of butterfly networks

Journal article Theory of Computing Systems · January 1, 2001 This paper proves tight bounds on the bisection width and expansion of butterfly networks with and without wraparound. We show that the bisection width of an n-input butterfly network is 2(√2 -1)n + o(n) ≈ 0.82n without wraparound, and n with wraparound. T ... Full text Cite

Protocols for asymmetric communication channels

Journal article Journal of Computer and System Sciences · January 1, 2001 In this paper we examine the problem of sending an n-bit data item from a client to a server across an asymmetric communication channel. We demonstrate that there are scenarios in which a high-speed link from the server to the client can be used to greatly ... Full text Cite

On the benefit of supporting virtual channels in wormhole routers

Journal article Journal of Computer and System Sciences · January 1, 2001 This paper analyzes the impact of virtual channels on the performance of wormhole routing algorithms. We study wormhole routing on network in which each physical channel, i.e., communication link, can support up to B virtual channels. We show that it is po ... Full text Cite

Improved routing and sorting on multibutterflies

Journal article Algorithmica New York · December 1, 2000 This paper shows that an N-node AKS network 0as described by Paterson) can be embedded in a (3N/2)-node twinbutterfly network (i.e., a multibutterfly constructed by superimposing two butterfly networks) with load 1, congestion 1, and dilation 2. The result ... Full text Cite

Sorting-based selection algorithms for hypercubic networks

Journal article Algorithmica New York · January 1, 2000 This paper presents several deterministic algorithms for selecting the kth largest record from a set of n records on any n-node hypercubic network. All of the algorithms are based on the selection algorithm of Cole and Yap, as well as on various sorting al ... Full text Cite

Tight analyses of two local load balancing algorithms

Journal article SIAM Journal on Computing · January 1, 1999 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 maximu ... Full text Cite

Tradeoffs between parallelism and fill in nested dissection

Journal article Annual ACM Symposium on Parallel Algorithms and Architectures · January 1, 1999 In this paper we demonstrate that parallelism and fill can be traded off in orders for Gaussian elimination. While the well-known nested dissection algorithm produces very parallel elimination orders, we show that by reducing the parallelism it is possible ... Full text Cite

Simple algorithms for routing on butterfly networks with bounded queues

Journal article SIAM Journal on Computing · January 1, 1999 This paper examines several simple algorithms for routing packets on butterfly networks with bounded queues. We show that for any greedy queuing protocol, a routing problem in which each of the N inputs sends a packet to a randomly chosen output requires O ... Full text Cite

Fast algorithms for finding O(congestion + dilation) packet routing schedules

Journal article Combinatorica · January 1, 1999 In 1988, Leighton, Maggs, and Rao showed that for any network and any set of packets whose paths through the network are fixed and edge-simple, there exists a schedule for routing the packets to their destinations in O(c+d) steps using constant-size queues ... Full text Cite

Protocols for asymmetric communication channels

Journal article Annual Symposium on Foundations of Computer Science Proceedings · December 1, 1998 The problem of sending an n-bit data item from a client to a server across a asymmetric communication channel is investigated. The scenarios in which a high-speed link from the server to the client can be used to greatly reduce the number of bits sent from ... Cite

Real-time emulations of bounded-degree networks

Journal article Information Processing Letters · June 16, 1998 Full text Cite

An experimental analysis of parallel sorting algorithms

Journal article Theory of Computing Systems · January 1, 1998 We have developed a methodology for predicting the performance of parallel algorithms on real parallel machines. The methodology consists of two steps. First, we characterize a machine by enumerating the primitive operations that it is capable of performin ... Full text Cite

On the bisection width and expansion of butterfly networks

Journal article Proceedings of the 1st Merged International Parallel Processing Symposium and Symposium on Parallel and Distributed Processing IPPS Spdp 1998 · January 1, 1998 The paper proves tight bounds on the bisection width and expansion of butterfly networks with and without wraparound. Previously it was known that the bisection width of an n-input butterfly with wraparound is n. We show that without wraparound, the bisect ... Full text Cite

Randomized protocols for low-congestion circuit routing in multistage interconnection networks

Journal article Conference Proceedings of the Annual ACM Symposium on Theory of Computing · January 1, 1998 In this paper we study randomized algorithms for circuit switching on multistage networks related to the butterfly. We devise algorithms that route messages by constructing circuits (or paths) for the messages with small congestion, dilation, and setup tim ... Full text Cite

Exploiting locality for data management in systems of limited bandwidth

Journal article Annual Symposium on Foundations of Computer Science Proceedings · December 1, 1997 The static and dynamic data management are investigated in computer systems where the computing nodes are connected by a relatively sparse network. In the static model, it is assume that the given application for which the rates of read and write accesses ... Cite

Parallelizing elimination orders with linear fill

Journal article Annual Symposium on Foundations of Computer Science Proceedings · December 1, 1997 This paper presents an algorithm for finding parallel elimination orders for Gaussian elimination. Viewing a system of equations as a graph, the algorithm can be applied directly to interval graphs and chordal graphs. For general graphs, the algorithm can ... Cite

Reconfiguring arrays with faults part I: Worst-case faults

Journal article SIAM Journal on Computing · January 1, 1997 In this paper we study the ability of array-based networks to tolerate worst-case faults. We show that an N × N two-dimensional array can sustain N1-∈ worst-case faults for any fixed ∈ > 0, and still emulate T steps of a fully functioning N × N ... Full text Cite

Improved routing and sorting on multibutterflies

Journal article Conference Proceedings of the Annual ACM Symposium on Theory of Computing · January 1, 1997 This paper shows that an N-node AKS network (as described by Paterson) can be embedded in a 3N/2-node degree-8 multibutterfly network with load 1, congestion 1, and dilation 2. The result has several implications, including the first deterministic algorith ... Full text Cite

Work-preserving emulations of fixed-connection networks

Journal article Journal of the ACM · January 1, 1997 In this paper, we study the problem of emulating TG steps of an NG-node guest network, G, on an NH-node host network, H. We call an emulation work-preserving if the time required by the host, TH, is O(TG Full text Cite

Parallel Algorithms

Journal article ACM Computing Surveys · March 1, 1996 Full text Cite

A Maximum Likelihood Stereo Algorithm

Journal article Computer Vision and Image Understanding · January 1, 1996 A stereo algorithm is presented that optimizes a maximum likelihood cost function. The maximum likelihood cost function assumes that corresponding features in the left and right images are normally distributed about a common true value and consists of a we ... Full text Cite

On-line algorithms for path selection in a nonblocking network

Journal article SIAM Journal on Computing · January 1, 1996 This paper presents the first optimal-time algorithms for path selection in an optimalsize 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 ... Full text Cite

On the benefit of supporting virtual channels in wormhole routers

Journal article Annual ACM Symposium on Parallel Algorithms and Architectures · January 1, 1996 This paper analyzes the impact of virtual channels on the performance of wormhole routing algorithms. We show that in any network in which each physical channel can emulate up to Q virtual channels, it is possible to route any set of L-bit messages whose p ... Full text Cite

Critical look at three of parallel computing's maxims

Journal article Proceedings of the International Symposium on Parallel Architectures Algorithms and Networks I Span · January 1, 1996 This paper takes a critical look at the following three maxims. 1. Parallel architecture is converging on a design based on commodity microprocessor chips. 2. Wormhole routing is decidedly more efficient than store-and-forward routing. 3. The PRAM is an un ... Cite

Routing on butterfly networks with random faults

Journal article Annual Symposium on Foundations of Computer Science Proceedings · December 1, 1995 In this paper we show that even if every node or edge in an N-node butterfly network fails independently with some constant probability, p, it is still possible to identify a set of Θ(N) nodes between which packets can be routed in any permutation in O(log ... Cite

Packet routing and job-shop scheduling in O(congestion+dilation) steps

Journal article Combinatorica · June 1, 1994 In this paper, we prove that there exists a schedule for routing any set of packets with edge-simple paths, on any network, in O(c+d) steps, where c is the congestion of the paths in the network, and d is the length of the longest path. The result has appl ... Full text Cite

Randomized routing and sorting on fixed-connection networks

Journal article Journal of Algorithms · January 1, 1994 This paper presents a general paradigm for the design of packet routing algorithms for fixed-connection networks. Its basis is a randomized on-line algorithm for scheduling any set of N packets whose paths have congestion c on any bounded-degree leveled ne ... Full text Cite

A Parallel Algorithm for Reconfiguring a Multibutterfly Network with Faulty Switches

Journal article IEEE Transactions on Computers · January 1, 1994 This paper describes a deterministic algorithm for reconfiguring a multibutterfly network with faulty switches. Unlike previous reconfiguration algorithms, the algorithm is performed entirely by the network, without the aid of any off-line computation, eve ... Full text Cite

Multi-scale self-simulation: A technique reconfiguring arrays with faults

Journal article Proceedings of the Annual ACM Symposium on Theory of Computing · June 1, 1993 In this paper we study the ability of array-based networks to tolerate faults. We show that an N x N two- dimensional array can sustain N1-ϵ worst-case faults, for any fixed e > 0, and still emulate a fully functioning N x N array with only constant slowdo ... Full text Cite

Approximate load balancing on dynamic and asynchronous networks

Journal article Proceedings of the Annual ACM Symposium on Theory of Computing · June 1, 1993 This paper presents a simple local algorithm for load balancing in a distributed network. The algorithm makes no assumption about the structure of the network. It can be executed on a synchronous networic with fixed topology, a synchronous network with dyn ... Full text Cite

Randomly wired multistage networks

Journal article Statistical Science · January 1, 1993 Randomly wired multistage networks have recently been shown to outperform traditional multistage networks in three respects. First, they have fast deterministic packet-switching and circuit-switching algorithms for routing permutations. Second, they are no ... Full text Cite

Simple algorithms for routing on butterfly networks with bounded queues

Journal article Proceedings of the Annual ACM Symposium on Theory of Computing · July 1, 1992 This paper examines several simple algorithms for routing packets on butterfly networks with bounded queues. We show that for any pure queuing protocol, a routing problem in which each of the N inputs sends a packet to a randomly chosen output requires O(l ... Full text Cite

Fast Algorithms for Routing Around Faults in Multibutterflies and Randomly-Wired Splitter Networks

Journal article IEEE Transactions on Computers · January 1, 1992 This paper describes simple deterministic O(log N) step algorithms for routing permutations of packets in multibutterflies and randomly-wired splitter networks. The algorithms are robust against faults (even in the worst case), and are efficient from a pra ... Full text Cite

Fast algorithms for bit-serial routing on a hypercube

Journal article Mathematical Systems Theory · December 1, 1991 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 ... Full text Cite

Empirical evaluation of randomly-wired multistage networks

Journal article Proceedings IEEE International Conference on Computer Design VLSI in Computers and Processors · September 1, 1990 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 ... Cite

On-line algorithms for path selection in a nonblocking network

Journal article undefined · January 1, 1990 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 ... Full text Cite

Fast algorithms for bit-serial routing on a hypercube

Journal article Algorithms and Architectures · January 1, 1990 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 ... Full text Cite

Expanders might be practical: Fast algorithms for routing around faults on multibutterflies

Journal article Annual Symposium on Foundations of Computer Science Proceedings · January 1, 1989 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 mul ... Full text Cite

Work-preserving emulations of fixed-connection networks

Journal article undefined · January 1, 1989 Full text Cite

Communication-efficient parallel algorithms for distributed random-access machines

Journal article Algorithmica · March 1, 1988 This paper introduces a model for parallel computation, called the distributed randomaccess machine (DRAM), in which the communication requirements of parallel algorithms can be evaluated. A DRAM is an abstraction of a parallel computer in which memory acc ... Full text Cite

Minimum-cost spanning tree as a path-finding problem

Journal article Information Processing Letters · January 25, 1988 In this paper we show that the minimum-cost spanning tree is a special case of the closed semiring path-finding problem. This observation gives us a nonrecursive algorithm for finding minimum-cost spanning trees on mesh-connected computers which has the sa ... Full text Cite

Universal packet routing algorithms

Journal article Annual Symposium on Foundations of Computer Science Proceedings · January 1, 1988 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 ... Full text Cite

COMMUNICATION-EFFICIENT PARALLEL GRAPH ALGORITHMS.

Journal article Proceedings of the International Conference on Parallel Processing · December 1, 1986 Communication bandwidth is a resource ignored by most parallel random-access machine (PRAM) models. It is shown that many graph problems can be solved in parallel, not only with polylogarithmic performance, but with efficient communication at each step of ... Cite

Preface

Journal article Methods in Enzymology · January 1, 1985 Full text Cite