Editing Exponential backoff (section)

==Exponential backoff algorithm==
An exponential backoff algorithm is a form of [[closed-loop control system]] that reduces the rate of a controlled process in response to adverse events. For example, if a smartphone app fails to connect to its server, it might try again 1 second later, then if it fails again, 2 seconds later, then 4, etc. Each time the pause is multiplied by a fixed amount (in this case 2). In this case, the adverse event is failing to connect to the server. Other examples of adverse events include [[collision (telecommunications)|collisions of network traffic]], an error response from a service, or an explicit request to reduce the rate (i.e. ''back off'').

The rate reduction can be modelled as an [[exponential function]]:

:<math>t = b^c</math>

or

:<math>f = \frac{1}{b^c}</math>

Here, {{math|''t''}} is the time delay applied between actions, {{math|''b''}} is the multiplicative factor or ''base'', {{math|''c''}} is the number of adverse events observed, and {{math|''f''}} is the frequency (or rate) of the process (i.e. number of actions per unit of time). The value of {{math|''c''}} is incremented each time an adverse event is observed, leading to an exponential rise in delay and, therefore, an inversely proportionate rate. An exponential backoff algorithm where {{math|1= ''b'' = 2}} is referred to as a ''binary'' exponential backoff algorithm.

When the rate has been reduced in response to an adverse event, it usually does not remain at that reduced level forever. If no adverse events are observed for some period of time, often referred to as the ''recovery time'' or ''cooling-off period'', the rate may be increased again. The time period that must elapse before attempting to increase the rate again may, itself, be determined by an exponential backoff algorithm. Typically, recovery of the rate occurs more slowly than reduction of the rate due to backoff and often requires careful tuning to avoid [[oscillation]] of the rate.<ref>{{harvnb|Tanenbaum|Wetherall|2010|chapter=5.3|page=395}}</ref> The exact recovery behaviour is implementation-specific and may be informed by any number of environmental factors.

The mechanism by which rate reduction is practically achieved in a system may be more complex than a simple time delay. In some cases, the value {{math|''t''}} may refer to an [[upper bound]] to the time delay, rather than a specific time delay value. The name ''exponential backoff'' refers to the [[exponential growth]] characteristic of the backoff, rather than an exact numeric relationship between adverse event counts and delay times.