De flesta tror att namnbyte är enkelt: välj helt enkelt ett namn slumpmässigt; om mer än en process väljer samma namn, försök igen. Vi lyfter fram de frågor som uppstår när vi försöker genomföra ett sådant system och kastar nytt ljus över läs-skriv komplexiteten i randomiserade namnbyten i en asynkron miljö. I hjärtat av vårt nya perspektiv står ett adaptivt genomförande av ett slumpmässigt test-och-sett objekt, som har poly-logaritmisk steg komplexitet per operation, med hög sannolikhet. Intressant nog är vårt genomförande anonymt, eftersom det inte kräver processidentifierare. Baserat på den här implementeringen presenterar vi två nya randomiserade namnbytesalgoritmer. Den första säkerställer en tight namnrymd av n namn med hjälp av O(n log 4 n) totala steg, med hög sannolikhet. Detta förbättrar avsevärt komplexiteten hos de mest kända namnrymdsoptimala algoritmerna. Den andra algoritmen uppnår ett namnrymd av storlek k (1 + ) med hjälp av O(k log 4 k/ log 2 (1 + )) totala steg, båda med hög sannolikhet, där k är det totala innehållet i utförandet. Det är den första adaptiva randomiserade namngivningsalgoritmen, och den förbättrar befintliga deterministiska lösningar genom att ge en mindre namnrymd, och genom att minska steg komplexitet.
I REF föreslår författarna ett adaptivt införande av test-andset-register med läs- och skrivregister.
Fast Randomized Test-and-Set and Renaming ⋆
{'venue': 'DISC', 'journal': None, 'mag_field_of_study': ['Computer Science']}