Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People

The Taub Faculty of Computer Science Events and Talks

Theory Seminar: Causality, Knowledge and Coordination in Synchronous Systems
event speaker icon
Ido Ben-Zvi (EE, Technion)
event date icon
Wednesday, 14.03.2012, 12:30
event location icon
Taub 201
Coordinating the proper ordering of events across remote sites is a central task of distributed applications. In asynchronous systems, such coordination depends in an essential way upon message chains, as captured by Lamport's happened-before relation. The relation provides a useful approximation of causality, in the sense that in asynchronous systems two event can only be causally related if they are Lamport related.

The talk will consider coordination and causality in synchronous systems, where upper bounds are available on message transmission times over each channel, and processes share a global clock. Here, communication is still essential whenever a spontaneous external input is meant to trigger an ordered sequence of responses across various sites. We capture the essence of such a coordination task in a proposed class of coordination problems called Ordered Response. Within this framework we embark on a search for a similar notion of causality. We will not ouch upon knowledge in any great depth, but consider that in a synchronous setting both message chains and the passage of time can be used to spread information across the system, and hence to enable coordination.

Indeed, it turns out that the synchronous analog for Lamport's causality is a structure that carefully combines message chains and the existing upper bounds on transmission times. This causal structure, called the centipede, is shown to be necessary in every solution of the Ordered Response problem.

Time permitting, we will also discuss the causal structure that captures coordination when simultaneous actions across remote sites is required.