Arrow Research search

Author name cluster

Michael A. Bender

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.

44 papers
2 author rows

Possible papers

44

FOCS Conference 2024 Conference Paper

Nearly Optimal List Labeling

  • Michael A. Bender
  • Alex Conway 0001
  • Martín Farach-Colton
  • Hanna Komlós
  • Michal Koucký 0001
  • William Kuszmaul
  • Michael E. Saks

The list-labeling problem captures the basic task of storing a dynamically changing set of up to $n$ elements in sorted order in an array of size $m=(1+\Theta(1))n$ • The goal is to support insertions and deletions while moving around elements within the array as little as possible. Until recently, the best known upper bound stood at $O(\log^{2}n)$ amortized cost. This bound, which was first established in 1981, was finally improved two years ago, when a randomized $O(\log^{3/2}n)$ expected-cost algorithm was discovered. The best randomized lower bound for this problem remains $\Omega(\log n)$, and closing this gap is considered to be a major open problem in data structures. In this paper, we present the See-Saw Algorithm, a randomized list-labeling solution that achieves a nearly optimal bound of $O(\log n \text{polyloglog}\ n)$ amortized expected cost. This bound is achieved despite at least three lower bounds showing that this type of result is impossible for large classes of solutions.

Details

FOCS Conference 2024 Conference Paper

Tight Bounds for Classical Open Addressing

  • Michael A. Bender
  • William Kuszmaul
  • Renfei Zhou

We introduce a classical open-addressed hash table, called rainbow hashing, that supports a load factor of up to 1 $-\varepsilon$, while also supporting $O(1)$ expected-time queries, and $O\left({\log \, \log {\varepsilon ^{ - 1}}} \right)$ expected-time insertions and deletions. We further prove that this tradeoff curve is optimal: any classical open-addressed hash table that supports load factor $1-\varepsilon$ must incur $\Omega \left({\log \, log{\varepsilon ^{ - 1}}} \right)$ expected time per operation. Finally, we extend rainbow hashing to the setting where the hash table is dynamically resized over time. Surprisingly, the addition of dynamic resizing does not come at any time cost-even while maintaining a load factor of $\geq 1-\varepsilon$ at all times, we can support $O(1)$ queries and $O\left({\log \, \log {\varepsilon ^{ - 1}}} \right)$ updates. Prior to our work, achieving any time bounds of the form $o(\varepsilon^{-1})$ for all of insertions, deletions, and queries simultaneously remained an open Question.

Details

SODA Conference 2023 Conference Paper

Tiny Pointers

  • Michael A. Bender
  • Alex Conway 0001
  • Martín Farach-Colton
  • William Kuszmaul
  • Guido Tagliavini

This paper introduces a new data-structural object that we call the tiny pointer. In many applications, traditional log n -bit pointers can be replaced with o (log n )-bit tiny pointers at the cost of only a constant-factor time overhead and a small probability of failure. We develop a comprehensive theory of tiny pointers, and give optimal constructions for both fixed-size tiny pointers (i. e. , settings in which all of the tiny pointers must be the same size) and variable-size tiny pointers (i. e. , settings in which the average tiny-pointer size must be small, but some tiny pointers can be larger). If a tiny pointer references an element in an array filled to load factor 1 — δ, then the optimal tiny-pointer size is Θ(log log log n + log δ -1 ) bits in the fixed-size case, and Θ(log δ -1 ) expected bits in the variable-size case. Our tiny-pointer constructions also require us to revisit several classic problems having to do with balls and bins; these results may be of independent interest. Using tiny pointers, we revisit five classic data-structure problems. We show that: • A data structure storing n v -bit values for n keys with constant-time modifications/queries can be implemented to take space nv + O ( n log ( r ) n ) bits, for any constant r > 0, as long as the user stores a tiny pointer of expected size O (1) with each key—here, log ( r ) n is the r -th iterated logarithm. • Any binary search tree can be made succinct with constant-factor time overhead, and can even be made to be within O ( n ) bits of optimal if we allow for O (log * n )-time modifications—this holds even for rotation-based trees such as the splay tree and the red-black tree. • Any fixed-capacity key-value dictionary can be made stable (i. e. , items do not move once inserted) with constant-time overhead and 1 + o (1) space overhead. • Any key-value dictionary that requires uniform-size values can be made to support arbitrary-size values with constant-time overhead and with an additional space consumption of log ( r ) n + O (log j ) bits per j -bit value for an arbitrary constant r > 0 of our choice. • Given an external-memory array A of size (1 + ε ) n containing a dynamic set of up to n key-value pairs, it is possible to maintain an internal-memory stash of size O ( n log ε -1 ) bits so that the location of any key-value pair in A can be computed in constant time (and with no IOs). These are all well studied and classic problems, and in each case tiny pointers allow for us to take a natural space-inefficient solution that uses pointers and make it space-efficient for free.

