We consider finite connected undirected graphs as a model for anonymous computer networks. In this framework we show a general purpose distributed election protocol, which uses forward links over the standard communication channels between processors. The forward links are represented in the form of structured labels, so the algorithm is a graph relabelling system, however its transformations are not local in the classical sense. For this particular algorithm we define a new notion of extended locality and claim that it still conforms to the intuitive meaning of the locality term.
PL
Rozpatrujemy skończone grafy spójne, będące modelem anonimowych sieci komputerowych. W modelu tym definiujemy uniwersalny algorytm elekcji, który w trakcie działania używa połączeń przekierowujących rozpiętych wzdłuż krawędzi grafu. Przekierowania są reprezentowane za pomocą strukturalnych etykiet, zatem algorytm jest wyrażalny w formalizmie systemów reetykietujących grafy. Jednak kroki algorytmu nie są transformacjami lokalnymi w klasycznym znaczeniu tego słowa. Dlatego też definiujemy dopasowane do tego algorytmu pojęcie lokalności rozszerzonej oraz uzasadnionym że jest ono zgodne z intuicyjnym rozumieniem terminu "lokalność".
2
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
We consider finite connected undirected graphs as a model for computer networks. In this framework we show a general-purpose distributed election algorithm, which uses a locally built auxiliary graph.
PL
W pracy rozpatrujemy nieskierowane grafy spójne, jako model sieci komputerowych. W modelu prezentujemy rozproszony algorytm elekcji, który podczas swego działania używa budowanego lokalnie grafu pomocniczego.
3
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
We consider undirected connected graphs as natural model for computer networks. For this model, the distributed election algorithm is presented, its correctness is proved and its complexity is discussed.
PL
W pracy rozpatrujemy nieskierowane grafy spójne, będące modelem sieci komputerowych. W tym modelu prezentujemy rozproszony algorytm elekcji, dowodzimy jego poprawności i dyskutujemy jego złożoność.
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.