Contention Resolution without Collision Detection

Explore contention resolution without collision detection in this ACM conference talk. Delve into the setup of a shared channel, feedback mechanisms for players, and the classic problem of contention resolution. Examine the state-of-the-art approaches assuming collision detection and using collision detection. Investigate exponential backoff for contention and discover a new algorithm that addresses the problem. Learn about simulating two channels, their roles, and the basic algorithm structure. Understand how to handle batch players, fresh arrivals, and the challenge of stragglers. Gain insights into an innovative algorithm for contention resolution that overcomes traditional limitations.

Contention Resolution without Collision Detection
THE SETUP: A SHARED CHANNEL
FEEDBACK GIVEN TO THE PLAYERS
A CLASSIC PROBLEM: CONTENTION RESOLUTION
CONTENTION RESOLUTION FROM THE PERSPECTIVE OF EACH PLAYER
STATE OF THE ART: ASSUME COLLISION DETECTION
STATE OF THE ART: USE COLLISION DETECTION
EXP BACKOFF PROBLEM 2: CONTENTION
THE REST OF TALK: OUR ALGORITHM
BACKOFF IS GOOD AT: GETTING A SINGLE SUCCESS The Setup: On players arrive into system over time.
BACKOFF IS GOOD AT: SIMPLIFIED CONTENTION RESOLUTION Batch Players
SIMULATING TWO CHANNELS
THE ROLES OF THE CHANNELS
BASIC ALGORITHM STRUCTURE
BATCH PLAYERS ON THE ACTIVE CHANNEL
FRESH ARRIVALS: IDENTIFYING THE CHANNELS
WAITING ON THE SILENT CHANNEL
CHANGING THE CHANNEL ROLES
IMPORTANT PROBLEM: STRAGGLERS Problem: Strangles on the active channel take no long
PUTTING THE PIECES TOGETHER Theorem: There is an algorithm for contention resolution that