Details

STOC Conference 2022 Conference Paper

On the optimal time/space tradeoff for hash tables

  • Michael A. Bender
  • Martín Farach-Colton
  • John Kuszmaul
  • William Kuszmaul
  • Mingmou Liu

For nearly six decades, the central open question in the study of hash tables has been to determine the optimal achievable tradeoff curve between time and space. State-of-the-art hash tables offer the following guarantee: If keys/values are Θ(log n ) bits each, then it is possible to achieve constant-time insertions/deletions/queries while wasting only O (loglog n ) bits of space per key when compared to the information-theoretic optimum—this bound has been proven to be optimal for a number of closely related problems (e.g., stable hashing, dynamic retrieval, and dynamically-resized filters). This paper shows that O (loglog n ) wasted bits per key is not the end of the line for hashing. In fact, for any k ∈ [log * n ], it is possible to achieve O ( k )-time insertions/deletions, O (1)-time queries, and the k -th iterated logarithm O (log ( k ) n ) wasted bits per key (all with high probability in n ), while also supporting dynamic resizing as the size of the table changes. We further show that this tradeoff curve is the best achievable by any of a large class of hash tables, including any hash table designed using the current framework for making constant-time hash tables succinct. Our result holds for arbitrarily large keys/values, and in the case where keys/values are very small, we can tighten our bounds to o (1) wasted bits per key. Building on this, we obtain a constant-time dynamic filter that uses n ⌈logє −1 ⌉+ n log e + o ( n ) bits of space for a wide choice of false-positive rates є, resolving a long-standing open problem for the design of dynamic filters.

Details

FOCS Conference 2022 Conference Paper

Online List Labeling: Breaking the log 2 n Barrier

  • Michael A. Bender
  • Alex Conway 0001
  • Martín Farach-Colton
  • Hanna Komlós
  • William Kuszmaul
  • Nicole Wein

The online list-labeling problem is an algorithmic primitive with a large literature of upper bounds, lower bounds, and applications. The goal is to store a dynamically-changing set of n items in an array of m slots, while maintaining the invariant that the items appear in sorted order, and while minimizing the relabeling cost, defined to be the number of items that are moved per insertion/deletion. For the linear regime, where $m = (1+\Theta(1))n$, an upper bound of $O(\log^{2}n)$ on the relabeling cost has been known since 1981. A lower bound of $\Omega(\log^{2}n)$ is known for deterministic algorithms and for so-called smooth algorithms, but the best general lower bound remains $\Omega(\log n)$. The central open question in the field is whether $O(\log^{2}n)$ is optimal for all algorithms. In this paper, we give a randomized data structure that achieves an expected relabeling cost of $O(\log^{3/2}n)$ per operation. More generally, if $m=(1+\varepsilon)n$ for $\varepsilon=O(1)$, the expected relabeling cost becomes $O(\varepsilon^{-1}\log^{3/2}n)$. Our solution is history independent, meaning that the state of the data structure is independent of the order in which items are inserted/deleted. For history-independent data structures, we also prove a matching lower bound: for all $\varepsilon$ between $1/n^{1/3}$ and some sufficiently small positive constant, the optimal expected cost for history-independent list-labeling solutions is $\Theta(\varepsilon^{-1}\log^{3/2}n)$.

Details

FOCS Conference 2021 Conference Paper

Linear Probing Revisited: Tombstones Mark the Demise of Primary Clustering

  • Michael A. Bender
  • Bradley C. Kuszmaul
  • William Kuszmaul

