Author name cluster

Maxwell Young

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.

6 papers

2 author rows

TCS Journal 2026 Journal Article

Softening the impact of collisions in contention resolution

Umesh Biswas
Trisha Chakraborty
Maxwell Young
Qian M. Zhou

Contention resolution addresses the problem of coordinating access to a shared communication channel. Time is discretized into synchronized slots, and a packet can be sent in any slot. If no packet is sent, then the slot is empty; if a single packet is sent, then it is successful; and when multiple packets are sent at the same time, a collision occurs, resulting in the failure of the corresponding transmissions. In each slot, every packet receives ternary channel feedback indicating whether the current slot is empty, successful, or a collision. Much of the prior work on contention resolution has focused on optimizing the makespan, which is the number of slots required for all packets to succeed. However, in many modern systems, collisions are also costly in terms of the time they incur. In this paper, we design and analyze a randomized algorithm, Collision-Aversion Backoff (CAB), that addresses both the makespan and the total number of slots in which a collision occurs (i. e. , total collision cost). We consider the static case where an unknown n ≥ 2 packets are initially present in the system, and each collision has a known cost C, where 1 ≤ C ≤ n κ for any constant κ ≥ 0. CAB guarantees that all packets succeed with expected makespan and an expected total collision cost of O ( n C poly ( log n ) ). We also give a complementary lower bound for the class of fair algorithms: where, in each slot, every packet sends with the same probability on a per-slot basis.

Details DOI

TCS Journal 2024 Journal Article

Defending hash tables from algorithmic complexity attacks with resource burning

Trisha Chakraborty
Jared Saia
Maxwell Young

We consider the problem of defending a hash table against a Byzantine attacker that is trying to degrade the performance of query, insertion and deletion operations. Our defense makes use of resource burning (RB)—the verifiable expenditure of network resources—where the issuer of a request incurs some RB cost. Our algorithm, Depth Charge, charges RB costs for operations based on the depth of the appropriate object in the list that the object hashes to in the table. By appropriately setting the RB costs, our algorithm mitigates the impact of an attacker on the hash table's performance. In particular, in the presence of a significant attack, our algorithm incurs a cost which is asymptotically less that the attacker's cost.

Details DOI

TCS Journal 2022 Journal Article

Singletons for simpletons revisiting windowed backoff with Chernoff bounds

Qian M. Zhou
Alice Calvert
Maxwell Young

Backoff algorithms are used in many distributed systems where multiple devices contend for a shared resource. For the classic balls-into-bins problem, the number of singletons—those bins with a single ball—is important to the analysis of several backoff algorithms; however, existing analyses employ advanced probabilistic tools. Here, we show that standard Chernoff bounds can be used instead, and the simplicity of this approach is illustrated by re-analyzing some well-known backoff algorithms.

Details DOI

I&C Journal 2018 Journal Article

Interactive communication with unknown noise rate

Varsha Dani
Thomas P. Hayes
Mahnush Movahedi
Jared Saia
Maxwell Young

Alice and Bob want to run a protocol over a noisy channel, where some bits are flipped adversarially. Several results show how to make an L-bit noise-free communication protocol robust over such a channel. In a recent breakthrough, Haeupler described an algorithm sending a number of bits that is conjecturally near optimal for this model. However, his algorithm critically requires prior knowledge of the number of bits that will be flipped by the adversary. We describe an algorithm requiring no such knowledge, under the additional assumption that the channel connecting Alice and Bob is private. If an adversary flips T bits, our algorithm sends L + O ( L ( T + 1 ) log ⁡ L + T ) bits in expectation and succeeds with high probability in L. It does so without any a priori knowledge of T. Assuming a lower bound conjectured by Haeupler, our result is optimal up to logarithmic factors.

Details DOI

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