13.00 - 13.45 Asynchroniczny
broadcasting
Bogdan
Chlebus (University of Colorado, USA)
Streszczenie:Rozwazamy
problem rozglaszania w modelach asynchronicznych sieci
radiowych. Modele sa okreslone przy uzyciu pojecia adwersarza. Protokoly
komunikacyjne okreslaja ile razy dana wiadomosc ma byc nadana. Calkowita
liczba nadawan komunikatu jest okreslona jako praca algorytmu i jest
uzywana jako miara zlozonosci obliczeniowej. Siec radiowa jest podana
jako
dane wejsciowe dla algorytmu sekwencyjnego. Zadania algorytmiczne to na
przyklad znalezienie efektywnego protokolu lub sprawdzenie poprawnosci
danego protokolu dla danej sieci. Pokazujemy dolne oszacowania na prace
protokolow, algorytmy wielomianowe dla pewnych problemow sekwencyjnych,
oraz NP-trudnosc pewnych zadan.