The linear-probing hash table is one of the oldest and most widely used data structures in computer science. However, linear probing famously comes with a major draw-back: as soon as the hash table reaches a high memory utilization, elements within the hash table begin to cluster together, causing insertions to become slow. This phenomenon, now known as primary clustering, was first captured by Donald Knuth in 1963; at a load factor of $1 -1/x$, the expected time per insertion is $\Theta(x^{2})$, rather than the more desirable $\Theta(x)$. We show that there is more to the story than the classic analysis would seem to suggest. It turns out that small design decisions in how deletions are implemented have dramatic effects on the asymptotic performance of insertions. If these design decisions are made correctly, then even a hash table that is continuously at a load factor $1-\Theta(1/x)$ can achieve average insertion time $\tilde{O}(x)$. A key insight is that the tombstones left behind by deletions cause a surprisingly strong “anti-clustering” effect, and that when insertions and deletions are one-for-one, the anti-clustering effects of deletions actually overpower the clustering effects of insertions. We also present a new variant of linear probing, which we call graveyard hashing, that completely eliminates primary clustering on any sequence of operations. If, when an operation is performed, the current load factor is $1 -1/x$ for some $x$, then the expected cost of the operation is $O(x)$. One corollary is that, in the external-memory model with a data block size of $B$, graveyard hashing offers the following remarkable guarantee: at any load factor $1 -1/x$ satisfying $x=o(B)$, graveyard hashing achieves $1 +o(1)$ expected block transfers per operation. Past external-memory hash tables have only been able to offer a $1 +o(1)$ guarantee when the block size $B$ is at least $\Omega(x^{2})$. Our results come with actionable lessons for both theoreticians and practitioners, in particular, that well-designed use of tombstones can completely change the asymptotic landscape of how the linear probing behaves (and if there are no deletions).

Details

SODA Conference 2021 Conference Paper

Randomized Cup Game Algorithms Against Strong Adversaries

  • Michael A. Bender
  • William Kuszmaul

In each step of the cup game on n cups, a filler distributes up to 1 – ∊ water among the cups, and then an emptier removes 1 unit of water from a single cup. The emptier's goal is to minimize the height of the fullest cup, also known as the backlog. The cup emptying game has found extensive applications to processor scheduling, network-switch buffer management, quality of service guarantees, and data-structure deamortization. The greedy emptying algorithm (i. e. , always remove from the fullest cup) is known to achieve backlog O (log n ) and to be the optimal deterministic algorithm. Randomized algorithms can do significantly better, achieving backlog O (log log n ) with high probability, as long as ∊ is not too small. In order to achieve these improvements, the known randomized algorithms require that the filler is an oblivious adversary, unaware of which cups the emptier chooses to empty out of at each step. Such randomized guarantees are known to be impossible against fully adaptive fillers. We show that, even when the filler is just “slightly” non-adaptive, randomized emptying algorithms can still guarantee a backlog of O (log log n ). In particular, we give randomized randomized algorithms against an elevated adaptive filler, which is an adaptive filler that can see the precise fills of every cup containing more than 3 units of water, but not of the cups containing less than 3 units.

Details

SODA Conference 2021 Conference Paper

Tight Bounds for Parallel Paging and Green Paging

  • Kunal Agrawal 0001
  • Michael A. Bender
  • Rathish Das
  • William Kuszmaul
  • Enoch Peserico
  • Michele Scquizzato

In the parallel paging problem, there are p processors that share a cache of size k. The goal is to partition the cache among the processors over time in order to minimize their average completion time. For this long-standing open problem, we give tight upper and lower bounds of Θ(log p ) on the competitive ratio with O (1) resource augmentation. A key idea in both our algorithms and lower bounds is to relate the problem of parallel paging to the seemingly unrelated problem of green paging. In green paging, there is an energy-optimized processor that can temporarily turn off one or more of its cache banks (thereby reducing power consumption), so that the cache size varies between a maximum size k and a minimum size k/p. The goal is to minimize the total energy consumed by the computation, which is proportional to the integral of the cache size over time. We show that any efficient solution to green paging can be converted into an efficient solution to parallel paging, and that any lower bound for green paging can be converted into a lower bound for parallel paging, in both cases in a black-box fashion. We then show that, with O (1) resource augmentation, the optimal competitive ratio for deterministic online green paging is Θ(log p ), which, in turn, implies the same bounds for deterministic online parallel paging.

Details

STOC Conference 2020 Conference Paper

Contention resolution without collision detection

  • Michael A. Bender
  • Tsvi Kopelowitz
  • William Kuszmaul
  • Seth Pettie

This paper focuses on the contention resolution problem on a shared communication channel that does not support collision detection. A shared communication channel is a multiple access channel, which consists of a sequence of synchronized time slots. Players on the channel may attempt to broadcast a packet (message) in any time slot. A player's broadcast succeeds if no other player broadcasts during that slot. If two or more players broadcast in the same time slot, then the broadcasts collide and both broadcasts fail. The lack of collision detection means that a player monitoring the channel cannot differentiate between the case of two or more players broadcasting in the same slot (a collision) and zero players broadcasting. In the contention-resolution problem, players arrive on the channel over time, and each player has one packet to transmit. The goal is to coordinate the players so that each player is able to successfully transmit its packet within reasonable time. However, the players can only communicate via the shared channel by choosing to either broadcast or not. A contention-resolution protocol is measured in terms of its throughput (channel utilization). Previous work on contention resolution that achieved constant throughput assumed that either players could detect collisions, or the players' arrival pattern is generated by a memoryless (non-adversarial) process.

