I hjärtat av distribuerad dator ligger det grundläggande resultatet att den nivå av överenskommelse som kan erhållas i en asynkron delad minnesmodell där t-processer kan krascha är exakt t + 1. Med andra ord, en motståndare som kan krascha någon delmängd av storlek som mest t kan förhindra processerna från att komma överens om t-värden. Men hur är det med resten (2 2 n − n) motståndare som kan krascha vissa kombination av processer och inte andra? Med tanke på alla motståndare, vad är dess oenighet makt? d.v.s. den största k för vilken den kan förhindra processer från att komma överens om k-värden. Detta dokument besvarar denna fråga. Vi presenterar en allmän karakterisering av motståndare som gör det möjligt att direkt härleda deras oenighet makt. Vi använder vår karakterisering för att också avsluta frågan om den svagaste feldetektorn för k-set-avtal. Hittills har resultatet uppnåtts i två extrema fall: samförstånd och n − 1-överenskommelse. Vi besvarar denna fråga för alla k och alla motståndare.
I REF presenteras ett exakt sätt att karakterisera motståndare genom att införa begreppet oenighet makt: det största heltal k som motståndaren kan förhindra processer från att komma överens om k värden endast när du använder register; och det visas hur man beräknar oenighet makt av en motståndare.
The Disagreement Power of an Adversary
{'venue': 'DISC', 'journal': None, 'mag_field_of_study': ['Computer Science']}