CX: Wait-Free Universal Construction

Re:CX: Wait-Free Universal Construction by gpderetta on Thursday November 07, 2019 @02:34PM (#21476510)

Herlihy[1] has a general transformation to make any arbitrary algorithm wait free, so I think that the claim of novelty is a bit overblown.

[1] The Art of Multiprocessor Programming; I seem to have misplaced my copy so I can't reference chapter and verse.

[ Parent | on HN ]

Re:CX: Wait-Free Universal Construction by thekdude on Thursday November 07, 2019 @07:13PM (#21478876)

I believe you are talking about chapter 6 section 4, page 130 of the Revised First edition

[ Parent | on HN ]

Re:CX: Wait-Free Universal Construction by DSingularity on Thursday November 07, 2019 @06:32PM (#21478524)

Yeah I remember it. Basically, compare-and-swap to enqueue an operation. In contention threads will cooperate to help threads finish operations. With this you bound the blocking and achieve wait-free concurrent operation.

[ Parent | on HN ]