40 Years Of Distributed-Computability on One-Leg

演讲人: Professor Eli Gafni University of California, Los Angeles
时间: 2015-05-27 14:00-2015-05-27 15:00
地点:FIT 1-222

Research can be viewed as a search of an accepting-state in an exponential-space.  When we look in hind-sight after we find an accepting-state, can we identify a much shorter path than the one that was discovered by trial and error as the search actually proceeded?
In this talk I'll show that this is the case for Distributed-Computability: The discovery that different distributed problems have different levels of difficulty, and identifying the weakest model of distributed-computation that allows to solve a problem. I'll explain the essence of 40 years of research in an hour, by showing that if the right questions were asked at the right time, all the results could have been had in a span of time order-of-magnitude shorter.
The notion of teaching something "on one-leg" comes from ancient Hebrew tradition and means that the essence of a topic to be taught, can be taught while the student stands on one-leg. In our case, sitting will be allowed.
This talk is a new-improved battle-tested version of a talk I gave in 201 last year.  Some of the major ideas in the talk were developed in works with Afek (TAU), and Borowsky (Akamai), Lynch (MIT), and Rajsbaum (UNAM).


Eli Gafni received his first degree from the Technion, second from UIUC, and third from MIT, all in E.E. He was involved with the Internet in the early days when it consisted of only few nodes. Unlike his contemporaries in MIT, of which quite a few went on to become few hundred times Internet Millionaires, he joined UCLA computer-science department and abstracted the Internet to the point that he became even too theoretical for that discipline. He received the Presidential Young Investigator award when he was young and promising. He still promises but ain't young any more. His claim to fame is for missing on the Godel award, for lack of Journal Version, leading one of the 3 teams which found the relationship between distributed computing and algebraic topology. Nevertheless, with tenure, he is still a Professor at UCLA, holding forth that intellectual fun or the ability to roam perhaps aimlessly through intellectually challenging roads, is the reason to be in University rather than Industry. He does not envy the Millionaires, he is only partially responsible for the sorry financial-state of the UC system, and most of his publications are still missing a Journal Version.