Arrow Research search

Author name cluster

Bruce M. Maggs

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

18 papers
1 author row

Possible papers

18

SODA Conference 2019 Conference Paper

Foundations of Differentially Oblivious Algorithms

  • T. -H. Hubert Chan
  • Kai-Min Chung
  • Bruce M. Maggs
  • Elaine Shi

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. Although ORAM techniques have significantly improved over the past few years, the concrete overheads are arguably still undesirable for real-world systems — part of this overhead is in fact inherent due to a well-known logarithmic ORAM lower bound by Goldreich and Ostrovsky. To make matters worse, when the program's runtime or output length depend on secret inputs, it may be necessary to perform worst-case padding to achieve full obliviousness and thus incur possibly super-linear overheads. Inspired by the elegant notion of differential privacy, we initiate the study of a new notion of access pattern privacy, which we call “( ∊, δ )-differential obliviousness”. We separate the notion of ( ∊, δ )-differential obliviousness from classical obliviousness by considering several fundamental algorithmic abstractions including sorting small-length keys, merging two sorted lists, and range query data structures (akin to binary search trees). We show that by adopting differential obliviousness with reasonable choices of ∊ and δ, not only can one circumvent several impossibilities pertaining to full obliviousness, one can also, in several cases, obtain meaningful privacy with little overhead relative to the non-private baselines (i. e. , having privacy “almost for free”). On the other hand, we show that for very demanding choices of ∊ and δ, the same lower bounds for oblivious algorithms would be preserved for ( ∊, δ )-differential obliviousness.

Details

FOCS Conference 1998 Conference Paper

Protocols for Asymmetric Communication Channels

  • Micah Adler
  • Bruce M. Maggs

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 reduce the number of bits sent from the client to the server across a slower link. In particular, we assume that the data item is drawn from a probability distribution D that is known to the server but not to the client. We present several protocols in which the expected number of bits transmitted by the server and client are O(n) and O(H(D)+1), respectively, where H(D) is the binary entropy of D (and can range from 0 to n). These protocols are within a small constant factor of optimal in terms of the number of bits sent by the client. The expected number of rounds of communication between the server and client in the simplest of our protocols is O(H(D)). We also give a protocol for which the expected number of rounds is only 0(1), but which requires more computational effort on the part of the server. A third technique provides a tradeoff between the computational effort and the number of rounds.

Details

FOCS Conference 1997 Conference Paper

Exploiting Locality for Data Management in Systems of Limited Bandwidth

  • Bruce M. Maggs
  • Friedhelm Meyer auf der Heide
  • Berthold Vöcking
  • Matthias Westermann

This paper deals with data management in computer systems in which the computing nodes are connected by a relatively sparse network. We consider the problem of placing and accessing a set of shared objects that are read and written from the nodes in the network. These objects are, e. g. , global variables in a parallel program, pages or cache lines in a virtual shared memory system, shared files in a distributed file system, or pages in the World Wide Web. A data management strategy consists of a placement strategy that maps the objects (possibly dynamically and with redundancy) to the nodes, and an access strategy that describes how reads and writes are handled by the system (including the routing). We investigate static and dynamic data management strategies.

Details

FOCS Conference 1997 Conference Paper

Parallelizing Elimination Orders with Linear Fill

  • Claudson F. Bornstein
  • Bruce M. Maggs
  • Gary L. Miller
  • R. Ravi 0001

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 be used to parallelize the order produced by some other heuristic such as minimum degree. In this case, the algorithm is applied to the chordal completion that the heuristic generates from the input graph. In general, the input to the algorithm is a chordal graph G with n nodes and m edges. The algorithm produces an order with height at most O(log/sup 3/ n) times optimal, fill at most O(m), and work at most O(W*(G)), where W*(G) is the minimum possible work over all elimination orders for G. Experimental results show that when applied after some other heuristic, the increase in work and fill is usually small. In some instances the algorithm obtains an order that is actually better, in terms of work and fill, than the original one. We also present an algorithm that produces an order with a factor of log n less height, but with a factor of O(/spl radic/log n) more fill.

Details

FOCS Conference 1995 Conference Paper

Routing on Butterfly Networks with Random Faults

  • Richard Cole 0001
  • Bruce M. Maggs
  • Ramesh K. Sitaraman

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 /spl Theta/(N) nodes between which packets can be routed in any permutation in O(logN) steps, with high probability. Although the analysis as complicated, the routing algorithm itself is relatively simple.

Details

FOCS Conference 1992 Conference Paper

On the Fault Tolerance of Some Popular Bounded-Degree Networks

  • Frank Thomson Leighton
  • Bruce M. Maggs
  • Ramesh K. Sitaraman

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. >

Details

FOCS Conference 1989 Conference Paper

Expanders Might Be Practical: Fast Algorithms for Routing Around Faults on Multibutterflies

  • Frank Thomson Leighton
  • Bruce M. Maggs

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. >

Details

FOCS Conference 1988 Conference Paper

Universal Packet Routing Algorithms (Extended Abstract)

  • Frank Thomson Leighton
  • Bruce M. Maggs
  • Satish Rao

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. >

Details
v2026.09.13