En distribuerad uppgift T på n-processorer är ett in-/utmatningsförhållande mellan en samling processorers in- och utgångar. Medan alla uppgifter är lösbara om ingen processor någonsin kan krascha, FLP resultatet avslöjade att möjligheten av ett misslyckande bara en enda processor utesluter en lösning på uppgiften att samförstånd. Det är ett samförstånd som inte är entydigt. Ändå är vissa icke-triviala uppgifter väntefria lösbara, d.v.s. n − 1- resilientt. Vilka uppgifter kan lösas om som mest t < n processorer kan krascha? Det vill säga. Vad är det för uppgifter som går att lösa? Herlihy-Shavit-tillståndet karakteriserar väntefri löslighet, d.v.s. när t = n − 1. Den Borowsky-Gafni (BG) simulering utvidgar denna karakterisering till t-resilient fall för fallet "färglösa" uppgifter - uppgifter som samförstånd där en processor kan anta utgången av någon annan processor. Det gör det genom att minska frågorna om t-resilient löslighet, till en fråga om vänta-fri löslighet. Den senare frågan har karakteriserats. I detta dokument ändrar vi BG-simuleringen för att resultera i Extended-BG-simuleringen, en förlängning som ger en fullständig karakterisering av t-resilient löslighet: En uppgift T på n processorer är lösbar t-resilient iff alla uppgifter T på t + 1 simulatorer s0,. .., St skapas så här är vänta-fri lösbar. Simulator si ges en ingång av processorn pi samt indata till en uppsättning processorer av storlek n − (t + 1) med ids högre än i. Simulator si utgångar för pi samt för en (eventuellt annorlunda) uppsättning processorer av storlek n − (t + 1) med ids högre än i. Input / output av t + 1 simulatorer måste vara en projektion av en enda original input / output tuple-pair i T. Vi visar den bekvämlighet som karakteriseringen ger, på två sätt. Först bevisar vi ett nytt ekvivalensresultat: Vi visar att n-processer kan lösa t-resiliently svag omnaming med n + (t + 1) − 2 namn, där n > 1 och 0 < t < n, iff svag-renaming på t + 1 processorer är vänta-fri lösbar med 2t namn. För det andra, vi återger resultatet att lösbarheten av n-processorer uppgifter, t-resiliently, för t > 1 och n > 2, är obeslutbar, genom en enkel minskning till
Kort sagt, den utökade BG-simulering REF går genom att etablera T, en "variant" av en uppgift T definieras på t + 1 simulatorer, där varje simulator ges värden för minst n − t processer i T så att när alla t + 1 simulatorer deltar, varje process i T ges en inmatning.
The extended BG-simulation and the characterization of t-resiliency
{'venue': "STOC '09", 'journal': None, 'mag_field_of_study': ['Computer Science']}