Algorithms to Live By: The Computer Science of Human Decisions
by Brian Christian and Tom Griffiths · 4 Apr 2016 · 523pp · 143,139 words
crucial to the system functioning correctly. The second question, of course, once we do recognize a breakdown, is what exactly we should do about it. Exponential Backoff: The Algorithm of Forgiveness The world’s most difficult word to translate has been identified as “ilunga,” from the Tshiluba language spoken in south-eastern
…
accommodate potentially any number of competing signals. Since the maximum delay length (2, 4, 8, 16…) forms an exponential progression, it’s become known as Exponential Backoff. Exponential Backoff was a huge part of the successful functioning of the ALOHAnet beginning in 1971, and in the 1980s it was baked into TCP, becoming a
…
a network of unknown topology and with an unknown, unknowable and constantly changing population of competing conversations, only one scheme has any hope of working—exponential backoff.” But it is the algorithm’s other uses that suggest something both more prescriptive and more profound. Beyond just collision avoidance
…
, Exponential Backoff has become the default way of handling almost all cases of networking failure or unreliability. For instance, when your computer is trying to reach a
…
website that appears to be down, it uses Exponential Backoff—trying again one second later, again a few seconds after that, and so forth. This is good for everyone: it prevents a host server that
…
much effort trying to get blood from a stone. But interestingly, it also does not force (or allow) your machine to ever completely give up. Exponential Backoff is also a critical part of networking security, when successive password failures in logging into an account are punished by an exponentially increasing lockout period
…
arbitrary and severe, but continuing to persist in perpetual rescheduling seemed naïve, liable to lead to an endless amount of disappointment and wasted time. Solution: Exponential Backoff on the invitation rate. Try to reschedule in a week, then two, then four, then eight. The rate of “retransmission” goes toward zero—yet you
…
to call again several weeks later and ask to be forgiven and taken back in. It seemed like a paradox, a cruel and impossible choice. Exponential Backoff isn’t a magic panacea in cases like this, but it does offer a possible way forward. Requiring an exponentially increasing period of sobriety, for
…
way the justice system itself handles community supervision for drug offenders. That revolution is being spearheaded by a pilot program called HOPE, which uses the Exponential Backoff principles of the ALOHAnet—and which, in a striking coincidence, began at the birthplace of the ALOHAnet itself: Honolulu. Shortly after being sworn in to
…
, Agner Krarup Erlang distribution error bars error tradeoff space ethics Evernote eviction policies evolution constraints and expected value Explicit Congestion Notification (ECN) explore/exploit tradeoff Exponential Backoff exponential time (O(2n)) Facebook factorial time (O(n!)) fads false positives FBI FCC spectrum auctions FDA feedback fencing filing Finkel, Larry Firefox fire truck
…
waiting, cost-benefit of “Walking” (Thoreau) Walpole, Horace war Ware, Jim Warhol, Andy Washington Star wealth web design websites. See also Internet advertising and “Akamaized” Exponential Backoff and malicious wedding seating plan Wedgwood, Emma weighted strategies Welch, Ivo Whitney, Hassler Whittaker, Steve Whittle, Peter Wikipedia Wilkes, Maurice Williams, Robin Win-Stay, Lose
Site Reliability Engineering: How Google Runs Production Systems
by Betsy Beyer, Chris Jones, Jennifer Petoff and Niall Richard Murphy · 15 Apr 2016 · 719pp · 181,090 words
particular, testing the system can highlight problems, and graceful degradation can reduce the effect of the retries on the backend. Always use randomized exponential backoff when scheduling retries. See also “Exponential Backoff and Jitter” in the AWS Architecture Blog [Bro15]. If retries aren’t randomly distributed over the retry window, a small perturbation (e
…
Understand how large clients use your service. For example, you want to know if clients: Can queue work while the service is down Use randomized exponential backoff on errors Are vulnerable to external triggers that can create large amounts of load (e.g., an externally triggered software update might clear an offline
…
purpose, an RPC that times out is either not retried (for example, in the case of the aforementioned pictures), or is retried with a randomized exponential backoff. Despite these safeguards, the tasks fail one by one and are then restarted by Borg, which drives the number of working tasks down even more
…
dropping a fraction of traffic (including retries!) upstream of the system once total load exceeds total capacity. Every client that makes an RPC must implement exponential backoff (with jitter) for retries, to dampen error amplification. Mobile clients are especially troublesome because there may be millions of them and updating their code to
…
/ August 2001. [Bre12] E. Brewer, “CAP Twelve Years Later: How the “Rules” Have Changed”, in Computer, vol. 45, no. 2, February 2012. [Bro15] M. Brooker, “Exponential Backoff and Jitter”, on AWS Architecture Blog, March 2015. [Bro95] F. P. Brooks Jr., “No Silver Bullet—Essence and Accidents of Software Engineering”, in The Mythical
UNIX® Network Programming, Volume 1: The Sockets Networking API, 3rd Edition
by W. Richard Stevens, Bill Fenner, Andrew M. Rudoff · 8 Jun 2013
send the initial INIT message before considering the peer endpoint unreachable. • sinit_max_init_timeo represents the maximum RTO value for the INIT timer. During exponential backoff of the initial timer, this value replaces RTO.max as the ceiling for retransmissions. This value is expressed in milliseconds. Note that when setting these
…
simplicity, we use floating-point calculations in our code that follows. Another point made in [Jacobson 1988] is that when the retransmission timer expires, an exponential backoff must be used for the next RTO. For example, if our first RTO is 2 seconds and the reply is not received in this time
…
expires, sigsetjmp returns 1. 604 Advanced UDP Sockets Chapter 22 Handle timeout 49–55 When a timeout occurs, rtt_timeout calculates the next RTO (the exponential backoff) and returns −1 if we should give up, or 0 if we should retransmit. If we give up, we set errno to ETIMEDOUT and return
…
); /* time to give up for this packet */ return (0); lib/rtt.c Figure 22.14 rtt_timeout function: applies exponential backoff. 86 lib/rtt.c The current RTO is doubled: This is the exponential backoff. 608 Advanced UDP Sockets 87–89 Chapter 22 If we have reached the maximum number of retransmissions, −1 is
…
, sig_alrm); 18 19 20 21 22 23 24 if (sigsetjmp(jmpbuf, 1)) { if (nsent >= 3) err_quit("no response"); printf("timeout\n"); timeout *= 2; /* exponential backoff: 3, 6, 12 */ } canjump = 1; /* siglongjmp is now OK */ 25 26 send_dns_query(); nsent++; 27 28 29 30 alarm(timeout); ui = udp_read(); canjump
…
a reply. If we have sent three requests, we terminate. Otherwise, we print a message and multiply the timeout value by 2. This is an exponential backoff, which we described in Section 22.5. The first timeout will be for 3 seconds, then 6, and then 12. Section 29.7 Examining the
…
– 946 exit function, 9, 39, 114, 128, 137, 237, 401 – 402, 409, 427, 614, 679 – 680, 910, 935 expedited data, see out-of-band data exponential backoff, 598, 802 extended unique identifier, see EUI extension headers, IPv6, 719 external data representation, see XDR F_CONNECTING constant, 457 – 459 F_DONE constant, 459
Docker in Action
by Jeff Nickoloff and Stephen Kuenzli · 10 Dec 2019 · 629pp · 109,663 words
container was configured to always restart, and Docker always immediately restarted it, the system would do nothing but restart that container. Instead, Docker uses an exponential backoff strategy for timing restart attempts. A backoff strategy determines the amount of time that should pass between successive restart attempts. An exponential back-off strategy
…
1 second, then on the second attempt it would wait 2 seconds, 4 seconds on the third attempt, 8 on the fourth, and so on. Exponential backoff strategies with low initial wait times are a common service-restoration technique. You can see Docker employ this strategy yourself by building a container that
Building Secure and Reliable Systems: Best Practices for Designing, Implementing, and Maintaining Systems
by Heather Adkins, Betsy Beyer, Paul Blankinship, Ana Oprea, Piotr Lewandowski and Adam Stubblefield · 29 Mar 2020 · 1,380pp · 190,710 words
outage difficult.9 Client software should be carefully designed to avoid tight retry loops. If a server fails, the client may retry, but should implement exponential backoff—for example, doubling the wait period each time an attempt fails. This approach limits the number of requests to the server, but on its own
…
clients, causing repeated bursts of high traffic. To avoid synchronous retries, each client should wait for a random duration, called jitter. At Google, we implement exponential backoff with jitter in most of our client software. What can you do if you don’t control the client? This is a common concern for
…
, but implement retries carefully in order to avoid a cascading failure (akin to falling dominoes).1 The most common solution is to retry with an exponential backoff.2 A good framework should provide support for such logic, rather than requiring the developer to implement the logic for every RPC call. A framework
…
request (before stage) and then logs all the failed requests with their status (after stage); WithAttemptCount is a framework-provided RPC call option that implements exponential backoff type logInterceptor struct { logger *LoggingBackendStub } func (*logInterceptor) Before(ctx context.Context, req *Request) (context.Context, error) { // callInfo was populated by the framework. callInfo, err := FromContext
…
, Handling emergencies directly removing dependency on accurate notions of time, Removing dependency on accurate notions of time revoking credentials at scale, Revoking credentials at scale exponential backoff, Client Retry Behavior, Example: Framework for RPC Backends external researchers, External Researchers-External Researchers F Facetime privacy bug, Trading Good OpSec for the Greater Good
Principles of Protocol Design
by Robin Sharp · 13 Feb 2008
load increases. Doubling the average retransmission delay for each failed attempt is a simple way of doing this. The technical term for this is Binary Exponential Backoff (BEB); or, if the doubling process terminates after a certain maximum number of attempts, as in the case of the ISO/IEEE CSMA/CD protocol
…
value is doubled after each unsuccessful retransmission. As in the case of the CSMA/CD protocol described by Protocol 11, this mechanism, known as Binary Exponential Backoff ensures stability in the system. After a successful retransmission, the normal way of evaluating the round trip time – and thus the timer value – is recontinued
…
transfer phase: Unacknowledged data transfer. Disconnection phase: None. Other features: Statistical time-division multiplexing with distributed control. Collision resolution by random wait with truncated binary exponential backoff. Coding: Start of DPDU marked by delimiter field. CRC-32 block checksum. Ad hoc binary coding of all fields in DPDU. Addressing: 16-bit or
…
availability 64 B backward learning 222 BAN logic 175 base64 encoding 255 BASN.1 248, 295 behaviour 7 observable 3 Bellman-Ford routing 223 binary exponential backoff (BEB) 109, 234 binding 307, 310 B-ISDN 68 bit stuffing 244 block oriented service 56, 72 blocking commit algorithm 132 Border Gateway Protocol (BGP
ZeroMQ
by Pieter Hintjens · 12 Mar 2013 · 1,025pp · 150,187 words
.h" #define HEARTBEAT_LIVENESS 3 // 3-5 is reasonable #define HEARTBEAT_INTERVAL 1000 // msec #define INTERVAL_INIT 1000 // Initial reconnect #define INTERVAL_MAX 32000 // After exponential backoff // Paranoid Pirate Protocol constants #define PPP_READY "\001" // Signals worker is ready #define PPP_HEARTBEAT "\002" // Signals worker heartbeat // Helper function that returns a new
…
simulation. The worker uses a reconnect strategy similar to the one we designed for the Lazy Pirate client, with two major differences: it does an exponential backoff, and it retries indefinitely (whereas the client retries a few times before reporting a failure). You can try the client, queue, and workers by using
…
worker: #define HEARTBEAT_LIVENESS 3 // 3-5 is reasonable #define HEARTBEAT_INTERVAL 1000 // msec #define INTERVAL_INIT 1000 // Initial reconnect #define INTERVAL_MAX 32000 // After exponential backoff ... // If liveness hits zero, queue is considered disconnected size_t liveness = HEARTBEAT_LIVENESS; size_t interval = INTERVAL_INIT; // Send out heartbeats at regular intervals uint64
…
the worker application gets stuck, heartbeats will stop and the broker will stop sending requests to the worker. The worker API doesn’t do an exponential backoff; it’s not worth the extra complexity. The APIs don’t do any error reporting. If something isn’t as expected, they raise an assertion
Hadoop: The Definitive Guide
by Tom White · 29 May 2009 · 933pp · 205,691 words
one map output for a reducer before declaring it as failed. The reducer may repeatedly reattempt a transfer within this time if it fails (using exponential backoff). io.sort.factor int 10 The maximum number of streams to merge at once when sorting files. This property is also used in the map
…
retry the operation in a loop until ZooKeeper is available. This is just one strategy for retry handling—there are many others, such as using exponential backoff where the period between retries is multiplied by a constant each time. The org.apache.hadoop.io.retry package in Hadoop Core is a set
Designing Data-Intensive Applications: The Big Ideas Behind Reliable, Scalable, and Maintainable Systems
by Martin Kleppmann · 16 Mar 2017 · 1,237pp · 227,370 words
to overload, retrying the transaction will make the problem worse, not better. To avoid such feedback cycles, you can limit the number of retries, use exponential backoff, and handle overload-related errors differently from other errors (if possible). It is only worth retrying after transient errors (for example due to deadlock, isolation
Designing Data-Intensive Applications: The Big Ideas Behind Reliable, Scalable, and Maintainable Systems
by Martin Kleppmann · 17 Apr 2017
to overload, retrying the transaction will make the problem worse, not better. To avoid such feedback cycles, you can limit the number of retries, use exponential backoff, and handle overload-related errors differently from other errors (if possible). • It is only worth retrying after transient errors (for example due to deadlock, iso