Impossibility Proofs for Distributed Computing

Speaker(s)

Michał Strojnowski

Affiliation

Uniwersytet Warszawski

Date

May 24, 2006, 2:15 p.m.

Room

room 5870

Seminar

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.

---