Nontrivial and universal helping for wait-free queues and stacks

Hagit Attiya, Armando Castañeda, Danny Hendler

نتاج البحث: فصل من :كتاب / تقرير / مؤتمرمنشور من مؤتمرمراجعة النظراء

ملخص

This paper studies two approaches to formalize helping in wait-free implementations of shared objects. The first approach is based on operation valency, and it allows us to make the important distinction between trivial and nontrivial helping. We show that a wait-free implementation of a queue from common2 objects (e.g., Test&Set) requires nontrivial helping. In contrast, there is a wait-free implementation of a stack from Common2 objects with only trivial helping. This separation might shed light on the difficulty of implementing a queue from Common2 objects. The other approach formalizes the helping mechanism employed by Herlihy's universal waitfree construction and is based on having an operation by one process restrict the possible linearizations of operations by other processes. We show that objects possessing such universal helping can be used to solve consensus.

اللغة الأصليةالإنجليزيّة
عنوان منشور المضيف19th International Conference on Principles of Distributed Systems, OPODIS 2015
المحررونEmmanuelle Anceaume, Christian Cachin, Maria Potop-Butucaru
الصفحات31.1-31.16
رقم المعيار الدولي للكتب (الإلكتروني)9783939897989
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 1 سبتمبر 2016
الحدث19th International Conference on Principles of Distributed Systems, OPODIS 2015 - Rennes, فرنسا
المدة: ١٤ ديسمبر ٢٠١٥١٧ ديسمبر ٢٠١٥

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

الاسمLeibniz International Proceedings in Informatics, LIPIcs
مستوى الصوت46

!!Conference

!!Conference19th International Conference on Principles of Distributed Systems, OPODIS 2015
الدولة/الإقليمفرنسا
المدينةRennes
المدة١٤/١٢/١٥١٧/١٢/١٥

All Science Journal Classification (ASJC) codes

  • !!Software

بصمة

أدرس بدقة موضوعات البحث “Nontrivial and universal helping for wait-free queues and stacks'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا