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 and objects: queues, stacks, multisets and registers, and examine their relative computational power.

שפה מקוריתאנגלית
עמודים (מ-עד)395-407
מספר עמודים13
כתב עתDistributed Computing
כרך29
מספר גיליון5
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 1 אוק׳ 2016
פורסם באופן חיצוניכן

הערה ביבליוגרפית

Publisher Copyright:
© 2016, Springer-Verlag Berlin Heidelberg.

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'The computability of relaxed data structures: queues and stacks as examples'. יחד הם יוצרים טביעת אצבע ייחודית.

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