Lovász Local Lemma (LLL), som infördes av Erdős och Lovász 1975, är ett kraftfullt verktyg för den probabilistiska metoden som gör att man kan bevisa att en uppsättning n "dåliga" händelser inte sker med icke-noll sannolikhet, förutsatt att händelserna har begränsat beroende. LLL själv föreslår dock inte hur man ska hitta en punkt för att undvika alla dåliga händelser. Sedan Becks arbete (1991) har det gjorts en ihärdig ansträngning för att hitta ett konstruktivt bevis (dvs. En algoritm) för LLL eller svagare versioner av den. I ett stort genombrott visade Moser och Tardos (2010) att man kan hitta en punkt där man undviker alla dåliga händelser på ett effektivt sätt. De föreslog också en distribuerad/parallell version av sin algoritm som kräver O(log 2 n) rundor av kommunikation i ett distribuerat nätverk. I detta dokument tillhandahåller vi två nya distribuerade algoritmer för LLL som förbättrar både effektiviteten och enkelheten hos Moser-Tardos algoritm. För tydlighetens skull uttrycker vi våra resultat i termer av den symmetriska LLL även om båda algoritmerna behandlar den asymmetriska versionen. Låt p bundet sannolikheten för någon dålig händelse och d vara den maximala graden i beroende grafen av de dåliga händelserna. När epd 2 < 1 ger vi en riktigt enkel LLL-algoritm som körs i O(log 1/epd 2 n) rundor. Under stramare villkor ep(d + 1) < 1 ger vi en något långsammare algoritm som körs i O(log 2 d · log 1/ep(d+1) n) rundor. Dessutom ger vi en algoritm som körs i sublogaritmiska rundor under villkoret p · f (d) < 1, där f (d) är en exponentiell funktion av d. Även om villkoren för LLL är lokalt kontrollerbara, visar vi att alla distribuerade LLL algoritm kräver  och (log * n) rundor. I många graffärgning problem förekomsten av en giltig färgning fastställs av en eller flera tillämpningar av LLL. Med hjälp av våra LLL-algoritmer ger vi logaritmisk tid *
Begränsningen av storleken på Δ kan avlägsnas via den distribuerade Lovász Local Lemma REF.
Distributed algorithms for the Lovász local lemma and graph coloring
{'venue': "PODC '14", 'journal': None, 'mag_field_of_study': ['Computer Science']}