Vi undersöker förhållandet mellan storleken på id-utrymmet och antalet rationella agenter i ett nätverk under vilket jämvikt i distribuerade algoritmer är möjlig. När antalet agenter i nätverket inte är a-prioriterat, kan en enda agent duplicera för att få en fördel, låtsas vara mer än en agent. När id-utrymmet är begränsat innebär dock varje dubblering en risk för att bli fångad. Genom att jämföra risken mot fördelen, med tanke på ett id-utrymme av storlek L, ger vi en metod för att beräkna den minsta tröskeln t, det antal agenter som krävs i nätverket, så att algoritmen är i jämvikt. Det vill säga, det är det minimala värdet av t sådan att om agenter a-priori vet att n ≥ t då algoritmen är i jämvikt. Vi demonstrerar denna metod genom att tillämpa den på två problem, Leader Val och kunskapsdelning, samt att ge en konstant tids approximation till L 5 av den minimala tröskeln för Leader Val.
Bank, Sulamy och Waserman REF undersökte det fall där id-utrymmet är begränsat och beräknade minimitröskeln för jämvikt.
Reaching Distributed Equilibrium with Limited ID Space
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science']}