Modular verification of concurrency-aware linearizability

Nir Hemed, Noam Rinetzky, Viktor Vafeiadis

פרסום מחקרי: פרק בספר / בדוח / בכנספרסום בספר כנסביקורת עמיתים


Linearizability is the de facto correctness condition for concurrent objects. Informally, linearizable objects provide the illusion that each operation takes effect instantaneously at a unique point in time between its invocation and response. Hence, by design, linearizability cannot describe behaviors of concurrency-aware concurrent objects (CAobjects), objects in which several overlapping operations “seem to take effect simultaneously”. In this paper, we introduce concurrency-aware linearizability (CAL), a generalized notion of linearizability which allows to formally describe the behavior of CA-objects. Based on CAL, we develop a thread- and procedure-modular verification technique for reasoning about CA-objects and their clients. Using our new technique, we present the first proof of linearizability of the elimination stack of Hendler et al. [10] in which the stack’s elimination subcomponent, which is a general-purpose CA-object, is specified and verified independently of its particular usage by the stack.

שפה מקוריתאנגלית
כותר פרסום המארחDistributed Computing - 29th International Symposium, DISC 2015, Proceedings
עורכיםYoram Moses
מספר עמודים17
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 2015
אירוע29th International Symposium on Distributed Computing, DISC 2015 - Tokyo, יפן
משך הזמן: 7 אוק׳ 20159 אוק׳ 2015

סדרות פרסומים

שםLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)


כנס29th International Symposium on Distributed Computing, DISC 2015

ASJC Scopus subject areas

  • ???subjectarea.asjc.2600.2614???
  • ???subjectarea.asjc.1700???

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Modular verification of concurrency-aware linearizability'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי