I detta dokument studerar vi frågan om hur effektivt en samling sammankopplade noder kan utföra en global beräkning i GOSSIP-modellen för kommunikation. I denna modell, noder inte vet den globala topologin av nätverket, och de kan bara initiera kontakt med en enda granne i varje runda. Denna modell står i kontrast till den mycket mindre restriktiva LOCAL-modellen, där en nod samtidigt kan kommunicera med alla sina grannar i en enda runda. En grundläggande fråga i detta sammanhang är hur många kommunikationsrundor som krävs för problemet med informationsspridning, där varje nod har någon information och är skyldig att samla in alla andra. I LOCAL-modellen är detta ganska enkelt: varje nod sänder all sin information i varje omgång, och antalet rundor som krävs kommer att vara lika med diametern på den underliggande kommunikationsgrafen. I GOSSIP modellen, varje nod måste självständigt välja en enda granne att kontakta, och bristen på global information gör det svårt att göra någon form av principiella val. Som sådan har forskare fokuserat på den enhetliga skvalleralgoritmen, där varje nod självständigt väljer en granne på måfå. När grafen är väl ansluten, fungerar detta ganska bra. I en rad vackra papper visade forskarna en sekvens av successivt starkare gränser på det antal rundor som krävs när det gäller lednings- och grafstorlek n, som kulminerar i en gräns av O( och −1 log n). I detta dokument visar vi att en ganska enkel ändring av protokollet ger en algoritm som löser problemet med informationsspridning i högst O(D + polylog(n) rundor i ett nätverk av diameter D, utan beroende av ledning. Detta är som mest en additiv polylogaritmisk faktor från den triviala nedre gränsen av D, som gäller även i LOCAL-modellen. I själva verket bevisar vi att något starkare är sant: någon algoritm * Detta arbete stöddes delvis av Simons Postdoktor Fellows Program och NSF bevilja CCF-0843915. Tillstånd att göra digitala eller papperskopior av hela eller delar av detta arbete för personligt bruk eller klassrum beviljas utan avgift, förutsatt att kopiorna inte görs eller distribueras för vinst eller kommersiella fördelar och att kopiorna är försedda med detta meddelande och den fullständiga hänvisningen på första sidan. För att kopiera på annat sätt, för att återpublicera, för att posta på servrar eller för att omfördela till listor, krävs tidigare specifik behörighet och/eller avgift. som kräver T-rundor i LOCAL-modellen kan simuleras i O(T + polylog(n)-rundor i GOSSIP-modellen. Vi bevisar alltså att dessa två modeller av distribuerad beräkning i huvudsak är likvärdiga.
Slutligen visade det sig i REF att en enkel ändring av Push&Pull-algoritmen ger en lösning för ryktesspridning med tids komplexitet av högst O(D + poly log n), där D är nätets diameter, därför utan beroende av ledning.
Global computation in a poorly connected world: fast rumor spreading with no dependence on conductance
{'venue': "STOC '12", 'journal': None, 'mag_field_of_study': ['Computer Science', 'Physics', 'Mathematics']}