Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Znaleziono wyników: 2

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: anonymous networks

Sortuj według:

Ogranicz wyniki do:

Communication Complexity of Consensus in Anonymous Message Passing Systems

Fusco E. G., Pelc A.

Fundamenta Informaticae

2015

Vol. 137, nr 3

305--322

We consider the message complexity of achieving consensus in synchronous anonymous message passing systems. Unlabeled processors (nodes) communicate through links of a network. An adversary wakes up some subset of processors at possibly different times and assigns them arbitrary numerical input values. All other processors are dormant and do not have input values. Any message wakes up a dormant processor. The goal of consensus is to have all processors agree on one of the input values. We seek deterministic consensus algorithms using as few messages as possible. As opposed to most of the literature on consensus, the difficulty of our scenario are not faults (we assume that the network is fault-free) but the arbitrary network topology combined with the anonymity of nodes. For n-node networks of unknown topology we show a consensus algorithm using Ώ(n2) messages; this complexity is optimal for this class. We show that if the network topology is known, then the complexity of consensus decreases significantly. Our main contribution is an algorithm that uses Ώ(n2/3 log2 n) messages on any n-node network and we show that some networks require (n log n) messages to achieve consensus.

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