Details

SODA Conference 2019 Conference Paper

Optimal Ball Recycling

  • Michael A. Bender
  • Jake Christensen
  • Alex Conway 0001
  • Martín Farach-Colton
  • Rob Johnson 0001
  • Meng-Tsung Tsai

Balls-and-bins games have been a successful tool for modeling load balancing problems. In this paper, we study a new scenario, which we call the ball-recycling game, defined as follows: Throw m balls into n bins i. i. d. according to a given probability distribution p. Then, at each time step, pick a non-empty bin and recycle its balls: take the balls from the selected bin and re-throw them according to p. This balls-and-bins game closely models memory-access heuristics in databases. The goal is to have a bin-picking method that maximizes the recycling rate, defined to be the expected number of balls recycled per step in the stationary distribution. We study two natural strategies for ball recycling: F ullest B in, which greedily picks the bin with the maximum number of balls, and R andom B all, which picks a ball at random and recycles its bin. We show that for general p, random B all is Θ(1)-optimal, whereas F ullest B in can be pessimal. However, when p = u, the uniform distribution, F ullest B in is optimal to within an additive constant.

Details

FOCS Conference 2018 Conference Paper

Bloom Filters, Adaptivity, and the Dictionary Problem

  • Michael A. Bender
  • Martín Farach-Colton
  • Mayank Goswami 0001
  • Rob Johnson 0001
  • Samuel McCauley
  • Shikha Singh 0002

An approximate membership query data structure (AMQ)-such as a Bloom, quotient, or cuckoo filter-maintains a compact, probabilistic representation of a set S of keys from a universe U. It supports lookups and inserts. Some AMQs also support deletes. A query for x ∈ S returns PRESENT. A query for x ∉ S returns PRESENT with a tunable false-positive probability ε, and otherwise returns ABSENT. AMQs are widely used to speed up dictionaries that are stored remotely (e. g. , on disk or across a network). The AMQ is stored locally (e. g. , in memory). The remote dictionary is only accessed when the AMQ returns PRESENT. Thus, the primary performance metric of an AMQ is how often it returns ABSENT for negative queries. Existing AMQs offer weak guarantees on the number of false positives in a sequence of queries. The false-positive probability ε holds only for a single query. It is easy for an adversary to drive an AMQ's false-positive rate towards 1 by simply repeating false positives. This paper shows what it takes to get strong guarantees on the number of false positives. We say that an AMQ is adaptive if it guarantees a false-positive probability of ε for every query, regardless of answers to previous queries. We establish upper and lower bounds for adaptive AMQs. Our lower bound shows that it is impossible to build a small adaptive AMQ, even when the AMQ is immediately told whenever a query is a false positive. On the other hand, we show that it is possible to maintain an AMQ that uses the same amount of local space as a non-adaptive AMQ (up to lower order terms), performs all queries and updates in constant time, and guarantees that each negative query to the dictionary accesses remote storage with probability ε, independent of the results of past queries. Thus, we show that adaptivity can be achieved effectively for free.

Details

TCS Journal 2018 Journal Article

The range 1 query (R1Q) problem

  • Michael A. Bender
  • Rezaul A. Chowdhury
  • Pramod Ganapathi
  • Samuel McCauley
  • Yuan Tang

We define the range 1 query (R1Q) problem as follows. Given a d-dimensional ( d ≥ 1 ) input bit matrix A (consisting of 0's and 1's), preprocess A so that for any given region R of A, efficiently answer queries asking if R contains a 1 or not. We consider both orthogonal and non-orthogonal shapes for R including rectangles, axis-parallel right-triangles, certain types of polygons, axis-parallel right simplices and spheres. We provide space-efficient deterministic and randomized algorithms with constant query times (in constant dimensions) for solving the problem in the word-RAM model. The space usage in bits is sublinear, linear, or near linear in the size of A, depending on the algorithm.

Details DOI

SODA Conference 2017 Conference Paper

File Maintenance: When in Doubt, Change the Layout!

  • Michael A. Bender
  • Jeremy T. Fineman
  • Seth Gilbert
  • Tsvi Kopelowitz
  • Pablo Montes

This paper gives a new deamortized solution to the sequential-file-maintenance problem. The data structure uses several new tools for solving this historically complicated problem. These tools include an unbalanced ternary-tree layout embedded in the sparse table, one-way rebalancing, and extra structural properties to keep interaction among rebalances to a minimum.

