Vi ger två nya randomiserade algoritmer för stark namnändring, som båda arbetar mot en adaptiv motståndare i asynkront delat minne. Den första använder upprepad provtagning över en sekvens av matriser av minskande storlek för att tilldela unika namn till var och en av n processer med steg komplexitet O(log 3 n). Den andra omvandlar varje sorteringsnätverk till ett starkt adaptivt namnbytesprotokoll, med en förväntad kostnad som motsvarar sorteringsnätets djup. Med hjälp av ett AKS sorteringsnätverk, ger detta en stark adaptiv namnändringsalgoritm med steg komplexitet O(log k), där k är innehållet i den aktuella körningen. Vi visar att detta är optimalt baserat på en klassisk nedre gräns för Jayanti. Vi visar också att alla sådana starka namnbyte protokoll kan användas för att bygga en monoton-konsistent räknare med logaritmisk steg komplexitet (till priset av att lägga till ett max register) eller en linjäriserbar hämta-och-krement register (till priset av att öka steget komplexitet med en logaritmisk faktor).
I REF ger författarna två nya randomiserade namnbytesalgoritmer som fungerar i närvaro av en adaptiv motståndare.
Optimal-time adaptive strong renaming, with applications to counting
{'venue': "PODC '11", 'journal': None, 'mag_field_of_study': ['Computer Science']}