Now that we know that the popular solution to the Byzantine consensus problem is to use a leader, we need to understand if this is viable for blockchain. In this lecture, we will discuss why the leader becomes a bottleneck at large-scale. It is important to note first that the process that plays the role of the leader typically changes over time. It is therefore, hard for a client or wallet application to know which process is the leader and to send requests to this leader. It is easier for a client to know the set of processes that run the blockchain service, and to send a request to some of the geographically closest of these processes. Consider that we want to decide a block of B bits, but let's focus on its set of transactions rather than its other data like hash, nouns, and so on. Consensus requires this information to be exchanged among all correct processes. So let's compare the time it takes to exchange this with two types of algorithms. One, leader-based, the other leaderless. In a leader-based algorithm, the set of transactions is proposed by the leader. Conversely, in a leaderless algorithm, the set of transactions is proposed by all the participating processes. Let's talk about each of these algorithms. On the one hand, a leader based algorithm would typically have the leaders send the set of transactions to others, so that the correct processes can decide what a process proposed. Considering this example that the leader is the process with index one and that there are three other processes or followers. Each process, i, has a download capacity, di, and an upload capacity, ui. The time it takes to exchange B bits among all processes is the maximum time it takes for two tasks that execute concurrently. First, the leader must upload N copies of B bits, which takes nB divided by ui time. Second, the follower with the lowest download capacity must download one copy, which takes B divided by the minimum among all di, for any i between one and n. Note that the overall time is therefore of the order of n times B. On the other hand, in the leaderless algorithm, the set of transactions to be decided can come from all processes. In this case, the processes propose B over n bits. The time it takes to exchange these sets of transaction is the maximum of the time for the slowest process to upload B over n bits, and the time for the slowest process to download B bits. The result is therefore of the order of B. If we consider that the leader has 10 times higher upload bandwidth than all other processes, and that every process downloads two times faster than they upload, then the time to exchange a set of transaction in a leader-based or leaderless algorithm is the same in small networks. Nonetheless, it is significantly slower for the leader-based algorithm than for the leaderless algorithm at large scale. This slowdown starts with 21 nodes and increases with the network size. To conclude, the leader is a bottleneck that prevents the information to be exchanged rapidly between nodes. It is therefore, better for scalability for all processes to propose transactions than having a leader trying to impose its set of transactions. This is in contradiction with the classic Byzantine consensus problem definition we saw earlier that requires the decided value to be one of the proposed values. There exists variance of the Byzantine consensus problem that are interesting, like interactive consistency and vector consensus. However, these variants required processes to decide a minimum number of proposals coming from correct processes, which is not suitable for blockchains, as we will discuss later in this module.
