För overlay nätverk, förmågan att återhämta sig från en mängd olika problem som medlemskap förändringar eller fel är en viktig del för att bevara sin funktionalitet. Under de senaste åren har olika självstabiliserande overlay-nät föreslagits som har fördelen att kunna återhämta sig från alla olagliga stater. De allra flesta av dessa nät kan dock inte ge några garantier för dess funktionalitet medan återhämtningsprocessen pågår. Vi är särskilt intresserade av sökbarhet, dvs. den funktionalitet som söker meddelanden för en specifik identifierare besvaras framgångsrikt om en nod med den identifieraren finns i nätverket. Vi undersöker overlay nätverk som inte bara är självstabiliserande utan som också ser till att monoton sökbarhet upprätthålls medan återhämtningsprocessen pågår, så länge det inte finns några skadade meddelanden i systemet. Mer exakt, när ett sökmeddelande från node u till en annan nod v levereras framgångsrikt, alla framtida sökmeddelanden från u till v lyckas också. Monotonisk sökbarhet introducerades nyligen i OPODIS 2015, där författarna ger en lösning för en enkel linje topologi. Vi presenterar den första universella strategin för att upprätthålla monoton sökbarhet som är tillämplig på ett brett spektrum av topologier. Som bas för vårt tillvägagångssätt, introducerar vi en uppsättning primitiver för att manipulera overlay nätverk som gör att vi kan upprätthålla sökbarhet och visa hur befintliga protokoll kan omvandlas till att använda teser primitiva. Vi kompletterar detta resultat med ett generiskt sökprotokoll som tillsammans med användningen av våra primitiva garanterar monoton sökbarhet. Som en ytterligare funktion, söker befintliga noder med den generiska sökprotokollet är lika snabbt som att söka en nod med någon annan fast routing protokoll när topologin har stabiliserats. Nyckelord och fraser Monotonic Self-Stabilization, Topological Self-Stabilization, Overlay Networks Detta är den fullständiga versionen av en korrespondent papper som förekommer i DISC 2016 förfaranden. * Detta arbete stöddes delvis av den tyska forskningsstiftelsen (DFG) inom Collaborative Research Center "On-The-Fly Computing" (SFB 901).  Internet har öppnat enorma möjligheter för människor att interagera och utbyta information. Särskilt populära sätt att interagera är peer-to-peer-system och sociala nätverk. För dessa system är det mycket viktigt att de är mycket tillgängliga. Men när väl dessa system blir tillräckligt stora är förändringar och fel inte ett undantag, utan regeln. Därför behövs mekanismer som säkerställer att alla problem som uppstår snabbt repareras och att alla delar av systemet som fortfarande fungerar inte påverkas av reparationsprocessen. Protokoll som kan återhämta sig från godtyckliga stater kallas också självstabiliserande protokoll. Sedan Dijkstras seminaluppsats 1974 [6] har självstabiliserande protokoll undersökts för många klassiska problem, inklusive ledarval, konsensus, matchning, klocksynkronisering och symboliska distributionsproblem. Nyligen har också olika protokoll för självstabiliserande overlay nätverk föreslagits (t.ex., [9, 17, 12, 15] ). För alla dessa protokoll är det dock bara känt att de så småningom konvergerar till den önskade lösningen, men konvergensprocessen är inte nödvändigtvis monoton. Med andra ord, det är inte säkerställt för två punkter i tid t, t med t < t att funktionaliteten i topologin vid tidpunkten t är bättre än funktionaliteten vid tidpunkten t. I detta papper fortsätter vi vår forskning startade i [20] och undersöka protokoll för självstabiliserande overlay nätverk som garanterar monotont bevarande av en egenskap som vi kallar sökbarhet, dvs., när ett sökmeddelande från node u till en annan node v levereras framgångsrikt, alla framtida sökmeddelanden från u till v lyckas också. Sökbarhet är en användbar och naturlig egenskap för ett overlay-nätverk eftersom sökandet efter andra deltagare är en av de vanligaste uppgifterna i verkliga nätverk. Dessutom, ett protokoll som upprätthåller monoton sökbarhet har den enorma fördelen att i varje tillstånd, även om självstabiliseringsprocessen inte har konvergerat ännu, de delar av topologin som redan är i ett legalt tillstånd kan användas för sökning begäran. I stället för att fokusera på en specifik topologi, som gjordes i [20], presenterar vi en strategi som är inriktad på universalitet. Som en bas, presenterar vi en uppsättning primitiva för overlay nätverk underhåll som vi bevisar att de möjliggör monoton sökbarhet. Dessutom ger vi ett generiskt sökprotokoll som, tillsammans med ett protokoll som enbart använder dessa primitiva, garanterar monoton sökbarhet. Dessutom visar vi att befintliga självstabiliserande overlay nätverk protokoll kan omvandlas till att använda våra primitiva. Såvitt vi vet är vi först med att undersöka entonisk sökbarhet som ett försök att utforska att upprätthålla egenskaper bortom de traditionella "tid- och rymdmåtten" under stabiliseringen. Vi tror att frågan om hur man upprätthåller monoton sökbarhet och liknande egenskaper under topologisk stabilisering har stor potential för framtida forskning. Vi anser att ett distribuerat system bestående av en fast uppsättning noder där varje nod har en unik referens och en unik oföränderlig numerisk identifierare (eller kort id). Systemet styrs av ett protokoll som anger de variabler och åtgärder som finns tillgängliga i varje nod. Förutom de protokollbaserade variablerna finns det en systembaserad variabel för varje nod som kallas kanal vars värden är grupper av meddelanden. Vi betecknar kanalen för en nod u som u.Ch och den innehåller alla inkommande meddelanden till u. Dess meddelandekapacitet är obegränsad och meddelanden går aldrig förlorade. En nod kan lägga till ett meddelande till u.Ch om den har en hänvisning till u. Det finns två typer av åtgärder som ett protokoll kan utföra. Den första typen har formen av en standard procedur etikett ( parametrar ): kommando, där etikett är det unika namnet på den åtgärden, parametrar anger parameterlistan för åtgärden, och kommando anger de uttalanden som ska utföras när den åtgärden anropas. Sådana åtgärder kan kallas lokalt (som orsakar deras omedelbara avrättning) och på distans. I själva verket antar vi att varje meddelande måste vara av formuläret etikett ( parametrar ), där etikett anger den åtgärd som ska anropas i den mottagande noden och parametrar innehåller de parametrar som ska skickas till den åtgärd anrop. Alla andra meddelanden ignoreras av noder. Den andra typen har formen etikett : vakt −→ kommando, där etikett och kommando definieras som ovan och vakt är en grund över lokala variabler. Vi kallar en handling vars vakt helt enkelt är en timeout handling. Systemtillståndet är en tilldelning av värden till varje variabel i varje nod och meddelanden till varje kanal. En åtgärd i någon nod u är aktiverad i vissa systemtillstånd om dess vakt utvärderar till sant, eller om det finns ett meddelande i u.Ch begär att ringa det. I det senare fallet, när motsvarande åtgärd genomförs, behandlas meddelandet (i vilket fall det tas bort från u.Ch). En åtgärd är inaktiverad annars. Att ta emot och bearbeta ett meddelande betraktas som ett atomsteg. En beräkning är en oändlig rättvis sekvens av system stater sådan att för varje tillstånd S i, nästa tillstånd S i+1 erhålls genom att utföra en åtgärd som är aktiverad i S i. Detta utesluter överlappningen av verkställandet av åtgärder, d.v.s. verkställandet av åtgärder är atomärt. Vi utgår från ett svagt rättvist verkställande av åtgärder och ett rättvist mottagande av budskapet. Svagt rättvist handlingsutförande innebär att om en handling är möjlig i alla utom ändligt många tillstånd av en beräkning, då denna handling utförs oändligt ofta. Lägg märke till att en punktering av en nod utförs oändligt ofta. Rättvist meddelande mottagande innebär att om en beräkning innehåller ett tillstånd där det finns ett meddelande i en kanal av en nod som möjliggör en åtgärd i den noden, då den åtgärden slutligen utförs med parametrarna i det meddelandet, dvs, meddelandet behandlas så småningom. Förutom dessa rättvisa antaganden, vi sätter inga gränser på meddelandespridning fördröjning eller relativa noder utförande hastigheter, dvs, vi tillåter helt asynkrona beräkningar och icke-FIFO meddelande leverans. En beräkning suffix är en sekvens av beräkningar tillstånd förbi en viss tillstånd av denna beräkning. Med andra ord erhålls suffixet i beräkningen genom att ta bort det ursprungliga tillståndet och ändligt många efterföljande tillstånd. Observera att en beräkningssuffix också är en beräkning. Vi säger att en stat S kan nås från en stat S om det börjar i S finns en sekvens av åtgärder avrättningar sådan att vi hamnar i State S. Vi använder begreppet S < S som en shorthand för att indikera att staten S hände kronologiskt innan S. Vi anser protokoll som inte manipulera interna nodreferenser. Specifikt är ett protokoll jämför-lager-skick om de enda operationer som det utför på nodreferenser är att jämföra dem, lagra dem i lokalt minne och skicka dem i ett meddelande. I ett jämförelse-lager-skick protokoll, en nod kan lära sig en ny referens av en nod endast genom att ta emot den i ett meddelande. Ett jämförelse-lager-skick protokoll kan inte skapa nya referenser. Den kan bara fungera på de hänvisningar som ges till den. Den overlay nätverk av en uppsättning noder bestäms av deras kunskap om varandra. Vi säger att det finns en (riktad) kant från a till b, betecknad av (a, b), om nod en lagrar en hänvisning till b i sitt lokala minne eller har ett meddelande i a.Ch bär referensen till b. I det förra fallet kallas kanten explicit, och i det senare fallet kallas kanten implicit. Meddelanden kan endast skickas via explicita kanter. Observera att meddelande kvitto konverterar en implicit kant till en explicit kant eftersom meddelandet är i det lokala minnet av en nod medan det behandlas. Med N G betecknar vi det riktade nätverket (multi-)graf ges av den explicita och implicita 4 Mot en Universal Approach för monoton sökbarhet kanter. EN G är den del av N G som induceras av endast de explicita kanterna. En svagt ansluten komponent i en riktad graf G är en subgraf av G av maximal storlek så att för två noder u och v i den subgrafen finns en (inte nödvändigtvis riktad) sökväg från u till v. Två noder som inte är i samma svagt anslutna komponent kopplas bort. Vi utgår från att processernas positioner i topologin är inkapslade i deras identifierare och att det finns ett avståndsmått som baseras på processernas identifierare och som kan kontrolleras lokalt. Det vill säga, för en given identifierare ID, kan varje nod u bestämma för varje granne v om v är närmare noden w med id(w) = ID om en sådan nod finns (vi säger också att id(v) är närmare ID än id(u) eller dist(id(v), ID < dist(id(u), ID). För en nod u definierar vi R(u, ID) som den uppsättning som innehåller u och alla processer v för vilken det finns en väg Q från u till v via explicita kanter så att för varje kant (a, b) som passeras i Q det håller att dist(id(b), ID) < dist(id(a), ID). Dessutom, för en uppsättning U, definierar vi R(U, ID) := u-U R (u, ID). I detta dokument är vi särskilt intresserade av sökningsförfrågningar, dvs. Search(v, destID) meddelanden som dirigeras längs EN G enligt ett givet sökprotokoll, där v är avsändaren av meddelandet och destID är identifieraren för en nod som vi letar efter. Vi antar att Sök () förfrågningar initieras lokalt av en (eventuellt användarstyrd) applikation som fungerar på toppen av nätverket. Observera att destID inte behöver vara en id av en befintlig nod w, eftersom det också är möjligt att vi söker efter en nod som inte finns i systemet. Om ett Search(v, destID)-meddelande når en node w med id(w) = destID, lyckas sökningsbegäran; om meddelandet når någon node u med id(u) = destID och inte längre kan vidarebefordras enligt det givna sökprotokollet, misslyckas sökningsbegäran. Ett protokoll är självstabiliserande om det uppfyller följande två egenskaper så länge inga övergående fel uppstår. Konvergens: från och med en godtycklig systemstat garanteras protokollet att komma fram till en legitim stat. Avslutande: Från och med en legitim stat förblir protokollet i legitima stater därefter. Ett självstabiliserande protokoll kan alltså återhämta sig från övergående fel oavsett deras natur. Dessutom behöver inte ett självstabiliserande protokoll initieras eftersom det så småningom börjar bete sig korrekt oavsett sitt ursprungliga tillstånd. I topologisk självstabilisering tillåter vi självstabiliserande protokoll att utföra förändringar i overlay-nätverket N G. Ett legitimt tillstånd kan då inkludera en viss graftopologi eller en familj av graftopologier. Vi är intresserade av självstabiliserande protokoll som stabiliserar sig till statiska topologier, d.v.s. i varje beräkning av protokollet som utgår från ett legitimt tillstånd, EN G förblir densamma, så länge noduppsättningen förblir densamma. I detta dokument fokuserar vi inte på att bygga ett självstabiliserande protokoll för en viss topologi. Istället är vi intresserade av att tillhandahålla ett pålitligt protokoll för att söka i ett brett spektrum av topologier som uppfyller vissa krav. Traditionellt, sökprotokoll för en given topologi krävdes bara för att leverera sökmeddelanden på ett tillförlitligt sätt när ett legitimt tillstånd har uppnåtts. Det är dock inte möjligt att avgöra när en legitim stat har nåtts. Dessutom är sökandet på ett tillförlitligt sätt under stabiliseringsfasen mycket mer involverat. Vi säger att ett självstabiliserande protokoll uppfyller monoton sökbarhet enligt vissa sökprotokoll R om det håller för något par av noder v, w att när en Sök(v, id(w) begäran (som styrs enligt R) initieras vid tidpunkten t lyckas, någon Sök(v, id(w) begäran initieras vid en tidpunkt t > t kommer att lyckas. Vi nämner inte R om det framgår av sammanhanget. Ett protokoll sägs tillfredsställa icke-trivial monoton sökbarhet om (i) det uppfyller C. Scheideler och A. Setzer och T. Strothmann 5 monoton sökbarhet och (ii) varje beräkning av protokollet innehåller en suffix sådan att för varje par av noder v, w, Search(v, id(w) förfrågningar kommer att lyckas om det finns en väg från v till w i målet topologi. Genom hela tidningen kommer vi bara att undersöka icke-trivial monoton sökbarhet. Följaktligen, när vi använder termen monoton sökbarhet i följande, hänvisar vi implicit till icke-trivial monoton sökbarhet. Ett meddelande invariant är en predikat av följande form: Om det finns ett meddelande m i den inkommande kanalen av en nod, då en logisk predikat P måste hålla. Ett protokoll kan ange ett eller flera meddelandeinvarianter. Ett godtyckligt meddelande m i ett system kallas korrumperat om förekomsten av m kränker en eller flera meddelanden invarianter. Ett tillstånd S kallas tillåtligt om det inte finns några skadade meddelanden i S. Vi säger ett (självstabiliserande) protokoll tillåtligt uppfyller ett predikat P om följande två villkor gäller: (i) predikatet är uppfyllt i alla beräkning suffix i protokollet som börjar från tillåtliga tillstånd, och (ii) varje beräkning av protokollet innehåller minst ett tillåtligt tillstånd. Ett protokoll uppfyller villkorslöst en predikat om det uppfyller denna predikat från vilken stat som helst. Följande bevisades i [20]: Följaktligen, för att bevisa monoton sökbarhet för ett protokoll (enligt ett givet sökprotokoll R) är det tillräckligt att visa att: i) i varje beräkning av protokollet som börjar från ett tillåtligt tillstånd, varje tillstånd är tillåtligt, ii) i varje beräkning av protokollet finns det ett tillåtligt tillstånd, och iii) protokollet uppfyller monoton sökbarhet enligt R i varje beräkning som börjar från ett tillåtligt tillstånd. Observera att vi ännu inte har definierat några invarianter och att det är möjligt att välja invarianter så att antalet tillåtliga stater motsvarar antalet legitima stater, där problemet blir trivialt. Men för de invarianter vi tillhandahåller, kan varje initial topologi vara ett godtagbart tillstånd. I synnerhet, så länge inga korrupta meddelanden är initialt i systemet, våra protokoll uppfyller monoton sökbarhet under hela beräkningen. Vi kommer att visa att en bred klass av befintliga självstabiliserande protokoll kan omvandlas för att tillfredsställa monoton sökbarhet. Mer specifikt, Vi kommer att överväga protokoll som uppfyller mdl egenskapen, dvs., för varje åtgärd en av protokollet den innehar att (i) en node u verkställande åtgärd a kommer alltid att hålla en hänvisning till en annan nod v i sitt lokala minne om en kant (u, v) är en del av den slutliga topologin, och (ii) om en node u verkställande åtgärd a i State S beslutar att inte hålla en hänvisning till en annan nod v i sitt lokala minne, varje annan åtgärd av protokollet som utförs av u i ett efterföljande tillstånd kommer att besluta att inte behålla referensen för v, och (iii) en node u verkställande åtgärd en beslutar deterministiskt och uteslutande baserat på dess lokala minne om att skicka och var att skicka referensen för v, (iv) i varje legitimt tillstånd, för varje referens av en node v i ett meddelande m i kanalen av en node u (dvs. för någon implicit kant (u, v)), Det finns fasta cykelfria sökvägar (u = u 1, u 2,. ., u k ) sådan att u i skickar referensen v till u i+1, och u k har en explicit kant (u k, v) (observera att det bara finns en sökväg om referensen aldrig dupliceras), dvs. referensen v vidarebefordras längs fasta vägar tills den slutligen smälter samman med en befintlig referens, och (v) någon stabil kant som kan passeras av sökprotokollet och någon implicit kant som resulterar från en delegering av en explicit kant som kan ha korsats av sökprotokollet, delegeras endast till en nod vars avstånd (i det underliggande avståndet metrisk) är närmare målet än corrent noden. Informellt innebär de två första egenskaperna att protokollet monotont konvergerar till sin önskade topologi, eftersom kanter av topologin alltid hålls och kanter som inte är en del av topologin är undanträngda med tiden. Den sista egenskapen innebär att i legitima stater, kommer alla implicita kanter så småningom gå samman med explicita kanter. Observera att mdl egenskapen är 6 Mot en Universal Approach för Monotonisk Sökbarhet i allmänhet inte en allvarlig begränsning. De flesta befintliga protokoll som stabiliserar sig till statiska topologier uppfyller naturligt denna egenskap (se avsnitt 6). Förutom mdl-egendomen och antagandet att den slutliga topologin är statisk har vi ytterligare ett villkor på topologierna och deras avståndsmått. Det allmänna sökprotokollet vi kommer att använda för att uppnå monoton sökbarhet förutsätter att i målet topologi för varje par av noder u, v inom samma anslutna komponent, det finns en väg av explicita kanter från u till v med egenskapen att varje kant på banan minskar avståndet till v (dvs. för varje kant (a, b) som korsas i sökvägen, dist (id(b), id(v) Observera att många topologier naturligt uppfyller denna egenskap (särskilt när avståndet definieras som antalet noder på en kortaste väg). Såvitt vi vet är vi först med att lösa problemet med att söka på ett tillförlitligt sätt under stabiliseringsfasen i självstabiliserande topologier. Även routing med en låg dilatation är en viktig motivation bakom användningen av overlay topologies, innan detta arbete, kunde man inte lita på routing vägar i sådana topologies 1 : I tidigare metoder, kan det hända att en node u kan skicka ett meddelande till en nod v, medan det inte kan göra det i ett senare tillstånd, bara för att systemet inte har stabiliserats ännu (som inte lokalt kan detekteras av noderna). I vår lösning, när ett sökmeddelande från en nod u har lyckats komma fram till en nod v, varje ytterligare sökmeddelande från u till v kommer också fram till sin destination, oavsett om systemet har helt stabiliserats eller inte. Vi presenterar en universell uppsättning primitiver för att manipulera kanter som protokoll bör använda och en enkel generisk sökprotokoll, som tillsammans uppfyller monoton sökbarhet. Dessutom ger vi en allmän beskrivning av hur en bred klass av självstabiliserande protokoll för overlay nätverk kan omvandlas så att de använder dessa primitiva, vilket tillfredsställer monoton sökbarhet efteråt. Våra resultat i Avsnitt 3 kan vara av oberoende intresse, där vi återinvesterar de grundläggande primitiva för att manipulera kanter infördes [16] och stärka resultaten om universaliteten hos dessa primitiva. Papperet är organiserat enligt följande: Vi ger en kort översikt över relaterade arbeten i Avsnitt 2. I Avsnitt 3, beskriver vi primitiver för manipulerande kanter introducerade i [16] som är basen för våra nya primitiver för sökbarhet. I Avsnitt 4, beskriver vi dessa nya primitiver som man bör använda i ett protokoll för att möjliggöra monoton sökbarhet och visa att konventionella protokoll för självstabilisering av en topologi kan omvandlas till dem som använder de nya primitiva. I Avsnitt 5 presenterar vi ett generiskt sökprotokoll enligt vilket sådana protokoll uppfyller monoton sökbarhet och bevisa dess korrekthet. I avsnitt 6 ger vi exempel på hur vi kan tillämpa våra resultat på befintliga topologier, nämligen listan och SKIP + grafen. En slutsats och framtidsutsikter (avsnitt 7) markerar slutet av pappret.  Idén om självstabilisering i distribuerade datorer introducerades i ett klassiskt papper av E.W. Dijkstra 1974 [6], där han undersökte problemet med självstabilisering i en symbolisk ring. För att återställa vissa nättopologier från något svagt uppkopplat tillstånd började forskarna med enkla linje- och ringnät (t.ex. [21, 19, 10] ). Under åren mer och mer nätverk topologier ansågs, allt från skip listor och hoppa grafer [17, 11], till expanderare [9], hyperträd och dubbelhövdade radix träd [8, 2], och små värld grafer [15]. Även en universell algoritm för topologisk självstabilisering är känd [3]. Under de senaste 20 åren har många strategier undersökts som fokuserar på att upprätthålla säkerhetsegenskaper under konvergensfasen av självstabilisering, t.ex. Snap-stabilisering [4, 5], super-stabilisering [7], säker konvergens [14] och självstabilisering med servicegaranti [13]. Ett protokoll stabiliseras snabbt om det alltid beter sig enligt sin specifikation oberoende av dess ursprungliga konfiguration. Snap-stabilisering har en användarcentrerad säkerhetsfastighet (där de andra tillvägagångssätten är systemcentrerade), d.v.s. Det säkerställer att svaret på en korrekt initierad användarbegäran från protokollet är korrekt. Säker konvergens säkerställer att (1) systemet snabbt konvergerar till en säker konfiguration, och (2) säkerhetsfastigheten förblir nöjd under stabiliseringen under protokollåtgärder. Externa störningar hanteras dock inte på ett säkert sätt. Ett superstabiliserande protokoll garanterar att (1) från och med en legitim konfiguration, en säkerhetsfastighet bevaras efter endast en specifik topologi förändring, och (2) säkerhetsfastigheten underhålls under återhämtning till en legitim konfiguration förutsatt att ingen mer topologi förändring sker under stabiliseringsfasen. Självstabilisering med servicegaranti ger och upprätthåller säkerhetsfastigheten redan före stabilisering, till skillnad från superstabilisering. Närmast vårt arbete är begreppet monoton konvergens av Yamauchi och Tixeuil [22]. En självstabiliserande protokoll är monotont konvergerande om varje förändring som görs av en nod p gör systemet närma sig en legitim stat och om varje nod ändrar sin utgång endast en gång. Författarna undersöker monotont konvergerande protokoll för olika klassiska distribuerade problem (t.ex., ledarval och vertex färgning) och fokuserar på mängden icke-lokal information som behövs för dem. Forskning om monoton sökbarhet inleddes i [20], där författarna bevisade att det är omöjligt att tillfredsställa monoton sökbarhet om skadade meddelanden är närvarande. Dessutom presenterade de ett självstabiliserande protokoll för linjen topologi som kan tillfredsställa monoton sökbarhet.
Med utgångspunkt i den forskningen presenterade samma författare ett universellt tillvägagångssätt för att upprätthålla monoton sökbarhet vid DISC 2016 tillsammans med ett generiskt routingprotokoll som kan tillämpas på ett brett spektrum av topologier REF.
Towards a Universal Approach for Monotonic Searchability in Self-Stabilizing Overlay Networks
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science']}