Speaker: Eli Gafni
Affiliation: UCLA - Computer Science Department
ABSTRACT: We resolve conclusively a foundational question in Theoretical Distributed Computing, open for almost two and a half decades. Jayanti formulated the so called Robustness Question in 1994: “Joining two objects results in a new object by simply considering the cartesian product of their specifications. Is the power of the joined object to affect consensus, is the maximum power of its constituents?” In a brilliant work Lo and Hadzilacos showed that for non-deterministic types the answer is negative. For deterministic types the question remained open, despite numerous trials to resolve the question positively.These trials were deemed good intuition rather than a rigorous proof. Here, we present a novel proof, based on the idea, proposed by Herlihy and Wing in the context of implementation of an object, that an “object state” serves for specification of behavior, but when implemented, an object is really in a cloud of states, and its next transition is based on a non-deterministic choice (an adversary) of a state in the cloud, that results in the next cloud of states. What hampered progress on the Robustness Question for so long was the conceptually mistaken view that when using a “real object” then the object is in some “real” state. It is not. It is in a cloud of uncertainty. Hence the title: We cannot know the unobservable.
Date(s) - May 22, 2018
4:15 pm - 5:45 pm