Skip to main content
construction release_alert
Scholars@Duke will be undergoing maintenance April 11-15. Some features may be unavailable during this time.
cancel

Bruce Maggs

Pelham Wilder Distinguished Professor of Computer Science
Computer Science
Box 90129, Durham, NC 27708-0129
LSRC D324, Durham, NC 27708

Selected Publications


No Root Store Left Behind

Conference HotNets 2023 - Proceedings of the 22nd ACM Workshop on Hot Topics in Networks · November 28, 2023 When a root certificate authority (CA) in the Web PKI misbehaves, primary root-store operators such as Mozilla and Google respond by distrusting that CA. However, full distrust is often too broad, so root stores often implement partial distrust of roots, s ... Full text Cite

Robust Algorithms for TSP and Steiner Tree

Conference ACM Transactions on Algorithms · March 9, 2023 Robust optimization is a widely studied area in operations research, where the algorithm takes as input a range of values and outputs a single solution that performs well for the entire range. Specifically, a robust algorithm aims to minimize regret, defin ... Full text Cite

Universal Algorithms for Clustering Problems

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

Hammurabi: A Framework for Pluggable, Logic-Based X.509 Certificate Validation Policies

Conference Proceedings of the ACM Conference on Computer and Communications Security · November 7, 2022 This paper proposes using a logic programming language to disentangle X.509 certificate validation policy from mechanism. Expressing validation policies in a logic programming language provides multiple benefits. First, policy and mechanism can be more ind ... 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

AnyOpt: Predicting and optimizing IP Anycast performance

Conference SIGCOMM 2021 - Proceedings of the ACM SIGCOMM 2021 Conference · August 9, 2021 The key to optimizing the performance of an anycast-based system (e.g., the root DNS or a CDN) is choosing the right set of sites to announce the anycast prefix. One challenge here is predicting catchments. A naïve approach is to advertise the prefix from ... Full text Cite

Puncturable Pseudorandom Sets and Private Information Retrieval with Near-Optimal Online Bandwidth and Time

Conference Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) · January 1, 2021 Imagine one or more non-colluding servers each holding a large public database, e.g., the repository of DNS entries. Clients would like to access entries in this database without disclosing their queries to the servers. Classical private information retrie ... Full text Cite

A Bird's Eye View of the World's Fastest Networks

Conference Proceedings of the ACM SIGCOMM Internet Measurement Conference, IMC · October 27, 2020 Low latency is of interest for a variety of applications. The most stringent latency requirements arise in financial trading, where sub-microsecond differences matter. As a result, firms in the financial technology sector are pushing networking technology ... Full text Cite

Robust algorithms for TSP and steiner tree

Other Leibniz International Proceedings in Informatics, LIPIcs · June 1, 2020 Robust optimization is a widely studied area in operations research, where the algorithm takes as input a range of values and outputs a single solution that performs well for the entire range. Specifically, a robust algorithm aims to minimize regret, defin ... Full text Cite

Untangling Header Bidding Lore: Some Myths, Some Truths, and Some Hope

Conference Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) · January 1, 2020 Header bidding (HB) is a relatively new online advertising technology that allows a content publisher to conduct a client-side (i.e., from within the end-user’s browser), real-time auction for selling ad slots on a web page. We developed a new browser exte ... Full text Cite

RPKI is coming of age: A longitudinal study of RPKI deployment and invalid route origins

Conference Proceedings of the ACM SIGCOMM Internet Measurement Conference, IMC · October 21, 2019 Despite its critical role in Internet connectivity, the Border Gateway Protocol (BGP) remains highly vulnerable to attacks such as prefix hijacking, where an Autonomous System (AS) announces routes for IP space it does not control. To address this issue, t ... Full text 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

Foundations of differentially oblivious algorithms

Conference Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms · January 1, 2019 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

Gearing up for the 21 st century space race

Conference HotNets 2018 - Proceedings of the 2018 ACM Workshop on Hot Topics in Networks · November 15, 2018 A new space race is imminent, with several industry players working towards satellite-based Internet connectivity. While satellite networks are not themselves new, these recent proposals are aimed at orders of magnitude higher bandwidth and much lower late ... Full text Cite

Is the web ready for OCSP must-staple?

Conference Proceedings of the ACM SIGCOMM Internet Measurement Conference, IMC · October 31, 2018 TLS, the de facto standard protocol for securing communications over the Internet, relies on a hierarchy of certificates that bind names to public keys. Naturally, ensuring that the communicating parties are using only valid certificates is a necessary fir ... Full text Cite

Message from the chairs

Conference 21st Conference on Innovation in Clouds, Internet and Networks, ICIN 2018 · June 29, 2018 Full text Cite

Redesigning cdn-broker interactions for improved content delivery

Conference CoNEXT 2017 - Proceedings of the 2017 13th International Conference on emerging Networking EXperiments and Technologies · November 28, 2017 Various trends are reshaping Internet video delivery: exponential growth in video traffic, rising expectations of high video quality of experience (QoE), and the proliferation of varied content delivery network (CDN) deployments (e.g., cloud computing-base ... Full text Cite

Understanding the role of registrars in DNSSEC deployment

Conference Proceedings of the ACM SIGCOMM Internet Measurement Conference, IMC · November 1, 2017 The Domain Name System (DNS) provides a scalable, flexible name resolution service. Unfortunately, its unauthenticated architecture has become the basis for many security attacks. To address this, DNS Security Extensions (DNSSEC) were introduced in 1997. D ... Full text Cite

Message from the program chairs

Conference 2017 2nd ACM/IEEE Symposium on Edge Computing, SEC 2017 · October 12, 2017 Full text Cite

No Root Store Left Behind

Conference HotNets 2023 - Proceedings of the 22nd ACM Workshop on Hot Topics in Networks · November 28, 2023 When a root certificate authority (CA) in the Web PKI misbehaves, primary root-store operators such as Mozilla and Google respond by distrusting that CA. However, full distrust is often too broad, so root stores often implement partial distrust of roots, s ... Full text Cite

Robust Algorithms for TSP and Steiner Tree

Conference ACM Transactions on Algorithms · March 9, 2023 Robust optimization is a widely studied area in operations research, where the algorithm takes as input a range of values and outputs a single solution that performs well for the entire range. Specifically, a robust algorithm aims to minimize regret, defin ... Full text Cite

Universal Algorithms for Clustering Problems

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

Hammurabi: A Framework for Pluggable, Logic-Based X.509 Certificate Validation Policies

Conference Proceedings of the ACM Conference on Computer and Communications Security · November 7, 2022 This paper proposes using a logic programming language to disentangle X.509 certificate validation policy from mechanism. Expressing validation policies in a logic programming language provides multiple benefits. First, policy and mechanism can be more ind ... 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

AnyOpt: Predicting and optimizing IP Anycast performance

Conference SIGCOMM 2021 - Proceedings of the ACM SIGCOMM 2021 Conference · August 9, 2021 The key to optimizing the performance of an anycast-based system (e.g., the root DNS or a CDN) is choosing the right set of sites to announce the anycast prefix. One challenge here is predicting catchments. A naïve approach is to advertise the prefix from ... Full text Cite

Puncturable Pseudorandom Sets and Private Information Retrieval with Near-Optimal Online Bandwidth and Time

Conference Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) · January 1, 2021 Imagine one or more non-colluding servers each holding a large public database, e.g., the repository of DNS entries. Clients would like to access entries in this database without disclosing their queries to the servers. Classical private information retrie ... Full text Cite

A Bird's Eye View of the World's Fastest Networks

Conference Proceedings of the ACM SIGCOMM Internet Measurement Conference, IMC · October 27, 2020 Low latency is of interest for a variety of applications. The most stringent latency requirements arise in financial trading, where sub-microsecond differences matter. As a result, firms in the financial technology sector are pushing networking technology ... Full text Cite

Robust algorithms for TSP and steiner tree

Other Leibniz International Proceedings in Informatics, LIPIcs · June 1, 2020 Robust optimization is a widely studied area in operations research, where the algorithm takes as input a range of values and outputs a single solution that performs well for the entire range. Specifically, a robust algorithm aims to minimize regret, defin ... Full text Cite

Untangling Header Bidding Lore: Some Myths, Some Truths, and Some Hope

Conference Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) · January 1, 2020 Header bidding (HB) is a relatively new online advertising technology that allows a content publisher to conduct a client-side (i.e., from within the end-user’s browser), real-time auction for selling ad slots on a web page. We developed a new browser exte ... Full text Cite

RPKI is coming of age: A longitudinal study of RPKI deployment and invalid route origins

Conference Proceedings of the ACM SIGCOMM Internet Measurement Conference, IMC · October 21, 2019 Despite its critical role in Internet connectivity, the Border Gateway Protocol (BGP) remains highly vulnerable to attacks such as prefix hijacking, where an Autonomous System (AS) announces routes for IP space it does not control. To address this issue, t ... Full text 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

Foundations of differentially oblivious algorithms

Conference Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms · January 1, 2019 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

Gearing up for the 21 st century space race

Conference HotNets 2018 - Proceedings of the 2018 ACM Workshop on Hot Topics in Networks · November 15, 2018 A new space race is imminent, with several industry players working towards satellite-based Internet connectivity. While satellite networks are not themselves new, these recent proposals are aimed at orders of magnitude higher bandwidth and much lower late ... Full text Cite

Is the web ready for OCSP must-staple?

Conference Proceedings of the ACM SIGCOMM Internet Measurement Conference, IMC · October 31, 2018 TLS, the de facto standard protocol for securing communications over the Internet, relies on a hierarchy of certificates that bind names to public keys. Naturally, ensuring that the communicating parties are using only valid certificates is a necessary fir ... Full text Cite

Message from the chairs

Conference 21st Conference on Innovation in Clouds, Internet and Networks, ICIN 2018 · June 29, 2018 Full text Cite

Redesigning cdn-broker interactions for improved content delivery

Conference CoNEXT 2017 - Proceedings of the 2017 13th International Conference on emerging Networking EXperiments and Technologies · November 28, 2017 Various trends are reshaping Internet video delivery: exponential growth in video traffic, rising expectations of high video quality of experience (QoE), and the proliferation of varied content delivery network (CDN) deployments (e.g., cloud computing-base ... Full text Cite

Understanding the role of registrars in DNSSEC deployment

Conference Proceedings of the ACM SIGCOMM Internet Measurement Conference, IMC · November 1, 2017 The Domain Name System (DNS) provides a scalable, flexible name resolution service. Unfortunately, its unauthenticated architecture has become the basis for many security attacks. To address this, DNS Security Extensions (DNSSEC) were introduced in 1997. D ... Full text Cite

Message from the program chairs

Conference 2017 2nd ACM/IEEE Symposium on Edge Computing, SEC 2017 · October 12, 2017 Full text Cite

Symmetric interdiction for matching problems

Conference Leibniz International Proceedings in Informatics, LIPIcs · August 1, 2017 Motivated by denial-of-service network attacks, we introduce the symmetric interdiction model, where both the interdictor and the optimizer are subject to the same constraints of the underlying optimization problem. We give a general framework that relates ... Full text Cite

CRLite: A Scalable System for Pushing All TLS Revocations to All Browsers

Conference Proceedings - IEEE Symposium on Security and Privacy · June 23, 2017 Currently, no major browser fully checks for TLS/SSL certificate revocations. This is largely due to the fact that the deployed mechanisms for disseminating revocations (CRLs, OCSP, OCSP Stapling, CRLSet, and OneCRL) are each either incomplete, insecure, i ... Full text Cite

Why is the internet so slow?!

Conference Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) · January 1, 2017 In principle, a network can transfer data at nearly the speed of light. Today’s Internet, however, is much slower: our measurements show that latencies are typically more than one, and often more than two orders of magnitude larger than the lower bound imp ... Full text Cite