Details

STOC Conference 2016 Conference Paper

Contention resolution with log-logstar channel accesses

  • Michael A. Bender
  • Tsvi Kopelowitz
  • Seth Pettie
  • Maxwell Young

For decades, randomized exponential backoff has provided a critical algorithmic building block in situations where multiple devices seek access to a shared resource. Surprisingly, despite this history, the performance of standard backoff is poor under worst-case scheduling of demands on the resource: (i) subconstant throughput can occur under plausible scenarios, and (ii) each of N devices requires Omega(log N) access attempts before obtaining the resource.

Details

SODA Conference 2016 Conference Paper

How to Scale Exponential Backoff: Constant Throughput, Polylog Access Attempts, and Robustness

  • Michael A. Bender
  • Jeremy T. Fineman
  • Seth Gilbert
  • Maxwell Young

Randomized exponential backoff is a widely deployed technique for coordinating access to a shared resource. A good backoff protocol should, arguably, satisfy three natural properties: (i) it should provide constant throughput, wasting as little time as possible; (ii) it should require few failed access attempts, minimizing the amount of wasted effort; and (iii) it should be robust, continuing to work efficiently even if some of the access attempts fail for spurious reasons. Unfortunately, exponential backoff has some well-known limitations in two of these areas: it provides poor (sub-constant) throughput (in the worst case), and is not robust (to adversarial disruption). The goal of this paper is to “fix” exponential backoff by making it scalable, particularly focusing on the case where processes arrive in an on-line, worst-case fashion. We present a relatively simple backoff protocol, R e -B ackoff, that has, at its heart, a version of exponential backoff. It guarantees expected constant throughput with dynamic process arrivals and requires only an expected polylogarithmic number of access attempts per process. R e -B ackoff is also robust to periods where the shared resource is unavailable for a period of time. If it is unavailable for D time slots, R e -B ackoff provides the following guarantees. When the number of packets is a finite n, the average expected number of access attempts for successfully sending a packet is O (log 2 ( n + D )). In the infinite case, the average expected number of access attempts for successfully sending a packet is O (log 2 ( η + D )) where η is the maximum number of processes that are ever in the system concurrently.

Details

TCS Journal 2015 Journal Article

The minimum backlog problem

  • Michael A. Bender
  • Sándor P. Fekete
  • Alexander Kröller
  • Vincenzo Liberatore
  • Joseph S.B. Mitchell
  • Valentin Polishchuk
  • Jukka Suomela

We study the minimum backlog problem (MBP). This online problem arises, e. g. , in the context of sensor networks. We focus on two main variants of MBP. The discrete MBP is a 2-person game played on a graph G = ( V, E ). The player is initially located at a vertex of the graph. In each time step, the adversary pours a total of one unit of water into cups that are located on the vertices of the graph, arbitrarily distributing the water among the cups. The player then moves from her current vertex to an adjacent vertex and empties the cup at that vertex. The player's objective is to minimize the backlog, i. e. , the maximum amount of water in any cup at any time. The geometric MBP is a continuous-time version of the MBP: the cups are points in the two-dimensional plane, the adversary pours water continuously at a constant rate, and the player moves in the plane with unit speed. Again, the player's objective is to minimize the backlog. We show that the competitive ratio of any algorithm for the MBP has a lower bound of Ω ( D ), where D is the diameter of the graph (for the discrete MBP) or the diameter of the point set (for the geometric MBP). Therefore we focus on determining a strategy for the player that guarantees a uniform upper bound on the absolute value of the backlog. For the absolute value of the backlog there is a trivial lower bound of Ω ( D ), and the deamortization analysis of Dietz and Sleator gives an upper bound of O ( D log ⁡ N ) for N cups. Our main result is a tight upper bound for the geometric MBP: we show that there is a strategy for the player that guarantees a backlog of O ( D ), independently of the number of cups. We also study a localized version of the discrete MBP: the adversary has a location within the graph and must act locally (filling cups) with respect to his position, just as the player acts locally (emptying cups) with respect to her position. We prove that deciding the value of this game is PSPACE-hard.

Details DOI

SODA Conference 2014 Conference Paper

Cache-Adaptive Algorithms

  • Michael A. Bender
  • Roozbeh Ebrahimi
  • Jeremy T. Fineman
  • Golnaz Ghasemiesfeh
  • Rob Johnson 0001
  • Samuel McCauley

