A Blockchain is a type of distributed ledger system that consists of a large number of nodes. A block is a container in which transactions are included, and the transactions can be recorded in chronological order by chaining blocks. To work properly, it is essential that the nodes in the Blockchain system have the same image of the chained-blocks. Blockchain systems use various types of consensus algorithms to achieve the same states among the nodes, and the fundamental elements in these algorithms are proof of work and the main chain selection policy, particularly in permissionless Blockchain systems. However, consensus algorithms for permissioned Blockchain systems can be completely different from those of permissionless blockchain systems. In this paper, we overview the basic working mechanism of consensus algorithms, and briefly introduce a few that are currently being applied.
돈 탭스콧, 알렉스탭스콧, "블록 체인혁명," 서울: 을유문화사, 2017.
World Economic Forum(WEF), "Deep Shift: Technology Tipping Points and Societal Impact," SurveyReport, 2015. 9.
Grand View Research, "Blockchain Technology Market," 2017.
Y. Sompolinsky and A. Zohar, "Secure High-Rate Transaction Processing in Bitcoin," In International Conference on Financial Cryptography and Data Security, Berlin, Heidelberg: Springer, 2015.
M. Castro and B. Liskov, "Practical Byzantine Fault Tolerance," Proc. Symp. Oper. Syst. Des. Inplementation,, New Orleans, LA, USA, Feb. 1999, pp. 1-14.
S. Nakamoto, "Bitcoin: A Peer-to-Peer Electronic Cash System," Oct. 2008, Accessed 2017. http://nakamotoinstitute.org/static/docs/bitcoin.pdf
BitFury Group, "Proof of Stake Versus Proof of Work White Paper," 2015. 9.
S. King and S. Nadal, "PPCoin: Peer-to-Peer Crypto-Currency with Proof-of-Stake," Self-Published Paper, 2012. 8.
I. Eyal, A.E. Gencer, E.G. Sirer, and R. van Renesse, "Bitcoin-NG: A Scalable Blockchain Protocol," Proc. Usenix Conf. Netw. Syst. Des. Implementation, Santa Clara, CA, USA, Mar. 2016, pp. 45-59.
L. Lamport, "The Part-Time Parliament," ACM Trans. Comput. Syst., vol. 16, no. 2, May 1998, pp. 133-169.
L. Lamport, "Paxos Made Simple," ACM SIGACT News, vol. 32, no. 4, Dec. 2001, pp. 18-25.
D. Ongaro and J.K. Ousterhout, "In Search of an Understandable Consensus Algorithm," USENIX Annu. Technical Conf., Philadelphia, PA, USA, June 2014, pp. 305-319.
M. Burrows, "The Chubby Lock Service for Loosely-Coupled Distributed Systems," In Symp. Operating Syst. Des. Implementation, Seattle, WA, USA, Nov. 2006, pp. 335-350.
J.C. Corbett et al., "Spanner: Google's Globally-Distributed Database," In Proc. OSDI'12, USENIX Sympos. Oper Syst. Des. Implementation, Hollywood, CA, USA, Oct. 2012, pp. 251-264.
M. Isard, "Autopilot: Automatic Data Center Management," Oper. Syst. Rev., vol. 41, no. 2, Apr. 2007, pp. 60-67.
B. Calder et al., "Windows Azure Storage: a Highly Available Cloud Storage Service with Strong Consistency," Proc. ACM Symp. Oper. Syst. Principles, Cascais, Portugal, Oct. 2011, pp. 143-157.
B.M. Oki and B.H. Liskov, "Viewstamped Replication: A New Primary Copy Method to Support Highly-Available Distributed Systems," Proc. Annu. ACM Symp. Principles Distributed Comput., Toronto, Canada, Aug. 15-17, 1988, pp. 8-17.
F. Junqueira, B. Reed, and M. Serafini, "Zab: High Performance Broadcast for Primary-Backup Systems," In Proc. USENEX Annu. Techn. Conf., Hong Kong, China, June 27-30, 2010, pp. 245-256.
L. Lamport, R. Shostak, and M. Pease, "The Byzantine Generals Problem," ACM Trans. Programming Languages Syst., vol. 4, no. 3, July 1982, pp. 382-401.
Proof of Elapsed Time of Hyperledger Sawtooth, Accessed 2017. https://sawtooth.hyperledger.org/docs/core/releases/latest/introduction.html#proof-of-elapsedtime-poet
L. Luu, V. narayanan, C. Zheng, K. Baweja, S. Gilbert, and P. Saxena, "A Secure Sharding Protocol for Open Blockchains," In Proc. ACM SIGSAC Conf. Comput. Commun. Security, Vienna, Austria, Oct. 2016, pp. 17-30.