10.15 - 11.00 Deterministyczne i
niedeterministyczne rozgłaszanie w sieciach radiowych
Rafał
Rusin (Uniwersytet Warszawski)
Streszczenie: Rozglaszanie (broadcast) polega na
wyslaniu z jednego wezla sieci
pewnej wiadomosci do wszystkich pozostalych wezlow.
Opowiem o dwoch algorytmach rozglaszania w sieciach radiowych.
Jeden jest randomizowany i dziala w czasie
O(D*log(N/epsilon)*log(delta)),
gdzie D jest tzw. network diameter (srednica sieci - dlugosc
najdluzszej sciezki
o rozlacznych wierzcholkach w sieci), N - gorne ograniczenie na liczbe
wezlow,
delta - gorne ograniczenie na maksymalny stopien wezlow.
Algorytm zatrzymuje sie z prawdopodobienstwem 1-epsilon. Epsilon jest
ustalona stala.
Dodatkowo algorytm ten jest odporny na modyfikacje sieci w trakcie
dzialania. Wystarcza zalozenie, ze siec jest spojna.
Drugi algorytm (Single Prime Algorithm) jest deterministyczny i dziala
w
czasie O(n^(3/2)).