We introduce the cache-adaptive model, which generalizes the external-memory model to apply to environments in which the amount of memory available to an algorithm can fluctuate. The cache-adaptive model applies to operating systems, databases, and other systems where the allocation of memory to processes changes over time. We prove that if an optimal cache-oblivious algorithm has a particular recursive structure, then it is also an optimal cache-adaptive algorithm. Cache-oblivious algorithms having this form include Floyd-Warshall all pairs shortest paths, naïve recursive matrix multiplication, matrix transpose, and Gaussian elimination. While the cache-oblivious sorting algorithm Lazy Funnel Sort does not have this recursive structure, we prove that it is nonetheless optimally cache-adaptive. We also establish that if a cache-oblivious algorithm is optimal on “square”” (well-behaved) memory profiles then, given resource augmentation it is optimal on all memory profiles. We give paging algorithms for the case where the cache size changes dynamically. We prove that LRU with 4-memory and 4-speed augmentation is competitive with optimal. Moreover, Belady's algorithm remains optimal even when the cache size changes. Cache-obliviousness is distinct from cache-adaptivity. We exhibit a cache-oblivious algorithm that is not cache-adaptive and a cache-adaptive algorithm for a problem having no optimal cache-oblivious solution. MSC codes cache adaptive cache oblivious external memory memory adaptive paging algorithms

Details

SODA Conference 2014 Conference Paper

Dynamic Task Allocation in Asynchronous Shared Memory

  • Dan Alistarh
  • James Aspnes
  • Michael A. Bender
  • Rati Gelashvili
  • Seth Gilbert

Task allocation is a classic distributed problem in which a set of p potentially faulty processes must cooperate to perform a set of tasks. This paper considers a new dynamic version of the problem, in which tasks are injected adversarially during an asynchronous execution. We give the first asynchronous shared-memory algorithm for dynamic task allocation, and we prove that our solution is optimal within logarithmic factors. The main algorithmic idea is a randomized concurrent data structure called a dynamic to-do tree, which allows processes to pick new tasks to perform at random from the set of available tasks, and to insert tasks at random empty locations in the data structure. Our analysis shows that these properties avoid duplicating work unnecessarily. On the other hand, since the adversary controls the input as well the scheduling, it can induce executions where lots of processes contend for a few available tasks, which is inefficient. However, we prove that every algorithm has the same problem: given an arbitrary input, if OPT is the worst-case complexity of the optimal algorithm on that input, then the expected work complexity of our algorithm on the same input is O ( OPT log 3 m ), where m is an upper bound on the number of tasks that are present in the system at any given time.

Details

FOCS Conference 2012 Conference Paper

How to Allocate Tasks Asynchronously

  • Dan Alistarh
  • Michael A. Bender
  • Seth Gilbert
  • Rachid Guerraoui

Asynchronous task allocation is a fundamental problem in distributed computing in which p asynchronous processes must execute a set of m tasks. Also known as write-all or do-all, this problem been studied extensively, both independently and as a key building block for various distributed algorithms. In this paper, we break new ground on this classic problem: we introduce the To-Do Tree concurrent data structure, which improves on the best known randomized and deterministic upper bounds. In the presence of an adaptive adversary, the randomized To-Do Tree algorithm has O(m+plogplog2m) work complexity. We then show that there exists a deterministic variant of the To-Do Tree algorithm with work complexity O(m+p log5 m log2 max(m, p)). For all values of m and p, our algorithms are within log factors of the O(m + p log p) lower bound for this problem. The key technical ingredient in our results is a new approach for analyzing concurrent executions against a strong adaptive scheduler. This technique allows us to handle the complex dependencies between the processes' coin flips and their scheduling, and to tightly bound the work needed to perform subsets of the tasks.

Details

FOCS Conference 2011 Conference Paper

Mutual Exclusion with O(log^2 Log n) Amortized Work

  • Michael A. Bender
  • Seth Gilbert

This paper presents a new algorithm for mutual exclusion in which each passage through the critical section costs amortized O(log 2 log n) RMRs with high probability. The algorithm operates in a standard asynchronous, local spinning, shared memory model with an oblivious adversary. It guarantees that every process enters the critical section with high probability. The algorithm achieves its efficient performance by exploiting a connection between mutual exclusion and approximate counting.

Details

TCS Journal 2004 Journal Article

The Level Ancestor Problem simplified

  • Michael A. Bender
  • Martı́n Farach-Colton

We present a simple algorithm for the Level Ancestor Problem. A Level Ancestor Query LA(v, d) requests the depth d ancestor of node v. The Level Ancestor Problem is to preprocess a given rooted tree T to support level ancestor queries. While optimal solutions to this problem already exist, our new optimal solution is simple enough to be taught and implemented.

