Distributed systems allow a collection of many computers to act as one system. Doing so requires consensus between the different computers within the system. The design needs to address fundamental underlying challenges: communication, coordination, synchronization, and uncertainty.
A rich literature in computer science addresses this problem from both theoretical and practical perspectives. These algorithms allow simultaneous editing of a Google Doc by different users, streaming of Netflix movies from multiple datacenters, and the reliability of the Bitcoin ledger of payments.
The goal of this class is to provide students with an introduction and an overview of the theory behind consensus protocols, and provide connections between this theoretical literature and game theory. The class will cover different modeling approaches, impossibility results that uncover the importance of the modeling assumptions, and practical and simple algorithms.
We will cover classic results in the literature, as well as more recent developments related to decentralized systems and cryptocurrencies (for example, the proof-of-work protocol that underlies Bitcoin). Recent developments raise questions about the feasibility of consensus among independent selfish entities. Answering these questions requires a combination of tools from both economics and computer science. Students in the class will acquire the tools to explore this novel field.
The class is open to all students. It is aimed at advanced students who are exploring research topics, and are interested in theoretical modeling. Background in computer science or economics is not necessary, but students are expected to have sufficient mathematical maturity.