Insamling av data från noder i ett nätverk står i centrum för många distribuerade applikationer, framför allt när de utför en global uppgift. Vi anser att information som sprids bland n noder i ett nätverk, där varje nod v har ett meddelande m(v) som måste tas emot av alla andra noder. Den tid som krävs för att sprida information har tidigare varit övre gräns med ett omvänt samband med ledning av den underliggande kommunikationsgrafen. Detta innebär höga körtider för grafer med liten ledningsförmåga. Det viktigaste bidraget i detta dokument är en algoritm som sprider information och som övervinner flaskhalsar i kommunikationen och på så sätt snabbt sprider information för en bred grupp grafer, trots sin ringa ledning. Som ett viktigt verktyg i vår studie använder vi det nyligen definierade begreppet svag ledning, en generalisering av klassisk grafledning som mäter hur väl sammankopplade komponenterna i en graf är. Vår hybridalgoritm, som växlar mellan slumpmässiga och deterministiska kommunikationsfaser, utnyttjar konnektiviteten inom komponenter genom att först tillämpa partiell informationsspridning, varefter meddelanden skickas över flaskhalsar, vilket sprider sig ytterligare i hela nätverket. Detta ger betydande förbättringar över de mest kända körtiderna av algoritmer för information som sprids på någon graf som har en stor svag ledning, från polynom till polylogaritmiskt antal rundor. Vi visar kraften i snabb informationsspridning för att utföra globala uppgifter om ledare val problemet, som är kärnan i distribuerade datorer. Våra resultat ger en algoritm för ledarval som har en skalbar körtid på grafer med stor svag ledning, vilket förbättrar avsevärt jämfört med tidigare resultat.
För att övervinna flaskhalsar i grafer med liten ledning, Censor-Hillel och Shachnai använde begreppet svag ledning för att förbättra körtiden för skvaller REF.
Fast information spreading in graphs with large weak conductance
{'venue': "SODA '11", 'journal': None, 'mag_field_of_study': ['Computer Science']}