Thursday, October 15, Volen 101, 2:00-3.00 pm
As we enter the 21st century, computers are being used more and more as coordination devices, making standard (Turing) notions of computability and complexity insufficient for evaluating their behaviour in our mostly asynchronous world. This talk introduces the use of topological models and methods, formerly used to analyze computability, as tools for the quantification and classification of asynchronous complexity.
We present the first asynchronous complexity theorem, applied to decision tasks in the IIS memory model of Borowsky and Gafni. We do so by introducing a novel form of topological tool called the non-uniform chromatic subdivision. To show the power of our theorem, we use it to derive two new results. The first closes the gap between known upper and lower bounds on the time to acheive $N$ process approximate agreement. The second is the first algorithm that trades time-complexity/number-of-names for the renaming problem.
More than the new bounds themselves, we beleive the importance of our asynchronous complexity theorem is that the algorithms and lower bounds it allows us to derive are intuitive and simple, with topological proofs that require no mention of concurrency at all.
This is joint work with Gunnar Hoest of MIT.
Host: Liuba Shrira