Semantiken av samtidiga datastrukturer ges vanligen av en sekventiell specifikation och ett konsekvent tillstånd. Linjärisering är den mest populära konsistens villkor på grund av dess enkelhet och allmän tillämplighet. Dessutom är linearizability känt för att kräva omfattande synkronisering som kan äventyra prestanda och skalbarhet. För tillämpningar som inte kräver alla garantier som linearizability erbjuder, har den senaste forskningen därför fokuserat på att förbättra prestanda och skalbarhet genom att slappna av semantik av samtidiga datastrukturer. I detta papper presenterar vi lokala linearizability, en avslappnad konsistens villkor som är tillämplig på pooler, köer, stackar, och många andra container-typ samtidiga datastrukturer. Även om linearizability kräver att effekten av varje åtgärd observeras av alla trådar samtidigt, kräver lokal linearizability endast att för varje tråd T, effekterna av dess lokala insättningsåtgärder och effekterna av de avlägsnande åtgärder som tar bort värden som införts av T observeras av alla trådar samtidigt. Lokal linearizability är strikt svagare än linearizability på de flesta containrar inklusive pooler, köer och stackar. Vi presenterar en generisk och enkel metod för att implementera lokalt linjäriserbara datastrukturer med hjälp av befintliga linjäriserbara datastrukturer som byggstenar. I våra experiment visar våra implementationer förbättringar i prestanda och skalbarhet jämfört med de ursprungliga linjäriserbara byggstenarna. Dessutom överträffar våra lokalt linjära implementationer de snabbaste befintliga container-liknande implementationer.
Lokal linearizability har också föreslagits för samtidiga datastrukturer såsom; FIFO köer och Stacks REF.
Local linearizability for concurrent container-type data structures
{'venue': 'CONCUR', 'journal': None, 'mag_field_of_study': ['Computer Science']}