Ido Ben-Zvi, Ph.D. Thesis Seminar
Wednesday, 16.3.2011, 11:30
Meyer 861 (Electrical Engineering building)
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.