In this talk I will introduce some traditional problems in distributed systems and describe simple algorithms to solve them. The focus will mostly be on asynchronous messaging passing algorithms, however we will look at some asynchronous shared memory and synchronous message passing algorithms as well. The first half of the talk will introduce problems that arise due to the asynchronous nature of distributed systems. We will look at 3 major topics in this section; (1) time and event ordering, (2) mutual exclusion, (3) global consistent snapshots. The second half we will look at additional problems that arise due to failure of components. Once again we will look at 3 major topics (1) consensus, (2) leader election, (3) fault tolerance via replication.
12