Betydelsen av skalbarhet och feltolerans i moderna distribuerade system har lett till betydande forskning i multicast protokoll med hjälp av skvaller. I ett skvallerprotokoll vidarebefordrar varje nod meddelanden till en liten uppsättning av "gossip partners" utvalda slumpmässigt från hela gruppmedlemskapet. Genom att överge de starka tillförlitlighetsgarantierna i traditionella protokoll till förmån för probabilistiska garantier kan skvallerprotokoll ge större skalbarhet och feltolerans. I tidiga skvalleralgoritmer, partners valdes enhetligt slumpmässigt från hela medlemskapet, begränsa skalbarhet på grund av de resurser som krävs för att lagra och upprätthålla kompletta medlemsvyer vid varje nod. Senare protokoll undvek detta problem genom att lagra mycket mindre slumpmässiga undergrupper av medlemskapet vid varje nod, och välja skvaller partners endast från dessa lokala vyer. Sådana protokoll är subtila: åtminstone vissa lokala åsikter måste ändras som svar på förändringar i gruppmedlemskapet för att bevara konnektivitet och prestandagarantier. Även om dessa protokoll har varit föremål för mycket simulering och analys, formella bevis på viktiga egenskaper - särskilt sannolikheten för partitionering - har förblivit svårfångade. I denna artikel ger vi en ny skalbar skvallerbaserad algoritm för lokalt vyunderhåll, tillsammans med ett bevis på att den förväntade tiden tills en nätverkspartition är minst exponentiellt i kvadraten av vystorleken. Vi utvecklar också probabilistiska gränser på in-grad (därav belastningen) av enskilda noder, och hävdar att protokoll som saknar vår förstärkning komponent så småningom konvergera till stjärnliknande nätverk, vars anslutning beror på en liten uppsättning överbelastade noder. Vi hävdar också att den oriktade konnektivitet grafen är en expander, för vilken programnivå skvaller multi-cast protokoll kommer att konvergera snabbt. Våra teoretiska resultat stöds av simuleringar.
Allavena m.fl. REF beskrev en skalbar skvallerbaserad för lokalt vyunderhåll.
Correctness of a gossip based membership protocol
{'venue': "PODC '05", 'journal': None, 'mag_field_of_study': ['Computer Science']}