Abstract

With the increasing prevalence of multi-core computers, asynchronous computation offers one of our best hopes for significant performance gains. Unfortunately the behaviour of asynchronous algorithms are much harder than that of their synchronous counterparts for humans to reason about. However several theorems exist allow proofs of properties of asynchronous computations to be derived from proofs of the corresponding synchronous behaviour. This talk will describe a mathematical formalisation for such asynchronous problems, as well as several theorems guaranteeing their convergence to a unique solution even in the presence of latency, message loss, reordering and duplication.