Impossibility Proofs for Distributed Computing

Prelegent(ci)

Michał Strojnowski

Afiliacja

Uniwersytet Warszawski

Termin

24 maja 2006 14:15

Pokój

p. 5870

Seminarium

Seminarium „Teoria automatów”

---

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.

---