Thursday, February 26, Volen 101, 2:00-3:00 pm. (Refreshments at 2:00pm)
This talk is an introduction to the problem of "wait free consensus". Because a slow machine may be extremely slow, we consider algorithms which solve consensus in a distributed system in which each process is guaranteed to finish in a bounded number of steps, regardless of the behaviour of other processes in the system. Consensus is the problem of getting several machines to agree on a common value. The immense differences in speed come from several sources: The most obvious (but smallest) is the speed differences of the processors themselves, but page faults (a disk access takes about a million instruction times, so one doesn't want to wait for another processor's page faults), crashes, or even machines off the network and in someone's pocket cause much larger waits. With the above definitions, we can state the problem as follows: Each of several processes reads an input value, runs an algorithm for a specified number of steps, and writes its output. We require that all the processes which write an output write the same output, and that that output be one of the input values. It has long been known (Fischer, Lynch, and Patterson, 1985) that with only message passing any single failure would make it impossible to reach consensus. Work since then has proceeded in two directions: First, weakening the definition of consensus, and secondly, investigating what can be done with somewhat stronger primitives. I will discuss the second direction by describing the relative power of different atomic operations in a shared memory system. I will describe a hierarchy of operations, each stronger than the last, and introduce the question of whether this hierarchy is robust. This talk is designed for a general audience, and assumes only a general computer science background.
Host: Liuba Shrira