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
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 1 ספט׳ 2016
אירוע19th International Conference on Principles of Distributed Systems, OPODIS 2015 - Rennes, צרפת
משך הזמן: 14 דצמ׳ 201517 דצמ׳ 2015

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

שםLeibniz International Proceedings in Informatics, LIPIcs
כרך46

כנס

כנס19th International Conference on Principles of Distributed Systems, OPODIS 2015
מדינה/אזורצרפת
עירRennes
תקופה14/12/1517/12/15

ASJC Scopus subject areas

  • ???subjectarea.asjc.1700.1712???

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Nontrivial and universal helping for wait-free queues and stacks'. יחד הם יוצרים טביעת אצבע ייחודית.

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