Proposal: SMP Networking concurrent deque implementation

[Lloyd Parkes <lloyd%must-have-coffee.gen.nz@localhost>]

Hi all,
On the 30th of June I will become voluntarily redundant from my day
job and I really ought to do something more productive than play
Skyrim and Diablo 3 non-stop. I am quite keen on implementing a
concurrent deque because I know someone who has written a paper on how
you can actually do this. I do have a few NetBSD things I want to
finish off before I start the bulk of this work, but I should be able
to start working on this sometime in the second week of July. All of
the hyphenated terms in the rest of this message are technical terms
and they don't mean what you think they mean.

My proposed deliverables are:
    1) An implementation of the deque algorithm described by Herlihy,
Luchangco and Moir (2003).
    2) A contention manager to ensure that the deque is wait-free
rather than obstruction-free.
    3) A test harness to beat the living daylights out of the deque.
    4) A technical report explaining why my implementation should be
considered a faithful implementation of the algorithm.

Note:
The algorithm uses a circular array as the data structure, not the
doubly linked list that many people might use by default. I know of no
lockless concurrent algorithm for doubly linked lists. I haven't
looked for such an algorithm and I will look, but I'm not going to
hold my breath.
The contention manager is much less grand piece of code than the name
would suggest. I'll rely on current NetBSD kernel behaviour as much as
possible and implement some kind of backoff algorithm to prevent
livelock and starvation.
All of the useful papers from Herlihy et al. are paywalled, but Moir
is an Adjunct Professor at my local university, so that shouldn't
present a problem.
The algorithm will require a CAS instruction. For systems that don't
have a CAS instruction, we may have to use some kind of lock. This in
turn may get interesting for platforms that only have a CAS
instruction for some CPU versions, but I won't let that distract me.

Cheers,
Lloyd