Det är bra att bevisa att ett genomförande följer en specifikation på ett korrekt sätt. Men även med ett korrekt genomförande, givet ett val, skulle en nod välja att följa det? Detta dokument undersöker hur man skapar distribuerade systemspecifikationer som troget kommer att genomföras i nätverk med rationella noder, så att ingen nod kommer att välja att avvika. Med tanke på en strategisäker centraliserad mekanism, och med tanke på ett nätverk av noder modellerade som har rationella manipulationsfel, tillhandahåller vi en bevisteknik för att etablera incitament-, kommunikations- och algoritmkompatibilitet egenskaper som garanterar att deltagande noder är trogna en föreslagen specifikation. Som en fallstudie använder vi våra metoder för att utöka den strategisäkra interdomain routing mekanism som föreslagits av Feigenbaum, Papadimitriou, Sami, och Shenker (FPSS) [7], definiera en trogen genomförande.  Kategorier och ämnesdeskriptorer Algoritmer, Design, Ekonomi. Distribuerad algoritmisk mekanism Design, Beräkningsmekanism Design, Rationell Manipulation, Algoritm Kompatibilitet, Kommunikation Kompatibilitet, Incitament Kompatibilitet, Misslyckande Modeller, Rationell Misslyckande I detta dokument behandlas hur man skapar bevisligen trogna specifikationer som genomförs på nätverk av rationella noder. I dessa nätverk agerar en nod på egennyttigt sätt för att förbättra resultatet i någon distribuerad mekanism. Det är inte svårt att hitta bevis för rationellt beteende i befintliga distribuerade system. Internetanvändare kan spela sina TCP-inställningar för att få bättre service på bekostnad av andra [27]. Användare fuskar i distribuerade beräkningar för att få tillstånd att göra digitala eller hårda kopior av hela eller delar av detta arbete för personligt eller klassrum användning beviljas utan avgift, förutsatt att kopior inte görs eller distribueras för vinst eller kommersiella fördelar och att kopior bär detta meddelande och den fullständiga citering på första sidan. För att kopiera på annat sätt, för att återpublicera, för att posta på servrar eller för att omfördela till listor, krävs tidigare specifik behörighet och/eller avgift. Detta beteende kan klassificeras som en typ av fel, som bör stå oberoende av andra typer av fel i distribuerade system och är ett tecken på ett underliggande incitament problem i ett systems design när det körs på ett nätverk med rationella noder. Medan traditionella misslyckade modeller övervinns genom att förlita sig på redundans, kan rationell manipulation också övervinnas med designtekniker som problempartitionering, fångst-och-push, och incitament. I ett sådant nätverk kan man uttala ett starkt påstående om troheten i varje nods genomförande. Detta påstående om trohet, som traditionella distribuerade system hävdar (t.ex. säkerhet och livlighet [35], görs med särskilda antaganden om den kunskap som finns tillgänglig för nätverksdeltagarna. Typiska distribuerade system kunskapsantaganden inkluderar nodfel egenskaper: till exempel, en given specifikation kan ange säkerhetsegenskaper under antagandet att inga länkfel kommer att inträffa i nätet. De kunskapsantaganden som är särskilt relevanta för vårt scenario kommer från ekonomi och kallas jämviktskoncept. Detta dokument fokuserar på (och motiverar) användningen av Nash i efterhand (utan samverkan) som ett rimligt kunskapsantagande. Ex post Nash lösning koncept kräver inte noder för att ha någon kunskap om den privata informationen om andra noder, men antar att noder är rationell nytta-maximizers och modell andra deltagare som sådan. När man kan bevisa att en specifikation troget kommer att följas av rationella noder i ett distribuerat nätverk, kan man intyga att systemet är incitament-, kommunikations- och algoritmkompatibelt (IC, CC och AC). Ett sådant system är bevisligen robust mot rationell manipulation. Vi introducerar en allmän nedbrytningssäker teknik, som delar upp en distribuerad algoritm i separata faser, som var och en kan bevisas IC, CC och AC genom att visa att en nod inte kan dra nytta av någon kombination av avvikelser från den specifikation som är relevant för den fasen. För att säkerställa att den ena fasen separeras från den andra certifieras en fas innan den efterföljande fasen inleds.
Författarna till REF övervägde problemet med att skapa distribuerade systemspecifikationer som troget kommer att genomföras i nätverk med rationella (dvs egenintresserade) noder så att ingen nod kommer att välja att avvika från specifikationen.
Specification faithfulness in networks with rational nodes
{'venue': "PODC '04", 'journal': None, 'mag_field_of_study': ['Computer Science']}