Make sure you check out Appendix A at the end of the paper (Asymptotic Worst-Case Time Complexity), in case you imagined the name "stack" implies constant-time push/pop performance. This data structure is only a "stack" in the sense that it provides last-in-first-out access.
Is it possible for a contended concurrent stack accessed by an arbitrary number of threads to have guaranteed constant-time operations? I wouldn't think that was a realistic expectation.
A lock-based stack can be O(M) in number of threads accessing it. Judging by the abstract (haven't read the paper) this is O(N) in the size of the stack.
"in terms of the number of concurrent threads in the system (N), the actual size of the stack(S) and the parameter W ... as soon as W consecutive nodes get marked ... the worst case time complexity of the pop operation is O(NWS)"
