caa a22 4500 445355166 CHVBK 20180317142857.0 cr unu---uuuuu 170323e20110401xx s 000 0 eng 10.1007/s00446-010-0121-5 doi (NATIONALLICENCE)springer-10.1007/s00446-010-0121-5 An optimal bit complexity randomized distributed MIS algorithm [Elektronische Daten] [Y. Métivier, J. Robson, N. Saheb-Djahromi, A. Zemmari] We present a randomized distributed maximal independent set (MIS) algorithm for arbitrary graphs of size n that halts in time O(log n) with probability 1 − o(n −1), and only needs messages containing 1 bit. Thus, its bit complexity par channel is O(log n). We assume that the graph is anonymous: unique identities are not available to distinguish between the processes; we only assume that each vertex distinguishes between its neighbours by locally known channel names. Furthermore we do not assume that the size (or an upper bound on the size) of the graph is known. This algorithm is optimal (modulo a multiplicative constant) for the bit complexity and improves the best previous randomized distributed MIS algorithms (deduced from the randomized PRAM algorithm due to Luby (SIAM J. Comput. 15:1036-1053, 1986)) for general graphs which is O(log2 n) per channel (it halts in time O(log n) and the size of each message is log n). This result is based on a powerful and general technique for converting unrealistic exchanges of messages containing real numbers drawn at random on each vertex of a network into exchanges of bits. Then we consider a natural question: what is the impact of a vertex inclusion in the MIS on distant vertices? We prove that this impact vanishes rapidly as the distance grows for bounded-degree vertices and we provide a counter-example that shows this result does not hold in general. We prove also that these results remain valid for Luby's algorithm presented by Lynch (Distributed algorithms. Morgan Kaufman 1996) and by Wattenhofer (http://dcg.ethz.ch/lectures/fs08/distcomp/lecture/chapter4.pdf, 2007). This question remains open for the variant given by Peleg (Distributed computing—a locality-sensitive approach 2000). Springer-Verlag, 2010 Métivier Y. Université de Bordeaux, LaBRI UMR CNRS 5800, 351 cours de la Libération, 33405, Talence, France aut Robson J. Université de Bordeaux, LaBRI UMR CNRS 5800, 351 cours de la Libération, 33405, Talence, France aut Saheb-Djahromi N. Université de Bordeaux, LaBRI UMR CNRS 5800, 351 cours de la Libération, 33405, Talence, France aut Zemmari A. Université de Bordeaux, LaBRI UMR CNRS 5800, 351 cours de la Libération, 33405, Talence, France aut Distributed Computing Springer-Verlag 23/5-6(2011-04-01), 331-340 0178-2770 23:5-6<331 2011 23 446 https://doi.org/10.1007/s00446-010-0121-5 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00446-010-0121-5 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Métivier Y. Université de Bordeaux, LaBRI UMR CNRS 5800, 351 cours de la Libération, 33405, Talence, France aut NATIONALLICENCE 700 1- Robson J. Université de Bordeaux, LaBRI UMR CNRS 5800, 351 cours de la Libération, 33405, Talence, France aut NATIONALLICENCE 700 1- Saheb-Djahromi N. Université de Bordeaux, LaBRI UMR CNRS 5800, 351 cours de la Libération, 33405, Talence, France aut NATIONALLICENCE 700 1- Zemmari A. Université de Bordeaux, LaBRI UMR CNRS 5800, 351 cours de la Libération, 33405, Talence, France aut NATIONALLICENCE 773 0- Distributed Computing Springer-Verlag 23/5-6(2011-04-01), 331-340 0178-2770 23:5-6<331 2011 23 446 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer