Computer Science 612
Course Description
The course provides a theoretical introduction to the area of distributed computing. We will study loosely-coupled, concurrent systems that are prone to failures of different types.
We wil study the most significant problems in distributed computing including leader election on a network, the consensus problem, resource allocation problems like mutual exclusion, communication protocols, shared memory consistency issues and causality and time.
We will study formal models for distributed computing, and study the relationships among them. We will look at message passing and shared memory models of communication, models that vary in their degree of synchrony, as well as models which exhibit varying degrees of fault-tolerance. In particular, we will study a variety of models ranging from completely synchronous to completely asynchronous.
We will prove correctness of algorithms and analyze their complexity. We will prove upper and lower bounds, and impossibility results for various problems in various models, while emphasizing the important techniques for algorithm design and lower bounds proofs.
Special topics covered this semester will include security issues in distributed systems, including blockchains.
As a pre-requisite for the course, you will be expected to be familiar with the basic concepts behind the design and analysis of sequential algorithms. This familiarity can be obtained from Com S 511 and, to a lesser extent, from Com S 311. Also, you should be comfortable with reasoning through and writing involved, mathematical proofs. Lower bound proofs and impossibility proofs in distributed computing often have the same style as the proofs done in a Theory of Computation course like Com S 531.
A background in distributed systems, fault-tolerance, operating systems, or networking would be helpful in appreciating possible applications of the results we will cover, but is not essential.