Update the connection backoff document with jitter.

This adds both jitter and explicit values for the "proposed" algorithm
that implementations should use.

1 files changed, 18 insertions, 2 deletions

diff --git a/doc/connection-backoff.md b/doc/connection-backoff.md
index 47b71f927b..e348a2b9e3 100644
--- a/doc/connection-backoff.md
+++ b/doc/connection-backoff.md
@@ -14,7 +14,7 @@ We have several parameters:
 ## Proposed Backoff Algorithm
 
 Exponentially back off the start time of connection attempts up to a limit of
-MAX_BACKOFF.
+MAX_BACKOFF, with jitter.
 
 ```
 ConnectWithBackoff()
@@ -24,9 +24,25 @@ ConnectWithBackoff()
          != SUCCESS)
     SleepUntil(current_deadline)
     current_backoff = Min(current_backoff * MULTIPLIER, MAX_BACKOFF)
-    current_deadline = now() + current_backoff
+    current_deadline = now() + current_backoff +
+      UniformRandom(-JITTER * backoff, JITTER * backoff)
+
 ```
 
+With specific parameters of
+INITIAL_BACKOFF = 20 seconds
+MULTIPLIER = 1.6
+MAX_BACKOFF = 120 seconds
+JITTER = 0.2
+
+Implementations with pressing concerns (such as minimizing the number of wakeups
+on a mobile phone) may wish to use a different algorithm, and in particular
+different jitter logic.
+
+Alternate implementations must ensure that connection backoffs started at the
+same time disperse, and must not attempt connections substantially more often
+than the above algorithm.
+
 ## Historical Algorithm in Stubby
 
 Exponentially increase up to a limit of MAX_BACKOFF the intervals between