Network and Distributed Algorithms

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 be repeated for credit one time. Grade Mode: Normal, Audit College Restrictions: School of Comp & Cyber Science Course Level Restrictions: Graduate Semester Schedule Type (Primary): Lecture Schedule Type (Additional): Asynchronous Instruction Click here for the Schedule of Classes.