lineaireerbaarheid

Lineaireerbaarheid is een correctness-property voor gelijktijdige systemen, met name voor gedeelde objecten zoals tellers, wachtrijen en databases. Een systeem is lineaireerbaar als alle bewerkingen op een object lijken te zijn uitgevoerd in een volgorde die een geldige sequentiële geschiedenis oplevert, waarbij elke bewerking plaatsvindt op een enkel tijdstip tussen de aanroep en het antwoord. Die volgorde moet bovendien overeenkomen met de real-time volgorde van niet-overlappende bewerkingen.

Formeel gezien bestaat de geschiedenis uit een totaalorder van bewerkingen die geldig is volgens de specificatie van het object en die real-time consistent is met de feitelijke aanroep-respons volgorde: iedere oproep heeft een tussenpunt tussen aanroep en antwoord waar de bewerking heeft plaatsgevonden.

Lineaireerbaarheid is sterker dan sequentiële consistentie: sequentiële consistentie vereist slechts dat de volgorde van operaties voldoet aan de programmerings- en procesvolgorde, maar lineaireerbaarheid verplicht ook dat niet-overlappende operaties in dezelfde real-time volgorde verschijnen. In gedistribueerde systemen wordt lineaireerbaarheid vaak nagestreefd om voorspelbaar gedrag te garanderen.

Implementaties gebruiken vaak consensus-protocollen zoals Paxos of Raft om een wereldwijde volgorde van operaties op meerdere replicas vast te leggen; dit kan leiden tot hogere latency en complexiteit, maar biedt sterke garanties tegen fouten. Voorbeelden zijn gedeelde tellers, maps en wachtrijen die bij gelijktijdige aanroepen consistent gedrag tonen.

Lineaireerbaarheid is een centraal concept in databases, geheugenconcurrentie en gedistribueerde systemen, en biedt een intuïtieve en sterke garantie voor correct gedrag ondanks gelijktijdigheid.