Details DOI

FOCS Conference 2003 Conference Paper

The Cost of Cache-Oblivious Searching

  • Michael A. Bender
  • Gerth Stølting Brodal
  • Rolf Fagerberg
  • Dongdong Ge
  • Simai He
  • Haodong Hu
  • John Iacono
  • Alejandro López-Ortiz

Tight bounds on the cost of cache-oblivious searching are proved. It is shown that no cache-oblivious search structure can guarantee that a search performs fewer than lg e log/sub B/N block transfers between any two levels of the memory hierarchy. This lower bound holds even if all of the block sizes are limited to be powers of 2. A modified version of the van Emde Boas layout is proposed, whose expected block transfers between any two levels of the memory hierarchy arbitrarily close to [lg e + O(lg lg B/ lgB)] logB N + O(1). This factor approaches lg e /spl ap/ 1. 443 as B increases. The expectation is taken over the random placement of the first element of the structure in memory. As searching in the disk access model (DAM) can be performed in log/sub B/N + 1 block transfers, this result shows a separation between the 2-level DAM and cache-oblivious memory-hierarchy models. By extending the DAM model to k levels, multilevel memory hierarchies can be modeled. It is shown that as k grows, the search costs of the optimal k-level DAM search structure and of the optimal cache-oblivious search structure rapidly converge. This demonstrates that for a multilevel memory hierarchy, a simple cache-oblivious structure almost replicates the performance of an optimal parameterized k-level DAM structure.

Details

I&C Journal 2003 Journal Article

The Lazy Bureaucrat scheduling problem

  • Esther M. Arkin
  • Michael A. Bender
  • Joseph S.B. Mitchell
  • Steven S. Skiena

We introduce a new class of scheduling problems in which the optimization is performed by the worker (single “machine”) who performs the tasks. A typical worker’s objective is to minimize the amount of work he does (he is “lazy”), or more generally, to schedule as inefficiently (in some sense) as possible. The worker is subject to the constraint that he must be busy when there is work that he can do; we make this notion precise both in the preemptive and nonpreemptive settings. The resulting class of “perverse” scheduling problems, which we denote “Lazy Bureaucrat Problems, ” gives rise to a rich set of new questions that explore the distinction between maximization and minimization in computing optimal schedules.

Details DOI

STOC Conference 2002 Conference Paper

Cache-oblivious priority queue and graph algorithm applications

  • Lars Arge
  • Michael A. Bender
  • Erik D. Demaine
  • Bryan Holland-Minkley
  • J. Ian Munro

(MATH) In this paper we develop an optimal cache-oblivious priority queue data structure, supporting insertion, deletion, and deletemin operations in O ( 1 \over B log M/B N \over B ) amortized memory transfers, where M and B are the memory and block transfer sizes of any two consecutive levels of a multilevel memory hierarchy. In a cache-oblivious data structure, M and B are not used in the description of the structure. The bounds match the bounds of several previously developed external-memory (cache-aware) priority queue data structures, which all rely crucially on knowledge about M and B . Priority queues are a critical component in many of the best known external- memory graph algorithms, and using our cache-oblivious priority queue we develop several cache- oblivious graph algorithms.

Details

I&C Journal 2002 Journal Article

The Power of a Pebble: Exploring and Mapping Directed Graphs

  • Michael A. Bender
  • Antonio Fernández
  • Dana Ron
  • Amit Sahai
  • Salil Vadhan

Exploring and mapping an unknown environment is a fundamental problem that is studied in a variety of contexts. Many results have focused on finding efficient solutions to restricted versions of the problem. In this paper, we consider a model that makes very limited assumptions about the environment and solve the mapping problem in this general setting. We model the environment by an unknown directed graph G, and consider the problem of a robot exploring and mapping G. The edges emanating from each vertex are numbered from ‘1’ to ‘d’, but we do not assume that the vertices of G are labeled. Since the robot has no way of distinguishing between vertices, it has no hope of succeeding unless it is given some means of distinguishing between vertices. For this reason we provide the robot with a “pebble”—a device that it can place on a vertex and use to identify the vertex later. In this paper we show: (1) If the robot knows an upper bound on the number of vertices then it can learn the graph efficiently with only one pebble. (2) If the robot does not know an upper bound on the number of vertices n, then Θ(log log n) pebbles are both necessary and sufficient. In both cases our algorithms are deterministic.

Details DOI

FOCS Conference 2000 Conference Paper

