New Challenges and Algebraic Topology

Maurice Herlihy

Maurice Herlihy discusses his view on the challenges distributed computing faces in the future, describes some of his work on programming abstractions and how he uses algebraic topology as a tool to reason about distributed protocols.

Guest: Maurice Herlihy
Host: Zvi Lotker and Yvonne-Anne Pignolet

The Impact of Memory Models on Software Reliability in Multiprocessors

Alexander Jaffe, Thomas Moscibroda, Laura Effinger-Dean, Luis Ceze, and Karin Strauss

Abstract: The memory consistency model is a fundamental system property characterizing a multiprocessor. The relative merits of strict versus relaxed memory models have been widely debated in terms of their impact on performance, hardware complexity and programmability. This paper adds a new dimension to this discussion: the impact of memory models on software reliability. By allowing some instructions to reorder, weak memory models may expand the window between critical memory operations. This can increase the chance of an undesirable thread-interleaving, thus allowing an otherwise-unlikely concurrency bug to manifest. To explore this phenomenon, we define and study a probabilistic model of shared-memory parallel programs that takes into account such reordering. We use this model to formally derive bounds on the vulnerability to concurrency bugs of different memory models. Our results show that for 2 concurrent threads, weaker memory models do indeed have a higher likelihood of allowing bugs. On the other hand, we show that as the number of parallel, buggy threads increases, the gap between the different memory models becomes proportionally insignificant, and thus the importance of using a strict memory model diminishes.

Guest: Thomas Moscibroda
Host: Yvonne-Anne Pignolet