Poly-logarithmic adaptive algorithms require unconditional primitives

Hagit Attiya, Arie Fouren

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

תקציר

This paper studies the step complexity of adaptive algorithms using primitives stronger than reads and writes. We first consider unconditional primitives, like fetch&inc, which modify the value of the register to which they are applied, regardless of its current value. Unconditional primitives admit snapshot algorithms with O(log k) step complexity, where k is the total or the point contention. These algorithms combine a renaming algorithm with a mechanism for propagating values so they can be quickly collected. When only conditional primitives, e.g., compare&swap or LL/SC, are used (in addition to reads and writes), we show that any collect algorithm must perform Ω(k) steps, in an execution with total contention k ∈ O(log log n). The lower bound applies for snapshot and renaming, both one-shot and long-lived. Note that there are snapshot algorithms whose step complexity is polylogarithmic in n using only reads and writes, but there are no adaptive algorithms whose step complexity is polylogarithmic in the contention, even when compare&swap and LL/SC are used.

שפה מקוריתאנגלית
כותר פרסום המארח19th International Conference on Principles of Distributed Systems, OPODIS 2015
עורכיםEmmanuelle Anceaume, Christian Cachin, Maria Potop-Butucaru
עמודים36.1-36.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???

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Poly-logarithmic adaptive algorithms require unconditional primitives'. יחד הם יוצרים טביעת אצבע ייחודית.

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