Network and Distributed Systems

Catalog description

This is an introduction to algorithmic aspects of distributed computing and computation in networks. The topics considered are those that arise in systems comprised of loosely coupled, heterogeneous and failure-prone processing units, arranged in a connected structure that allows information exchange. The range of applications starts at wide-area networks, goes through clusters of workstations connected by local-area networks, to multi-processor shared-memory machines. The relevant properties of solutions reflect the communication mechanisms (message passing, shared memory), the algorithmic constraints (deterministic, randomized, quantum), the timing models (synchronous, asynchronous), and the types of failures (crashes, omissions, Byzantine). The algorithmic goals to achieve include: sharing resources in a fair manner, providing fault-tolerance and privacy, and maintaining global consistency of computations. The specific problems include: symmetry breaking, consensus, resource allocation and scheduling, renaming, and synchronization. Strong understanding of undergraduate-level distributed systems, discrete mathematics (especially graph theory) and algorithms are expected. Lecture Hours: 3 Repeatability: May not be repeated for credit. Grade Mode: Normal, Audit Schedule Type (Primary): Lecture Click here for the Schedule of Classes.