Concurrent Data Structures

#1

Post by mdzkhan » Wed, Jul 06, 2011, 5:55 AM UTC

Re: Concurrent Data Structures

#2

Post by GrooveStomp » Wed, Jul 06, 2011, 7:16 AM UTC

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

Re: Concurrent Data Structures

#3

Post by mdzkhan » Wed, Jul 06, 2011, 8:05 AM UTC

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

Re: Concurrent Data Structures

#4

Post by adaszko » Wed, Jul 06, 2011, 8:38 AM UTC

GrooveStomp wrote: post #2

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…

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.

Re: Concurrent Data Structures

#5

Post by TwistedWave » Wed, Jul 06, 2011, 11:17 AM UTC

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

Re: Concurrent Data Structures

#6

Post by signa11 » Wed, Jul 06, 2011, 3:01 PM UTC

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

Re: Concurrent Data Structures

#7

Post by GrooveStomp » Wed, Jul 06, 2011, 6:38 PM UTC

adaszko wrote: post #4

GrooveStomp wrote: post #2

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…

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.

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