Office of the Registrar
Campus Address
Hanover, NH
Phone: (603) 646-xxxx
Fax: (603) 646-xxxx
Email: reg@Dartmouth.EDU

Organization, Regulations, and Courses 2023-24

COSC 49.04 Concurrent Algorithms

We consider problems where multiple processes have to coordinate their activities to accomplish a task. For an example, suppose that there are many sensing agents on an aircraft and each agent, based on its reading of the environment, has a recommendation on whether the aircraft should keep straight, turn left, or turn right. Since different agents can have different recommendations, we would want a protocol by which they can arrive at an "agreement" on whether the plane should go left, right, or straight. How hard is it to design such a protocol? It turns out that if you want the protocol to be fault-tolerant, i.e., the protocol works correctly even if one of the agents stops communicating, it is impossible to design a correct protocol (under certain reasonable assumptions about the system).

In the course, we will look at several fascinating coordination problems and solve them for several models of distributed computing: shared-memory versus message passing, synchronous versus asynchronous, fault-free versus fault-tolerant. We design algorithms, and prove lower bounds or even impossibility results.

There will be weekly homework and a final exam.

Prerequisite: COSC 31 (Undergraduate Algorithms) or equivalent, and an interest in algorithms/theory.


COSC 31 (Undergraduate Algorithms) or equivalent, and an interest in algorithms/theory.

Degree Requirement Attributes


The Timetable of Class Meetings contains the most up-to-date information about a course. It includes not only the meeting time and instructor, but also its official distributive and/or world culture designation. This information supersedes any information you may see elsewhere, to include what may appear in this ORC/Catalog or on a department/program website. Note that course attributes may change term to term therefore those in effect are those (only) during the term in which you enroll in the course.