A longitudinal, end-to-end view of the DnSSec ecosystem

Conference Proceedings of the 26th USENIX Security Symposium · January 1, 2017 The Domain Name System’s Security Extensions (DNSSEC) allow clients and resolvers to verify that DNS responses have not been forged or modified inflight. DNSSEC uses a public key infrastructure (PKI) to achieve this integrity, without which users can be su ... Cite

Measuring and applying invalid SSL Certificates: The silent majority

Conference Proceedings of the ACM SIGCOMM Internet Measurement Conference, IMC · November 14, 2016 SSL and TLS are used to secure the most commonly-used Internet protocols. As a result, the ecosystem of SSL certificates has been thoroughly studied, leading to a broad understanding of the strengths and weak-nesses of the certificates accepted by most web ... Full text Cite

Measurement and analysis of private key sharing in the HTTPS ecosystem

Conference Proceedings of the ACM Conference on Computer and Communications Security · October 24, 2016 The semantics of online authentication in the web are rather straightforward: if Alice has a certificate binding Bob's name to a public key, and if a remote entity can prove knowledge of Bob's private key, then (barring key compromise) that remote entity m ... 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

Reducing Latency through Page-aware Management of Web Objects by Content Delivery Networks

Conference Performance Evaluation Review · June 1, 2016 As popular web sites turn to content delivery networks (CDNs) for full-site delivery, there is an opportunity to improve the end-user experience by optimizing the delivery of entire web pages, rather than just individual objects. In particular, this paper ... Full text Cite

An end-to-end measurement of certificate revocation in the Web's PKI

Conference Proceedings of the ACM SIGCOMM Internet Measurement Conference, IMC · October 28, 2015 Critical to the security of any public key infrastructure (PKI) is the ability to revoke previously issued certificates. While the overall SSL ecosystem is well-studied, the frequency with which certificates are revoked and the circumstances under which cl ... 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

Algorithmic nuggets in content delivery

Conference Computer Communication Review · July 1, 2015 This paper "peeks under the covers" at the subsystems that provide the basic functionality of a leading content delivery network. Based on our experiences in building one of the largest distributed systems in the world, we illustrate how sophisticated algo ... 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

A universal approach to data center network design

Conference ACM International Conference Proceeding Series · January 4, 2015 This paper proposes an approach to the design of large-scale general-purpose data center networks based on the notions of volume and area universality introduced by Leiserson in the 1980's in the context of VLSI design. In particular, we suggest that the p ... Full text Cite

Back-office web traffic on the internet

Conference Proceedings of the ACM SIGCOMM Internet Measurement Conference, IMC · November 5, 2014 Although traffic between Web servers and Web browsers is readily apparent to many knowledgeable end users, fewer are aware of the extent of server-to-server Web traffic carried over the public Internet. We refer to the former class of traffic as front-offi ... Full text Cite

The internet at the speed of light

Conference Proceedings of the 13th ACM Workshop on Hot Topics in Networks, HotNets 2014 · October 27, 2014 For many Internet services, reducing latency improves the user experience and increases revenue for the service provider. While in principle latencies could nearly match the speed of light, we find that infrastructural inefficiencies and protocol overheads ... 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 · September 5, 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

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

Reliable client accounting for P2P-infrastructure hybrids

Conference Proceedings of NSDI 2012: 9th USENIX Symposium on Networked Systems Design and Implementation · January 1, 2012 Content distribution networks (CDNs) have started to adopt hybrid designs, which employ both dedicated edge servers and resources contributed by clients. Hybrid designs combine many of the advantages of infrastructure-based and peer-to-peer systems, but th ... 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 · November 30, 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

Parallel algorithms

Chapter · November 20, 2009 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

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

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

Journal Article ACM SIGCOMM 2007: Conference on Computer Communications · December 17, 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

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

