Yayınlanmış 1 Ocak 2009
| Sürüm v1
Konferans bildirisi
Açık
Communication Efficiency in Self-Stabilizing Silent Protocols
Oluşturanlar
- 1. Univ Grenoble 1, VERIMAG UMR 5104, Grenoble, France
- 2. Osaka Univ, Grad Sch Informat Sci Technol, Osaka, Japan
- 3. Univ Paris 06, LIP6, Paris, France
Açıklama
In this paper, our focus is to lower the communication complexity of self-.stabilizing protocols below the need of checking every neighbor forever. Our contribution is threefold: (i) We provide new complexity measures for communication efficiency of self-stabilizing protocols, especially it? the stabilized phase or when there are no faults, (ii) On the negative side, we show that for non-trivial problems such as coloring, maximal matching, and maximal independent set, it is impossible to get (deterministic or probabilistic) self stabilizing solutions where every participant communicates with less than every neighbor in the stabilized phase, and (iii) On the positive side, we present protocols for maximal matching and maximal independent set such that a fraction of the participants communicates with exactly one neighbor in the stabilized phase.
Dosyalar
bib-42524472-712e-4863-bdc3-81dbe3dbc8de.txt
Dosyalar
(184 Bytes)
| Ad | Boyut | Hepisini indir |
|---|---|---|
|
md5:a75448ee2dc5f8525b0caf2e61880d85
|
184 Bytes | Ön İzleme İndir |