You are not logged in | Log in

Impossibility Proofs for Distributed Computing

Michał Strojnowski
Uniwersytet Warszawski
May 24, 2006, 2:15 p.m.
room 5870
Seminar Automata Theory

Many problems have no solution in distributed computing. One of the best known examples is Byzantine Generals Problem, for which it is shown that if at least one third of the generals are malicious, there is no way to achieve mutual consensus among the rest. There are many more such examples, especially where randomization and asynchronization is considered. Techniques used to show impossibility are sometimes very interesting, and may be applied in areas different from distributed computing. This presentation will be based on a classical paper of Nancy Lynch, in which she managed to collect over a hundred of such proofs. Some of them are in fact lower bounds, that show some problems unsolvable with limited resources. Of course only a few particularly interesting proofs will be presented.