Randomized enumeration

• Autorzy: Dembiński P.
• Języki publikacji: PL

Abstrakty

PL

W pracy zaproponowano probabilistyczną wersję rozproszonego algorytmu numeracji węzłów sieci procesów. Zaletą tego probabilistycznego podejścia jest to, że wynikowy algorytm poprawnie numeruje węzły sieci o dowolnej topologii i może być całkowicie asynchroniczny (w przypadku deterministycznych rozwiązań obie te cechy mają pewne ograniczenia). Przebadano zarówno poprawność zaproponowanego algorytmu jak i jego efektywność. Te ostatnią szacuje sie poprzez oczekiwaną liczbę 'rund', w terminach których zdefiniowano algorytm. Okazuje się, że ta oczekiwana wartość jest bliska jedynce, a to znaczy, że czas wykonania algorytmu jest w praktyce równy maksymalnemu czasowi przepływu informacji pomiędzy węzłami rozpatrywanej sieci. Algorytm został opisany w języku specyfikacji Estelle. Eksperymenty symulacyjne (wykonywane zarówno dla deterministycznych jak i probabilistycznych specyfikacji algorytmu w tym formalizmie) potwierdziły otrzymane rezultaty.

EN

The paper describes a randomized version of the distributed enumeration algorithm (protocol) in a network of processes. The advantage of the randomized approach is in that the resulting algorithm works for all network topologies and for fully asynchronous communication (which is not the case for the deterministic case). Correctness of the protocol is examined as well its efficiency. The latter is estimated in probabilistic terms by means of the expected number of 'drawing rounds' in which the algorithm is defined. The value is shown to be close to one and it means that practically the algorithm is performed in time needed to broadcast a message in the network. The algorithm is implemented in the specification language Estelle. Simulation experiments (with both deterministic and randomized Estelle specifications) confirmed the obtained results.

Słowa kluczowe

EN

randomized algorithms; distributed algorithms; network protocols

• Wydawca: Instytut Podstaw Informatyki PAN
• Czasopismo: Prace Instytutu Podstaw Informatyki Polskiej Akademii Nauk
• Rocznik: 1998
• Tom: nr 848
• Strony: 1--17
• Opis fizyczny: I--XI.

Twórcy

autor

Dembiński P.

• Piotr Dembiński Institute of Computer Science Polish Academy of Science ul. Ordona 21 01-237 Warsaw, Poland,