Skvallerprotokoll

Ett skvallerprotokoll eller epidemiprotokoll är en procedur eller process för peer-to-peer-kommunikation i dator som är baserad på hur epidemier sprids. Vissa distribuerade system använder peer-to-peer-skvaller för att säkerställa att data sprids till alla medlemmar i en grupp. Vissa ad-hoc-nätverk har inget centralt register och det enda sättet att sprida gemensamma data är att lita på att varje medlem skickar den vidare till sina grannar.

Kommunikation

Konceptet med skvallerkommunikation kan illustreras genom analogin med kontorsanställda som sprider rykten. Låt oss säga att kontorsarbetarna samlas runt vattenkylaren varje timme. Varje anställd parar ihop sig med en annan, vald slumpmässigt, och delar med sig av det senaste skvallret. I början av dagen startar Dave ett nytt rykte: han kommenterar Bob att han tror att Charlie färgar hans mustasch. Vid nästa möte berättar Bob för Alice, medan Dave upprepar idén för Eve. Efter varje möte med vattenkylare fördubblas antalet individer som har hört ryktet ungefär (även om detta inte står för skvaller två gånger till samma person; kanske försöker Dave berätta historien för Frank, bara för att upptäcka att Frank redan hört det från Alice). Datorsystem implementerar vanligtvis den här typen av protokoll med en form av slumpmässigt "peer-val": med en given frekvens väljer varje maskin en annan maskin slumpmässigt och delar alla rykten.

Varianter och stilar

Det finns förmodligen hundratals varianter av specifika skvallerliknande protokoll eftersom varje användningsscenario sannolikt kommer att anpassas efter organisationens specifika behov.

Till exempel kan ett skvallerprotokoll använda några av dessa idéer:

  • Kärnan i protokollet involverar periodiska, parvisa inter-processinteraktioner.
  • Informationen som utbyts under dessa interaktioner är av begränsad storlek.
  • När agenter interagerar ändras tillståndet för åtminstone en agent för att återspegla den andras tillstånd.
  • Tillförlitlig kommunikation förutsätts inte.
  • Frekvensen av interaktionerna är låg jämfört med typiska meddelandefördröjningar så att protokollkostnaderna är försumbara.
  • Det finns någon form av slumpmässighet i kamraturvalet. Peers kan väljas från hela uppsättningen noder eller från en mindre uppsättning grannar .
  • På grund av replikeringen finns det en implicit redundans av den levererade informationen.

Protokolltyper

Det är användbart att särskilja två rådande stilar av skvallerprotokoll:

  • Spridningsprotokoll (eller ryktesspridningsprotokoll). Dessa använder skvaller för att sprida information; de fungerar i princip genom att översvämma agenter i nätverket, men på ett sätt som producerar begränsade värsta tänkbara belastningar:
    1. Protokoll för spridning av händelser använder skvaller för att utföra multicasts . De rapporterar händelser, men skvallret inträffar med jämna mellanrum och händelser utlöser faktiskt inte skvallret. Ett problem här är den potentiellt höga latensen från det att händelsen inträffar tills den levereras.
    2. Protokoll för spridning av bakgrundsdata skvallrar kontinuerligt om information associerad med de deltagande noderna. Vanligtvis är spridningsfördröjningen inte ett problem, kanske för att informationen i fråga ändras långsamt eller att det inte finns någon betydande straff för att agera på lite inaktuella data.
  • Protokoll som beräknar aggregat . Dessa beräknar ett nätverksomfattande aggregat genom att sampla information vid noderna i nätverket och kombinera värdena för att komma fram till ett systemomfattande värde – det största värdet för vissa mätnoder som görs, minsta, etc. Nyckelkravet är att aggregatet måste kunna beräknas genom parvisa informationsutbyten av fast storlek; dessa avslutas typiskt efter ett antal omgångar av informationsutbyte logaritmiskt i systemstorleken, vid vilken tidpunkt ett allt-till-alla-informationsflödesmönster kommer att ha etablerats. Som en bieffekt av aggregering är det möjligt att lösa andra typer av problem med hjälp av skvaller; till exempel finns det skvallerprotokoll som kan ordna noderna i en skvalleröverlagring till en lista sorterad efter nod-id (eller något annat attribut) i logaritmisk tid med hjälp av aggregeringsliknande utbyte av information. På liknande sätt finns det skvalleralgoritmer som arrangerar noder i ett träd och beräknar aggregat som "summa" eller "räkning" genom att skvallra i ett mönster som är partiskt för att matcha trädstrukturen.

Många protokoll som föregår den tidigaste användningen av termen "skvaller" faller inom denna ganska inkluderande definition. Till exempel routingprotokoll för Internet ofta skvallerliknande informationsutbyte. Ett skvallersubstrat kan användas för att implementera ett standardrutat nätverk: noder "skvallrar" om traditionella punkt-till-punkt-meddelanden, vilket effektivt driver trafik genom skvallerlagret. Om bandbredden tillåter, innebär detta att ett skvallersystem potentiellt kan stödja vilket klassiskt protokoll som helst eller implementera vilken klassisk distribuerad tjänst som helst. En så brett inkluderande tolkning är dock sällan avsedd. Mer typiska skvallerprotokoll är de som specifikt körs på ett regelbundet, periodiskt, relativt lat, symmetriskt och decentraliserat sätt; den höga graden av symmetri mellan noder är särskilt karakteristisk. Således, även om man skulle kunna köra ett 2-fas commit-protokoll över ett skvallersubstrat, skulle det strida mot andemeningen, om inte formuleringen, i definitionen.

