Linjäriserbarhet är guldstandarden bland algoritmdesigners för att härleda korrektheten hos en distribuerad algoritm med hjälp av implementerade delade objekt från riktigheten av motsvarande algoritm med hjälp av atomversioner av samma objekt. Vi visar att linjärisering inte räcker för detta ändamål när processer kan utnyttja randomisering, och vi diskuterar förekomsten av alternativa korrekta förhållanden. I detta dokument ges följande bidrag: 1. Olika exempel visar att användning av välkända linjäriserbara implementationer av objekt (t.ex. ögonblicksbilder) i stället för atomföremål kan ändra sannolikhetsfördelningen av de resultat som motståndaren kan generera. I vissa fall kan en omedveten motståndare skapa en sannolikhetsfördelning av utfall för en algoritm med implementerade, linjäriserbara objekt, som inte ens en stark motståndare kan generera för samma algoritm med atomföremål. 2. Utgångspunkten är följande: Ett nytt krav på korrekthet för delade objektimplementeringar, som kallas stark linjärisability, definieras. Vi bevisar att en stark motståndare (dvs. en som ser resultatet av varje mynt flip omedelbart) inte får någon ytterligare kraft när atomföremål ersätts av starkt linjära implementationer. I allmänhet räcker det inte med en strikt svagare korrekthet för att säkerställa detta. Vi visar också att stark linearizability är en lokal och kombosable egendom. 3. Vad är det som händer? I motsats till situationen för den starke motståndaren, för en naturlig svagare motståndare (en som inte kan se en processs mynt vända tills dess nästa operation på ett delat objekt) bevisar vi att det inte finns något motsvarande allmänt korrekthetstillstånd. Specifikt, varje linearizable implementation av räknare från atomregister och last-bundna / lager-villkorliga objekt, som uppfyller en naturlig lokalitet egendom, ger nödvändigtvis den svaga motståndaren mer makt än den har med atomräknare.
En viktig konsekvens av våra resultat är att stark linjärisering REF motsvarar förekomsten av en framåtsimulering mot en atomspecifikation.
Linearizable implementations do not suffice for randomized distributed computation
{'venue': "STOC '11", 'journal': None, 'mag_field_of_study': ['Computer Science']}