תקציר
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.