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.
Prerequisite
COSC 31 (Undergraduate Algorithms) or equivalent, and an interest in algorithms/theory.