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
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 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

بصمة

أدرس بدقة موضوعات البحث “Poly-logarithmic adaptive algorithms require unconditional primitives'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا