Mar 14, 2012
The opposite of exponential backoff

Every few days I'm on IM with some coworker from a different building. The conversation goes something like this:

Them: Lunch?
(6 minutes)
Me: Sounds good! Meet downstairs?
(1 minute)
Me: Now?
(2 minutes)
Them: Yes!
(1 minute)
Them: You there?
(3 minutes)
Me: Oops, sorry. Heading down now.
Now I never know whether to wait for a response, or to run down because I'm already late. But today I finally figured out the answer:
Me: New rule. Head down when both of us say 'ready' within 1 minute of each
other.
That's it. No more ambiguity. It's kind of a silly example, but the general idea feels deep, complementary somehow to exponential backoff. Exponential backoff is the ideal game-theoretic strategy for competitive situations where two people need to contend for a common resource, like trying to call someone back after a dropped call and getting a busy signal. Both try to diverge away from a network-defined window of conflict by waiting longer and longer. Here both parties are trying to converge into an agreed window of agreement. Defining the size of the window by diktat should be handy anytime two parties (people, computers, ..) need to cooperate synchronously atop an asynchronous channel.

I'm sure there's a paper on this idea, perhaps something like that one by Lamport pdf on Buridan's ass. If you have a pointer I'd love to hear about it.

Comments gratefully appreciated. Please send them to me by any method of your choice and I'll include them here.

archive
projects
writings
videos
subscribe
Mastodon
RSS (?)
twtxt (?)
Station (?)