Concurrent Data Structures · shard-db HN Explorer

GrooveStomp 15y ago ↗

Very nice paper; it seems to cover datastructures used for several different algorithms. I've only glanced at it so far, as it is quite long. I noticed in 1.1.5 "Correctness" that it discusses equivalency of locking, sequential non-locking and combining tree methods. This is the bread and butter that I'm personally looking for, but it appears that the paper doesn't do any more than just mention methods that are used for proving correctness and equivalency. Can anyone recommend some good resources that delve into that topic? I'd also love to read about mapping high-level concurrency to low-level locking primitives, and specifically how to prove correctness. Again. :D

adaszko 15y ago ↗

This article is indeed very interesting. I've read somewhere that there's a more recent, extended version of it available via the ACM Digital Library.

For correctness proving, you may look for example in http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.101... . It is constrained to π-calculus though.

GrooveStomp 15y ago ↗

Thanks! I'll take a look at it later on (hopefully today).

mdzkhan 15y ago ↗

Another interesting paper on analyzing concurrent data structures. Seems to be simplified and easy to go with. Implementations included. http://resources.aims.ac.za/archive/2009/viateur.pdf

TwistedWave 15y ago ↗

PDF version available here: http://www.cs.tau.ac.il/~afek/ConcurrentDS-MS04.pdf

signa11 15y ago ↗

nir-shavit's book "The Art of Multiprocessor Programming" is also very very good (imho).

Concurrent Data Structures (cs.tau.ac.il)

6 comments