I detta dokument behandlas den grundläggande PULL-modellen för kommunikation, där varje agent i varje omgång extraherar information från få slumpmässigt utvalda agenter. Vi försöker identifiera den minsta mängd information som avslöjas i varje interaktion (meddelandestorlek) som ändå möjliggör effektiva och robusta beräkningar av grundläggande informationsspridningsuppgifter. Vi fokuserar på Majority Bit Dissemination problem som anser en population av n agenter, med en utsedd delmängd av källagenter. Varje källagent har en ingångsbit och varje agent har en utgångsbit. Målet är att låta alla agenter konvergera sina utdatabitar på den vanligaste inmatningsdelen av källorna (majoriteten bit). Observera att det särskilda fallet med ett enda källombud motsvarar det klassiska problemet med radio- och TV-sändningar (även kallat Rumor Spridning). Vi koncentrerar oss på den allvarliga feltoleranta kontexten av självstabilisering, där en korrekt konfiguration så småningom måste uppnås, trots att alla agenter startar avrättningen med godtyckliga inledande tillstånd. I synnerhet, specifikationen av vem som är en källa och vad som är dess första inmatning bit kan ställas in av en motståndare. Vi designar först en allmän kompilator som i huvudsak kan omvandla vilken självstabiliserande algoritm som helst med en viss egenskap (kallad "bitwise-oberoende egenskapen") som använder -bits meddelanden till en som bara använder log-bits meddelanden, samtidigt som den bara betalar en liten straffavgift i körtiden. Genom att tillämpa denna kompilator rekursivt får vi sedan en självstabiliserande Clock Synkronisering protokoll, där agenter synkroniserar sina klockor modulo några givet heltal T, inom Õ(logg n log T ) rundor w.h.p., och med meddelanden som endast innehåller 3 bitar. Vi använder sedan den nya Clock Synkronisering verktyg för att få en självstabiliserande Majority Bit Dissemination protokoll som konvergerar i Õ(log n) tid, w.h.p., på varje inledande konfiguration, förutsatt att förhållandet av källor som stöder minoritetsyttrandet begränsas bort från hälften. Dessutom använder detta protokoll också endast 3 bitar per interaktion.
Ett aktuellt exempel på denna smak är REF för meddelandestorlek i självstabiliserande klocksynkronisering.
Minimizing message size in stochastic communication patterns: fast self-stabilizing protocols with 3 bits
{'venue': 'Distributed Computing', 'journal': 'Distributed Computing', 'mag_field_of_study': ['Computer Science', 'Engineering']}