15 kwiecień 2004r.


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)).