FDD 3008 Distributed Algorithms

News	Schedule	Prerequisites
Content	Course material	Professor
Objectives	Examination and grading	Code of honour

Please refer to the undergraduate course page for up to date information

Content

Introductory postgraduate level course in computer science on the theory, algorithms, and techniques of parallel and distributed computing systems. Parallel and distributed algorithms are fundamental to many aspects of modern computing and communications technology, including processor architectures (multicore, manycore), programming languages and operating systems, databases, and networks. The course covers the principles of parallel and distributed algorithms, emphasizing the fundamental issues underlying the design and analysis of both parallel and distributed systems, including synchronization, communication, coordination, agreement, fault-tolerance, locality, symmetry breaking, self-organization. The course addresses both shared memory and message passing concurrent and distributed systems.

Objectives

The course is intended to give students a thorough introduction to the topic of distributed algorithms with emphasis on principles and theory. The main audience is graduate and postgraduate students in computer science, and engineering students preferably with some background in logic and discrete structures and, generally, an interest in algorithmic problems. Upon completion of the course, the student will have developed a working understanding of the problem domain and its main mathematical tools and techniques and be able to use these techniques in their own research, and in the critical examination of published work in the area.

Schedule

Lectures:

Lecture 1	24 Oct	10-12	D35	Introduction, mutual exclusion, locks
Lecture 2	27 Oct	13-15	B23	Concurrent objects, linearization, sequential consistency
Lecture 3	31 Oct	10-12	D42	Registers, snapshots
Lecture 4	2 Nov	13-15	E34	Consensus, I
Lecture 5	8 Nov	13-15	E31	Consensus, II
Lecture 6	10 Nov	15-17	Q17	Fault tolerance, I
Lecture 7	14 Nov	13-15	D35	Fault tolerance, II
Lecture 8	16 Nov	15-17	D42	Leader election
Presentations	18 Nov	10-12	V33
Lecture 9	21 Nov	10-12	D35	Spanning trees, aggregation
Presentations	23 Nov	15-17	V23
Lecture 10	25 Nov	10-12	E36	P2P systems, DHT's
Lecture 11	28 Nov	10-12	D35	Vertex colouring, perhaps
Presentations	1 Dec	10-12	D34
Lecture 12	5 Dec	10-12	D35	TBD
Presentations	6 Dec	10-12	Q31

The subjects indicated above are tentative and subject to change as we move along

Seminars

Each student will be required to present a research paper at a special sessions, to be announced.

Course Material

Main textbook is

• Maurice Herlihy, Nir Shavit: The art of multiprocessor programming, Morgan Kaufmann 2008.

Other useful references - among many:

• Hagit Attiya, Jennifer Welch: Distributed Computing: Fundamentals, Simulations and Advanced Topics, McGraw-Hill Publishing, 2004
• David Peleg: Distributed Computing: A Locality-Sensitive Approach. Society for Industrial and Applied Mathematics (SIAM), 2000
• George Coulouris, Jean Dollimore, Tim Kindberg, Gordon Blair: Distributed Systems, Concepts and Design. Pearson 2012
• Christian Cachin, Rachid Guerraoui, Luis Rodrigues: Reliable and secure Distributed Programming, 2n ed., Springer 2011

Additional material will be made available here as the course moves on.

Examination and Grading

The course is examined by hand-ins, a paper presentation, and a written report. The details will be announced at the first lecture.

Prerequisites

The course does not have formal prerequisites. Basic familiarity with algorithms, including theory, basic mathematical discourse in cs, and programming will be very useful.

Companion Course

This course is a companion to the masters level course DD2451 Parallel and Distributed Computing.

Professor

Mads Dam, mfd@kth.se, 790 6229, room 4416. No specific office hours. Preferred contact by email.

Code of Honour

It goes without saying that the Nada code of honour applies to this course as well.