Importance of timeouts

We all know that timeouts are important everyday, but they are equally important in computer science. Especially in the field of distributed computing. The buzz word in the industry nowadays is Microservices, which are inherently distributed systems which take care one single thing and accomplish the task which they are responsible for in the most efficient way as much as possible.

*What’s a sequential process?

A sequential algorithm is a formal description of the behaviour of a sequential state machine. The text of the algorithm states the transitions that have to be sequentially executed. When this text is transformed into a sequence of instructions in a programming language, it becomes a program. The concept of process is introduced especially to highlight the difference between an algorithm as a text and its execution on a processor. So on a very high level, we can think of a process being a dynamic entity generated by the execution of an algorithm on a processor(any computing device). At any point in time it is characterized by its state(which comprises, among other things, the current value of its program counter). A sequential program is defined by a single control flow, i.e, its behaviour is managed by a single program counter, which means it executes a single step at a time.

What exactly is a distributed system

Communication Medium

Processes in a distributed system communicate by sending and receiving messages through channels(internet for example). A channel can be either reliable(neither message loss, creation, modification, nor duplicationFeels like heaven doesn’t it :P), or unreliable(Welcome to the reality). The channel can be either synchronous or asynchronous.

• Synchronous: There will be an upper bound on message transfer delays.
• Asynchronous: There’s no bound, i.e, a message sent today can be delivered any time greater than today.

In addition to the above properties, a channel can also satisfy ordering of messages which are sent, i.e, let’s assume that Pa sends messages Ma, Mb, Mc to Pb, we can say that the channel provides FIFO guarantees if Pb receives the messages from Pa in the following order Ma, Mb, Mc.

Let’s get to the subject

Now that you know some basics about distributed systems, let’s see why timeouts are important, by considering an abstract example:

Problem statement

The problem here concerns an irrevocable decision-making by two processes. Let us consider two hilltops T1 and T2 separated by a valley V. There are two armies A and B. The army A is composed of two divisions A1 and A2, each with a general, the general-in-chief being located in division A1. Moreover, A1 is camping on T1, while A2 is camping on T2. Army B is in between, camping in the valley V. The only way A1 and A2 can communicate is by sending messengers who need to traverse the valley V. But messengers can be captured by army B, and never arrive. We can also safely assume that not all messengers sent by A1 and A2 can be captured.

Let’s assume that the generals of army A previously agreed on two possible battle plans bp1 and bp2, but, accordingly to his analysis of the situation, it is up to the general-in-chief to decide which plan must be adopted. To this end, the general-in-chief must communicate his decision to the general of A2 so that they both adopt the same battle plan(and win).

The end goal here is designing a distributed algorithm(a sequence of message exchanges initiated by the general-in-chief in A1), at the end of which

• A2 knows the battle plan selected by A1
• both A1 and A2 know that they no longer have to send/receive messages

System model

Let p1 and p2 be the two processes representing A1 and A2 respectively, connected by a bi-directional asynchronous channel controlled by the army B. The processes are assumed to never fail. While no message can be modified(corrupted), the channel is asynchronous and unreliable in the sense that messages can be lost(a message loss represents a messenger captured by army B). It is nevertheless assumed that not all messages sent by p1 to p2 can be lost(otherwise, there is a case where the processes could not communicate, making the problem impossible to solve).

As the general-in-chief of army A is in A1, process p1 activates the sequence of message exchanges by sending the message DECIDE(bp) to p2, where bp is the number to choose the battle plan.

For i ∈ {1, 2}, let donei be a local variable of pi initialized to no(for corresponding process, no decision has been made). Hence, representing a global state by the pair {done1, done2}, the initial global state is the pair {no, no}. At the end of its execution, the algorithm must stop in the global state {yes, yes}. When donei = yes, process pi knows

• that each process knows the selected battle plan
• there is no need for messages to be exchanged, namely each process terminates its local algorithm

This brings us to the following properties

• Validity: A final global state cannot contain both yes and no
• Liveness: If p1 activates the algorithm, it eventually and permanently enters the local state done1 = yes

validity property states which are the correct outputs of the algorithm: in no case p1 and p2 are allowed to disagree. Liveness property states that, if p1 starts the algorithm, it must eventually progress. Algorithm structure

Practical instance of the problem

Let us consider two micro services which are communicating through an unreliable fair channel, to decide upon the executor of a critical section, let’s assume that the initial state was {no, no} and the final state is {yes, yes} denoting that they have decided the true owner of the critical section.