R-BGP: Staying connected in a connected world

Conference 4th Symposium on Networked Systems Design and Implementation, NSDI 2007 · January 1, 2007 Many studies show that, when Internet links go up or down, the dynamics of BGP may cause several minutes of packet loss. The loss occurs even when multiple paths between the sender and receiver domains exist, and is unwarranted given the high connectivity ... 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

Quorum placement in networks: Minimizing network congestion

Conference Proceedings of the Annual ACM Symposium on Principles of Distributed Computing · September 21, 2006 A quorum system over a universe of logical elements is a collection of subsets (quorums) of elements, any two of which intersect. In numerous distributed algorithms, the elements of the universe reside on the nodes of a physical network and the participati ... 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 · December 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

Quorum placement in networks to minimize access delays

Conference Proceedings of the Annual ACM Symposium on Principles of Distributed Computing · January 1, 2005 A quorum system is a family of sets (themselves called quorums), each pair of which intersect. In many distributed algorithms, the basic unit accessed by a client is a quorum of nodes. Such algorithms are used for applications such as mutual exclusion, dat ... Full text Cite

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

Journal Article Computer Communication Review · December 1, 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 · December 1, 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 · December 1, 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

Parallel algorithms

Chapter · January 1, 2004 The subject of this chapter is the design and analysis of parallel algorithms. Most of today’s computer algorithms are sequential, that is, they specify a sequence of steps in which each step consists of a single operation. As it has become more difficult ... 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 · January 1, 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

Routing and communication in interconnection networks

Conference Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) · January 1, 2002 Cite

Topic 06, complexity theory and algorithms

Conference Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) · January 1, 2001 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

On balls and bins with deletions

Conference Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) · January 1, 1998 We consider the problem of extending the analysis of balls and bins processes where a ball is placed in the least loaded of d randomly chosen bins to cover deletions. In particular, we are interested in the case where the system maintains a fixed load, and ... 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

Messagfer om the organizers

Conference 3rd International Symposium on Parallel Architectures, Algorithms, and Networks, I-SPAN 1997 · January 1, 1997 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 array in O( ... 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(TGNG/NH), because then both the guest and host networks ... 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

Models of parallel computation: A survey and synthesis

Conference Proceedings of the Annual Hawaii International Conference on System Sciences · January 1, 1995 In the realm of sequential computing, the random access machine has successfully provided an underlying model of computation that has promoted consistency and coordination among algorithm developers, computer architects and language experts. In the realm o ... Full text Cite

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

Conference Proceedings of the Annual Hawaii International Conference on System Sciences · January 1, 1995 In 1988, Leighton, Maggs and Rao (1988) 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 ... Full text 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

An algorithm for finding predecessors in integer sets

Conference Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) · January 1, 1993 This paper presents a data structure that supports the operations of inserting and deleting elements drawn from a universe U={0⋯u-1} into a set S, and for finding the predecessors of elements of U in S. We consider both random inputs and worst-case inputs. ... Full text Cite

The role of randomness in the design of interconnection networks

Conference Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) · January 1, 1993 It has recently been discovered that randomly-wired interconnection networks outperform traditional well-structured networks in several notable respects. Among other things, randomly-wired networks have been found to be exceptionally fault-tolerant and wel ... Full text Cite

Sorting-based selection algorithms for hypercubic networks

Conference Proceedings of 7th International Parallel Processing Symposium, IPPS 1993 · January 1, 1993 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 (1985), as well as on various sor ... 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

On the fault tolerance of some popular bounded-degree networks

Conference Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS · January 1, 1992 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 ... 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

A comparison of sorting algorithms for the connection machine CM-2

Conference Proceedings of the 3rd Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 1991 · June 1, 1991 We have implemented three parallel sorting algorithms on the Connection Machine Supercomputer model CM-2: Batcher's bitonic sort, a parallel radix sort, and a sample sort similar to Reif and Valiant's flashsort. We have also evaluated the implementation of ... 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

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

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