Exponential backoff

Exponential backoff is an algorithm that uses feedback to multiplicatively decrease the rate of some process, in order to gradually find an acceptable rate. It is a form of closed-loop control: each adverse event, such as a failed connection, a collision of network traffic, packet loss or an error response, multiplies the delay by a fixed factor, so a client that retries after 1 second may next wait 2 seconds, then 4. When the factor is 2 it is called binary exponential backoff. In rate limiting it lets a service slow its clients dynamically without telling them anything in advance, and the SIP protocol over UDP uses a non-random version that starts at 500 milliseconds and doubles up to 4 seconds. For collision avoidance on a shared channel, a deterministic delay would make every sender retry together, so the delay is randomized and the algorithm only sets the range of possible slot counts; this lowers the chance of another collision but raises average latency. It is used in CSMA/CD and CSMA/CA networks and is the usual way Ethernet schedules retransmissions after collisions. Its history runs through Norman Abramson's 1970 ALOHA paper, Larry Roberts's slotted ALOHA and the stability work of Simon Lam and Leonard Kleinrock.