Solving the problem - Attempt 1

Starting with p1 let us to try to design an algorithm for p1. As messages(but not all) sent by p1 to p2 can be lost, a simple idea is to require p1 to repeatedly send a message denoted by DECIDE(bp) to p2 until it has received an acknowledgement(bp is the - dynamically defined p1 - number of the selected battle plan):

done 1 ← no;
bp ← selected battle plan ∈ {1, 2};
repeat send DECIDE (bp) to p 2 until ACK ( DECIDE ) received from p 2 end repeat;
done 1 ← yes.

Continuing with p2 while in the state done2 = no, p2 receives the message DECIDE(bp), it sends back p1 the acknowledgement message ACK(DECIDE), but this acknowledgement message can be lost. Hence p2 must resend ACK(DECIDE) until it knows a copy of it has been received by p1. Consequently, the local algorithm of p1 must be enriched with a statement sending an acknowledgement message back to p2 that we denote ACK2(DECIDE). We then obtain the following algorithm for p2

done 2 ← no;
wait(message DECIDE (bp) from p 1 );
repeat send ACK ( DECIDE ) to p 1 until ACK 2 ( DECIDE ) received from p 1 end repeat;
done 2 ← yes.

Returning to p1, As p1 is required to send the message ACK2(DECIDE) to p2, and this message must be received by p2, p1 needs to resend it until it knows that a copy of it has been received by p2. As we have seen, the only way for p1 to know if p2 received ACK2(DECIDE) is to receive an acknowledgement message ACK3(DECIDE) from p2. This results in the following algorithm for p1

done 1 ← no;
bp ← selected battle plan number ∈ {1, 2};
repeat send DECIDE (bp) to p 2 until ACK ( DECIDE ) received from p 2 end repeat;
repeat send ACK 2 ( DECIDE ) to p 2 until ACK 3 ( DECIDE ) received from p 2 end repeat;
done 1 ← yes.

So on forever, (I thought recursion in a single process was hard, this is recursion among two different processes 😭). This clearly demonstrates that the plain acknowledgement approach doesn’t work.

Attempt 2

In order to prevent the sending of infinite sequence of different acknowledgement messages, let us consider the same algorithm as before for p1, namely p1 sends DECIDE(bp) until it knows p2 has received it. When this occurs, p1 knows that p2 knows the number of the decided battle plan, and p1 terminates it local algorithm:

done 1 ← no;
bp ← selected battle plan ∈ {1, 2};
repeat send DECIDE (bp) to p 2 until ACK ( DECIDE ) received from p 2 end repeat;
done 1 ← yes.

Let’s modify the algorithm of p2 according to the previous modification of p1

done 2 ← no;
wait(message DECIDE (bp) from p 1 );
repeat send ACK ( DECIDE ) to p 1 each time DECIDE (bp) received from p 1 end repeat;
done 2 ← yes.

When it receives a copy of the message DECIDE(bp), p2 knows that “Both p1 and p2 know the number of the battle plan”, but it cannot be allowed to proceed to the local state done2 = yes. This is because, as p1 needs to know that “both p1 and p2 know the number of the battle plan”, p2 needs to send an acknowledgement ACK(DECIDE) each time it receives a copy of the message DECIDE(bp). As not all the messages are lost, this ensures that p1 will know that “both p1 and p2 know the battle plan”, despite message losses. Even if p1 sends a finite number of copies of DECIDE(bp), and none of them are lost, the “repeat” statement inside p2 cannot be bounded. This is because p2 can never know how many copies of message DECIDE(bp), it will receive. Due to the fact that not all messages are lost, it knows the number is finite, but not the exact value. Hence, this tentative version does not ensure that both processes terminate their algorithm.

Is there another approach that can successfully solve the problem

Turns out that there is none indeed, hence the concept of timeout is introduced. The modified and an approximation algorithm would now be

• p1 sends a message DECIDE(bp) to p2 and waits for the message ACK(DECIDE)
• This wait is bounded by a timeout, beyond which p1 retries the SEND(DECIDE(bp))operation and goes into the waiting state.
• Since we know that not all messages are lost, the approximation would be that one of the SEND(DECIDE(bp)) -> RECEIVE(ACK(DECIDE)) succeeds
• But we since we cannot keep retrying indefinitely at the same frequency, a retry, exponential-backoff threshold is introduced, beyond retry threshold p1 doesn’t execute SEND(DECIDE(bp)) immediately, but instead waits for the exponential-backoff timer to run out and try again.