A Wait-Free Stack
arxiv.org
A Wait-Free Stack
1–10 of 71 posts
Re: A Wait-Free Stack
#2[deleted]
Re: A Wait-Free Stack
#3What is a wait-free stack?
Re: A Wait-Free Stack
#4What is a wait-free stack?
From the introduction:
> In this paper, we describe an algorithm to create a wait-free stack. A concurrent data structure is said to be wait-free if each operation is guaranteed to complete within a finite number of steps. In comparison, the data structure is said to be lock-free if at any point of time, at least one operation is guaranteed to complete in a finite number of steps. Lock-free programs will not have deadlocks but can have starvation, whereas wait-free programs are starvation free.
Re: A Wait-Free Stack
#5What is a wait-free stack?
Wait-freedom is described in the introduction. Quote:
There are three levels of progress guarantees for non-blocking data structures. A concurrent object is:
- obstruction-free if a thread can perform an arbitrary operation on the object in a finite number of steps when it executes in isolation,
- lock-free if some thread performing an arbitrary operation on the object will complete in a finite number of steps, or
- wait-free if every thread can perform an arbitrary operation on the object in a finite number of steps.
Wait-freedom is the strongest progress guarantee; it rules out the possibility of starvation for all threads. Wait-free data structures are particularly desirable for mission critical applications that have real-time constraints, such as those used by cyber-physical systems.
Re: A Wait-Free Stack
#6I love papers but I love it more when their code is in github :) thanks for sharing!
Re: A Wait-Free Stack
#7More discussion on pdf link
Re: A Wait-Free Stack
#8So uhm the top 2 link of HN in the last 5 hours have been about this and while they are highly voted there is very little discussion going. Can someone give some context as to why this is attracting so much (surely deserved) attention? How will this affect us? Is it likely to have a deep effect on general computing performances? In what ways will this be applied? I'm sorry if this are silly questions but I find interesting the lack of discussion going on.
Re: A Wait-Free Stack
#9So uhm the top 2 link of HN in the last 5 hours have been about this and while they are highly voted there is very little discussion going. Can someone give some context as to why this is attracting so much (surely deserved) attention? How will this affect us? Is it likely to have a deep effect on general computing performances? In what ways will this be applied? I'm sorry if this are silly questions but I find inter…
one is a stack, the other a queue, they are different things.
Re: A Wait-Free Stack
#10The first few lines of pop() are:
mytop