The Taub Faculty of Computer Science Events and Talks

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, active coordination is required 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 touch 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.