August 17, 2010

Concurrency problem :)

Imagine we have a concurrent integer counter, that doesn't support "Increment and read" operation, but supports two separate operations: "Increment" and "Read". Can it be used to generate sequences of unique integer numbers concurrently, and if so, how?

To be precise, I want to write a program involving only such counter for concurrency control, that, being executed concurrently, would produce a sequence of unique numbers in each thread. I.e. I want to ensure no one number is shared among these sequences.

The answer is here (although I'm not absolutely sure it is correct), but I'd suggest you to solve the puzzle by your own first.

Initially it seems the problem is far from being practical - nearly any implementation of concurrent counter supports "Increment and Read" operation. But it looks like we've found one that doesn't :)