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
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 2015
الحدث29th International Symposium on Distributed Computing, DISC 2015 - Tokyo, اليابان
المدة: ٧ أكتوبر ٢٠١٥٩ أكتوبر ٢٠١٥

سلسلة المنشورات

الاسمLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
مستوى الصوت9363


!!Conference29th International Symposium on Distributed Computing, DISC 2015

All Science Journal Classification (ASJC) codes

  • !!Theoretical Computer Science
  • !!Computer Science (all)


أدرس بدقة موضوعات البحث “Modular verification of concurrency-aware linearizability'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا