Beyond Lamport causality: Combining time and communication for distributed coordination

The Faculty of Informatics is pleased to announce a seminar given by Yoram Moses

DATE: Tuesday, November 8th, 2011
PLACE: USI Università della Svizzera italiana, room SI-006, Informatics building (Via G. Buffi 13)
TIME: 15:30

ABSTRACT:
Communicated messages play a central role in coordinating events in distributed computer systems. In purely asynchronous systems, Lamport's "happened-before" relation, based on message chains, has been shown to govern causality and coordination. This talk will consider the role that guarantees regarding message transmission times plays. The existence of clocks and such timing information significantly affect the ways in which sites can coordinate their actions.

In this work, Lamport's relation is replaced by two relations, one involving message chains and the other timing guarantees. A new class of coordination problems is presented, and causal structures that generalize message chains are shown to characterize coordination in a model with clocks and time bounds. The main results are obtained by reducing coordination to properties involving knowledge in distributed systems, and then characterizing this knowledge in terms of time bounds and communication.

The talk is self-contained, and is geared towards a broad audience. It is based on joint work with Ido Ben Zvi.

BIO:
Yoram Moses is a professor of Electrical Engineering at the Technion. He received a PhD in Computer Science from Stanford in 1986, and is the recipient of the 1997 Gödel prize and the 2009 Dijkstra prize for his work on knowledge in distributed systems.

HOST: Prof. Fabian Kuhn