The computability of relaxed data structures: Queues and stacks as examples

Nir Shavit, Gadi Taubenfeld

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

ملخص

Most concurrent data structures being designed today are versions of known sequential data structures. However, in various cases it makes sense to relax the semantics of traditional concurrent data structures in order to get simpler and possibly more efficient and scalable implementations. For example, when solving the classical producer-consumer problem by implementing a concurrent queue, it might be enough to allow the dequeue operation (by a consumer) to return and remove one of the two oldest values in the queue, and not necessarily the oldest one. We define infinitely many possible relaxations of several traditional data structures: queues, stacks and multisets, and examine their relative computational power.

اللغة الأصليةالإنجليزيّة
عنوان منشور المضيفStructural Information and Communication Complexity - 22nd International Colloquium, SIROCCO 2015, Post-Proceedings
المحررونChristian Scheideler
ناشرSpringer Verlag
الصفحات414-428
عدد الصفحات15
رقم المعيار الدولي للكتب (المطبوع)9783319252575
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 2015
منشور خارجيًانعم
الحدث22nd International Colloquium on Structural Information and Communication Complexity, SIROCCO 2015 - Montserrat, أسبانيا
المدة: ١٤ يوليو ٢٠١٥١٦ يوليو ٢٠١٥

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

الاسمLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
مستوى الصوت9439
رقم المعيار الدولي للدوريات (المطبوع)0302-9743
رقم المعيار الدولي للدوريات (الإلكتروني)1611-3349

!!Conference

!!Conference22nd International Colloquium on Structural Information and Communication Complexity, SIROCCO 2015
الدولة/الإقليمأسبانيا
المدينةMontserrat
المدة١٤/٠٧/١٥١٦/٠٧/١٥

ملاحظة ببليوغرافية

Publisher Copyright:
© Springer International Publishing Switzerland 2015.

بصمة

أدرس بدقة موضوعات البحث “The computability of relaxed data structures: Queues and stacks as examples'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا