KSV13
Summary
Korman, Amos, Sereni, Jean-Sébastien and Viennot, Laurent (2013) Toward more localized local algorithms: removing assumptions concerning global knowledge. Distributed Computing, 26(5-6):289-308. (PDF)
Abstract
Numerous sophisticated local algorithm were suggested in the literature for various fundamental problems. Notable examples are the MIS and $(\Delta+1)$-coloring algorithms by Barenboim and Elkin, by Kuhn, and by Panconesi and Srinivasan, as well as the $\bigo{\Delta^2}$-coloring algorithm by Linial. Unfortunately, most known local algorithms (including, in particular, the aforementioned algorithms) are \emph{non-uniform}, that is, they assume that all nodes know good estimations of one or more global parameters of the network, e.g., the maximum degree $\Delta$ or the number of nodes $n$. This paper provides a rather general method for transforming a non-uniform local algorithm into a \emph{uniform} one. Furthermore, the resulting algorithm enjoys the same asymptotic running time as the original non-uniform algorithm. Our method applies to a wide family of both deterministic and randomized algorithms. Specifically, it applies to almost all of the state of the art non-uniform algorithms regarding MIS and Maximal Matching, as well as to many results concerning the coloring problem. (In particular, it applies to all aforementioned algorithms.) To obtain our transformations we introduce a new distributed tool called \emph{pruning algorithms}, which we believe may be of independent interest.
Bibtex entry
@ARTICLE { KSV13,
AUTHOR = { Korman, Amos and Sereni, Jean-Sébastien and Viennot, Laurent },
TITLE = { Toward more localized local algorithms: removing assumptions concerning global knowledge },
JOURNAL = { Distributed Computing },
VOLUME = { 26 },
NUMBER = { 5-6 },
YEAR = { 2013 },
MONTH = { jan },
PAGES = { 289-308 },
ABSTRACT = { Numerous sophisticated local algorithm were suggested in the literature for various fundamental problems. Notable examples are the MIS and $(\Delta+1)$-coloring algorithms by Barenboim and Elkin, by Kuhn, and by Panconesi and Srinivasan, as well as the $\bigo{\Delta^2}$-coloring algorithm by Linial. Unfortunately, most known local algorithms (including, in particular, the aforementioned algorithms) are \emph{non-uniform}, that is, they assume that all nodes know good estimations of one or more global parameters of the network, e.g., the maximum degree $\Delta$ or the number of nodes $n$. This paper provides a rather general method for transforming a non-uniform local algorithm into a \emph{uniform} one. Furthermore, the resulting algorithm enjoys the same asymptotic running time as the original non-uniform algorithm. Our method applies to a wide family of both deterministic and randomized algorithms. Specifically, it applies to almost all of the state of the art non-uniform algorithms regarding MIS and Maximal Matching, as well as to many results concerning the coloring problem. (In particular, it applies to all aforementioned algorithms.) To obtain our transformations we introduce a new distributed tool called \emph{pruning algorithms}, which we believe may be of independent interest. },
PDF = { http://gang.inria.fr/~viennot/publis/articles/distrcomp2013MoreLocalized.pdf },
}