Termen konvergent konsistent används ibland för att beskriva protokoll som uppnår exponentiellt snabb spridning av information. För detta ändamål måste ett protokoll sprida all ny information till alla noder som kommer att påverkas av informationen inom tidslogaritmisk storlek i systemet ("blandningstiden" måste vara logaritmisk i systemstorlek).

Exempel

Anta att vi vill hitta det objekt som bäst matchar något sökmönster, inom ett nätverk av okänd storlek, men där datorerna är länkade till varandra och där varje maskin kör ett litet agentprogram som implementerar ett skvallerprotokoll .

  • För att starta sökningen skulle en användare be den lokala agenten att börja skvallra om söksträngen. (Vi antar att agenter antingen börjar med en känd lista över peers eller hämtar denna information från någon form av delad butik.)
  • Med jämna mellanrum, i någon takt (låt oss säga tio gånger per sekund, för enkelhetens skull), väljer varje agent någon annan agent på måfå och skvallrar med den. Söksträngar kända för A kommer nu också att vara kända för B, och vice versa. I nästa "omgång" av skvaller kommer A och B att välja ytterligare slumpmässiga kamrater, kanske C och D. Detta fördubblingsfenomen runda för varv gör protokollet mycket robust, även om vissa meddelanden går vilse, eller om några av de utvalda kamraterna är samma eller redan känner till söksträngen.
  • Vid mottagandet av en söksträng för första gången kontrollerar varje agent sin lokala dator för matchande dokument.
  • Agenter skvallrar också om den bästa matchen hittills. Således, om A skvallrar med B, efter interaktionen, kommer A att känna till de bästa matchningarna som B känner till, och vice versa. Bästa matchningar kommer att "spridas" genom nätverket.

Om meddelandena kan bli stora (till exempel om många sökningar är aktiva samtidigt) bör en storleksbegränsning införas. Sökningar bör också "åldras" från nätverket.

Det följer att inom logaritmisk tid i storleken på nätverket (antalet agenter) kommer varje ny söksträng att ha nått alla agenter. Inom en ytterligare fördröjning av samma ungefärliga längd kommer varje agent att lära sig var den bästa matchningen kan hittas. I synnerhet kommer agenten som startade sökningen att ha hittat den bästa matchningen.

Till exempel, i ett nätverk med 25 000 maskiner kan vi hitta den bästa matchningen efter cirka 30 omgångar av skvaller: 15 för att sprida söksträngen och 15 till för att upptäcka den bästa matchningen. Ett skvallerutbyte kan inträffa så ofta som en gång var tionde sekund utan att belasta onödigt mycket, därför kan denna form av nätverkssökning söka i ett stort datacenter på cirka tre sekunder.

I det här scenariot kan sökningar automatiskt åldras ur nätverket efter till exempel 10 sekunder. Då vet initiativtagaren svaret och det är ingen idé att skvallra vidare om det sökandet.

Skvallerprotokoll har också använts för att uppnå och underhålla distribuerad databaskonsistens eller med andra typer av data i konsekventa tillstånd, räkna antalet noder i ett nätverk av okänd storlek, sprida nyheter robust, organisera noder enligt någon struktureringspolicy, bygga så- kallas överlagringsnätverk , beräkningsaggregat, sortering av noderna i ett nätverk, val av ledare, etc.

Epidemiska algoritmer

Skvallerprotokoll kan användas för att sprida information på ett sätt som liknar det sätt som en virusinfektion sprids i en biologisk population. Faktum är att matematiken för epidemier ofta används för att modellera matematiken för skvallerkommunikation. Termen epidemialgoritm används ibland när man beskriver ett mjukvarusystem där denna typ av skvallerbaserad informationsspridning används.

Se även

  • Skvallerprotokoll är bara en klass bland många klasser av nätverksprotokoll. Se även virtuell synkronisering , distribuerade tillståndsmaskiner , Paxos-algoritm , databastransaktioner . Varje klass innehåller tiotals eller till och med hundratals protokoll, som skiljer sig åt i sina detaljer och prestandaegenskaper men liknande på nivån för de garantier som erbjuds användarna.
  • Vissa skvallerprotokoll ersätter den slumpmässiga kamraturvalsmekanismen med ett mer deterministiskt schema. Till exempel, i NeighbourCast -algoritmen, istället för att prata med slumpmässiga noder, sprids information genom att bara prata med närliggande noder. Det finns ett antal algoritmer som använder liknande idéer. Ett nyckelkrav när man utformar sådana protokoll är att grannuppsättningen spårar ut en expandergraf .
  • Routing
  • Tribler , BitTorrent peer to peer-klient med skvallerprotokoll.

Vidare läsning

Hämtad från " https://en.wikipedia.org/w/index.php?title=Gossip_protocol&oldid=1136398751 "