The Instability of all Backoff Protocols
In this paper we prove Aldous's conjecture from 1987 that there is no backoff protocol that is stable for any positive arrival rate. The setting is a communication channel for coordinating requests for a shared resource. Each user who wants to access the resource makes a request by sending a message to the channel. The users don't have any way to communicate with each other, except by sending messages to the channel. The operation of the channel proceeds in discrete time steps. If exactly one message is sent to the channel during a time step then this message succeeds (and leaves the…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2602.21315
curl -X POST /api/v1/records/arxiv/2602.21315/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2602.21315/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'