Most distributed systems require coordination between all components involved. With the steady growth of such systems, the probability of failures increases, which necessitates fault-tolerant agreement protocols. The most common practical agreement protocol, for such scenarios, is leader-based atomic broadcast. In this work, we propose AllConcur, a distributed system that provides agreement through a leaderless concurrent atomic broadcast algorithm, thus, not suffering from the bottleneck of a central coordinator. In AllConcur, all components exchange messages concurrently through a logical overlay network that employs early termination to minimize the agreement latency. Our implementation of AllConcur supports standard sockets-based TCP as well as high-performance InfiniBand Verbs communications. AllConcur can handle up to 135 million requests per second and achieves 17x higher throughput than today's standard leader-based protocols, such as Libpaxos. Therefore, AllConcur not only offers significant improvements over existing solutions, but enables novel hitherto unattainable system designs in a variety of fields.
Bitcoin @cite_28 offers an alternative solution to the (Byzantine fault-tolerant) atomic broadcast problem: It uses to order the transactions on a distributed ledger. In a nutshell, a server must solve a cryptographic puzzle in order to add a block of transactions to the ledger. Yet, Bitcoin does not guarantee @cite_34 ---multiple servers solving the puzzle may lead to a fork (conflict), resulting in branches. Forks are eventually solved by adding new blocks. Eventually one branch outpaces the others, thereby becoming the ledger all servers agree upon. To avoid frequent forks, Bitcoin controls the expected puzzle solution time to 10 minutes and currently limits the block size to 1MB, resulting in limited performance, i.e., around seven transactions per second. To increase performance, Bitcoin-NG @cite_55 uses proof-of-work to elect a leader that can add blocks until a new leader is elected. Yet, conflicts are still possible and consensus finality is not ensured.
@cite_28 @cite_55 @cite_34
1897250020 2964262836 2486460265
Cryptocurrencies, based on and led by Bitcoin, have shown promise as infrastructure for pseudonymous online payments, cheap remittance, trustless digital asset exchange, and smart contracts. However, Bitcoinderived blockchain protocols have inherent scalability limits that trade off between throughput and latency, which withhold the realization of this potential. This paper presents Bitcoin-NG (Next Generation), a new blockchain protocol designed to scale. Bitcoin-NG is a Byzantine fault tolerant blockchain protocol that is robust to extreme churn and shares the same trust model as Bitcoin. In addition to Bitcoin-NG, we introduce several novel metrics of interest in quantifying the security and efficiency of Bitcoin-like blockchain protocols. We implement Bitcoin-NG and perform large-scale experiments at 15 the size of the operational Bitcoin system, using unchanged clients of both protocols. These experiments demonstrate that Bitcoin-NG scales optimally, with bandwidth limited only by the capacity of the individual nodes and latency limited only by the propagation time of the network. Bitcoin cryptocurrency demonstrated the utility of global consensus across thousands of nodes, changing the world of digital transactions forever. In the early days of Bitcoin, the performance of its probabilistic proof-of-work (PoW) based consensus fabric, also known as blockchain, was not a major issue. Bitcoin became a success story, despite its consensus latencies on the order of an hour and the theoretical peak throughput of only up to 7 transactions per second.