Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Powiadomienia systemowe

Sesja wygasła!

Znaleziono wyników: 3

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: ambiguous graphs

Sortuj według:

Ogranicz wyniki do:

Universal Election Algorithm using forward links

Wróblewski D.

Prace Instytutu Podstaw Informatyki Polskiej Akademii Nauk

2003

Nr 970

1-32

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.

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ść".

Universal Election Algorithm using an auxiliary graph

Wróblewski D.

Prace Instytutu Podstaw Informatyki Polskiej Akademii Nauk

2003

Nr 968

1-24

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.

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.

Universal Election Algorithm

Wróblewski D.

Prace Instytutu Podstaw Informatyki Polskiej Akademii Nauk

2003

Nr 967

1-16

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.

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ść.