Vi introducerar projektion analys-en ny teknik för att analysera stopptiden för protokoll som är baserade på slumpmässig linjär nätverk kodning (RLNC). Projektionsanalys förenklar drastiskt, utökar och stärker tidigare resultat på RLNC skvaller protokoll. Vi analyserar RLNC-skvaller i ett allmänt ramverk för nätverks- och kommunikationsmodeller som omfattar och förenar de modeller som tidigare använts i detta sammanhang. Vi visar, i de flesta miljöer för första gången, att RLNC skvaller konvergerar med hög sannolikhet i optimal tid. De flesta stopptider är av formen O(k + T ), där k är antalet meddelanden som ska distribueras och T är den tid det tar att sprida ett meddelande. Detta innebär att RLNC skvaller uppnår "perfekt pipeline". Vår analys sträcker sig direkt till mycket dynamiska nätverk där topologin kan förändras helt när som helst. Detta är fortfarande sant, även om nätverksdynamiken styrs av en fullt adaptiv motståndare som känner till hela nätverkstillståndet. Praktiskt taget ingenting förutom enkla O (kT ) sekventiella översvämning protokoll var tidigare känt för en sådan inställning. Medan RLNC skvaller fungerar i denna stora variation av nätverk förblir vår analys densamma och extremt enkel. Detta står i kontrast till mer komplexa bevis som lades fram för att ge mindre starka resultat i olika specialfall.
Verket av REF analyserar RLNC skvaller i stor allmänhet.
Analyzing Network Coding (Gossip) Made Easy
{'venue': 'JACM', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}