English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

In contention resolution, multiple processors are trying to coordinate tosend discrete messages through a shared channel with sharply limitedcommunication. If two processors inadvertently send at the same time, themessages collide and are not transmitted successfully. An important case isacknowledgement-based contention resolution, in which processors cannot listento the channel at all; all they know is whether or not their own messages havegot through. This situation arises frequently in both networking and cloudcomputing. The most common acknowledgement-based protocols in practice arebackoff protocols - variants of binary exponential backoff are used in bothEthernet and TCP/IP, and both Google Drive and AWS instruct their users toimplement it to handle busy periods.  In queueing models, where each processor has a queue of messages, stablebackoff protocols are already known (H{\aa}stad et al., SICOMP 1996). Inqueue-free models, where each processor has a single message but processorsarrive randomly, it is a long-standing conjecture of Aldous (IEEE Trans. Inf.Theory 1987) that no stable backoff protocols exist for any positive arrivalrate of processors. Despite exciting recent results for full-sensing protocolswhich assume far greater listening capabilities of the processors (see e.g.Bender et al. STOC 2020 or Chen et al. PODC 2021), this foundational questionremains open; here instability is only known in general when the arrival rateof processors is at least 0.42 (Goldberg et al. SICOMP 2004). We prove Aldous'conjecture for all backoff protocols outside of a tightly-constrained specialcase using a new domination technique to get around the main difficulty, whichis the strong dependencies between messages.

Instability of backoff protocols with arbitrary arrival rates