In today's lecture, we will discuss how to solve consensus when no failures can occur in the network. Before we begin, let's recap on an important thing you learned in the last module regarding consensus. Previously, you learned that consensus can be defined as a problem along three properties; agreement, validity, and termination. Agreement means that no two correct processes can decide differently in order to prevent disagreement. Validity means that any decided value is a value proposed. In other words, all the processes must decide on one of the values that were proposed at the beginning. Finally, termination means that every correct process eventually decides. Remember, if we want to solve consensus, we must solve each of these properties. Let's see a simple consensus algorithm. In this scenario, we assume that none of the processes in our system can fail. So here, we have n equals 4 processes that are all correct. Let's say that initially, each of these processes have a different proposal represented as an integer 0, 1, 2, and 3. Now, what do we need for our algorithm to solve consensus? We need to satisfy the requirements for agreement, termination, and validity. A consensus algorithm without failure can be considered a simple solution in which each node sends or broadcast its proposal to all other nodes. Once each process receives all the proposals from all the nodes, they decide the smallest among all these values. Let's look at this solution differently through pseudocode. This pseudocode indicates the algorithm that each process Pi runs. The process starts with a set of values denoted capital V that initially contains the only non proposal, say x. The algorithm executes by sending the values of V that have not been sent yet to all the processes. By then receiving the values that are sent by all the processes, it stores all these values in the set of non values, V, before simply deciding the minimum value in this set of values V. To get a better understanding of how this consensus algorithm executes, let's observe a particular execution using the four correct processes we mentioned earlier. Initially, each process only knows about its own proposal value. After, everyone sends its value to everyone else, every node learns about all proposals, 0, 1, 2, 3. Finally, as indicated on the right hand side, all processes decide the minimum zero among these values. It is easy to see that these algorithms solve the consensus problem. Why? The decided value can only be one of the proposed values indicating that validity is ensured. Termination is satisfied because all nodes eventually decide. Finally, agreement is satisfied because they decide the same value. But what are the costs of this algorithm? The costs are threefold. First is the number of messages that need to be exchanged. Second is the total number of bits that need to be exchanged. Here, let's consider b as the number of bits needed to encode an integer in a message. Last, is the time it takes to execute this algorithm. The time it takes to execute the algorithm heavily depends on the time it takes to deliver a message. Because the time it takes to deliver a message is often significantly larger than the time it takes to compute things locally. To this end, let's express the time as the number of consecutive message delays. Let's examine these three costs further. There are three types of complexity we should analyze in order to understand consensus without failure. First, let's look at the message complexity. All processes broadcast to all other processes, leading to n times n minus 1 messages, which means that the message complexity is of the order of n square messages. Next is the communication complexity. Remember, each message contains a single integer that can be coded with b bits. As each message contains a single integer that can be coded with b bits, this algorithm exchanges b times n times n minus 1 bits. The big complexity becomes of the order of n square. Last is time complexity. All processes broadcast in parallel. It only takes all of one message delays to exchange all messages. You now understand how to solve consensus when all processes are correct, and that's such a solution can be costly. In the next lesson, we will explore solution to the consensus problem when failures can occur.
