Maximal Independent Set (MIS) problem är en av grunderna i studien av lokalitet i distribuerade grafalgoritmer. Detta dokument presenterar en extremt enkel randomiserad algoritm som ger en nästan optimal lokal komplexitet för detta problem, vilket för övrigt, i kombination med vissa kända tekniker, också leder till en nästan optimal global komplexitet. Klassiska MIS algoritmer av Luby [STOC'85] och Alon, Babai och Itai [JALG'86] ger den globala komplexiteten garanti att, med hög sannolikhet 1, alla noder slutar efter O(log n) rundor. Däremot är vårt första fokus på den lokala komplexiteten, och vårt huvudsakliga bidrag är att tillhandahålla en mycket enkel algoritm som garanterar att varje enskild nod v avslutas efter O(log deg(v) + log 1/ε) rundor, med sannolikhet minst 1 − ε. Garantin håller även om slumpmässigheten utanför 2-hops grannskapet v bestäms motariskt. Detta gradberoende är optimalt på grund av en lägre gräns mellan Kuhn, Moscibroda och Wattenhofer [PODC'04]. Intressant nog går denna lokala komplexitet smidigt över till en global komplexitet: genom att lägga till tekniker av Barenboim, Elkin, Pettie, och Schneider [FOCS'12; arXiv: 1202], vi 2 får en randomiserad MIS algoritm med en hög sannolikhet global komplexitet av O (log) + 2 O ( ε log log n), där  påvisar den maximala graden. Detta förbättrar över O(log 2 ) + 2 O( ε logg n) resultat av Barenboim et al., och kommer nära den nedre gränsen av Kuhn et al. Korollärer inkluderar förbättrade algoritmer för MIS i grafer med övre gräns för arboricitet, eller nedre gräns för omkrets, för härskande uppsättningar, för MIS i modellen för lokal beräkningsalgoritmer (LCA) och en snabbare distribuerad algoritm för Lovász Local Lemma. 1 Som standard använder vi frasen med hög sannolikhet för att indikera att en händelse har sannolikhet minst 1 − 1/n. 2 kvasi nanos, gigantium humeris insidentes
Ett genombrott nyligen av Ghaffari REF erhöll en randomiserad algoritm i O(log  på) + 2 O ( ε log log n) rundor.
An Improved Distributed Algorithm for Maximal Independent Set
{'venue': None, 'journal': 'arXiv: Data Structures and Algorithms', 'mag_field_of_study': ['Mathematics', 'Computer Science']}