Cache-Oblivious B-Trees

  • Michael A. Bender
  • Erik D. Demaine
  • Martín Farach-Colton

We present dynamic search-tree data structures that perform well in the setting of a hierarchical memory (including various levels of cache, disk, etc.), but do not depend on the number of memory levels, the block sizes and number of blocks at each level, or the relative speeds of memory access. In particular between any pair of levels in the memory hierarchy, where transfers between the levels are done in blocks of size B, our data structures match the optimal search bound of /spl Theta/(log/sub B/ N) memory transfers. This bound is also achieved by the classic B-tree data structure, but only when the block size B is known, which in practice requires careful tuning on each machine platform. One of our data structures supports insertions and deletions in /spl Theta/(log/sub B/ N) amortized memory transfers, which matches the B-tree's worst-case bounds. We augment this structure to support scans optimally in /spl Theta/(N/B) memory transfers. In this second data structure insertions and deletions require /spl Theta/(log/sub B/ N+log/sup 2/N/B) amortized memory transfers. Thus, we match the performance of the B-tree for B=/spl Omega/(log N log log N).

Details

FOCS Conference 1996 Conference Paper

Fault Tolerant Data Structures

  • Yonatan Aumann
  • Michael A. Bender

The authors consider the tolerance of data structures to memory faults. They observe that many pointer-based data structures (e. g. linked lists, trees, etc.) are highly nonresilient to faults. A single fault in a linked list or tree may result in the loss of the entire set of data. They present a formal framework for studying the fault tolerance properties of pointer-based data structures, and provide fault tolerant versions of the stack, the linked list, and the dictionary tree.

Details

FOCS Conference 1996 Conference Paper

New Algorithms for the Disk Scheduling Problem

  • Matthew Andrews
  • Michael A. Bender
  • Lisa Zhang 0001

Processor speed and memory capacity are increasing several times faster than disk speed. This disparity suggests that disk I/O performance will become an important bottleneck. Methods are needed for using disks more efficiently. Past analysis of disk scheduling algorithms has largely been experimental and little attempt has been made to develop algorithms with provable performance guarantees. We consider the following disk scheduling problem. Given a set of requests on a computer disk and a convex reachability function which determines how fast the disk head travels between tracks, our goal is to schedule the disk head so that it services all the requests in the shortest time possible. We present a 3/2-approximation algorithm (with a constant additive term). For the special case in which the reachability function is linear we present an optimal polynomial-time solution. The disk scheduling problem is related to the special case of the asymmetric Traveling Salesman Problem with the triangle inequality (ATSP-/spl Delta/) in which all distances are either 0 or some constant /spl alpha/. We show how to find the optimal tour in polynomial time and describe how this gives another approximation algorithm for the disk scheduling problem. Finally we consider the on-line version of the problem in which uniformly-distributed requests arrive over time. We present an algorithm (related to the above ATSP-/spl Delta/) that appears to give higher throughput than previously existing head scheduling algorithms.

Details

TCS Journal 1995 Journal Article

Parallel interval order recognition and construction of interval representations

  • Michael A. Bender
  • Michel Gastaldo
  • Michel Morvan

Parallel algorithms for recognizing and representing interval orders are proposed for different models of parallel random access machines (PRAM). The algorithms accept as input a transitively-closed directed graph with N nodes and M edges. They run in time O(log N) with O(N + M) processors and O(N + M) space and in constant time with O(N 2) processors and O(N 2) space depending on the data structure and the PRAM model used. Optimal probabilistic algorithms for PRAM are also presented as well as algorithms for distributed-memory machines.

Details DOI

FOCS Conference 1994 Conference Paper

The Power of Team Exploration: Two Robots Can Learn Unlabeled Directed Graphs

  • Michael A. Bender
  • Donna K. Slonim

We show that two cooperating robots can learn exactly any strongly-connected directed graph with n indistinguishable nodes in expected time polynomial in n. We introduce a new type of homing sequence for two robots which helps the robots recognize certain previously-seen nodes. We then present an algorithm in which the robots learn the graph and the homing sequence simultaneously by wandering actively through the graph. Unlike most previous learning results using homing sequences, our algorithm does not require a teacher to provide counterexamples. Furthermore, the algorithm can use efficiently any additional information available that distinguishes nodes. We also present an algorithm in which the robots learn by taking random walks. The rate at which a random walk converges to the stationary distribution is characterized by the conductance of the graph. Our random-walk algorithm learns in expected time polynomial in n and in the inverse of the conductance and is more efficient than the homing-sequence algorithm for high-conductance graphs. >

Details
v2026.09.13