Research On Unbounded Wait-free Universal Constructions

When studying the concurrent computing,the system is distinguished between the following concurrency levels: k-bounded concurrency model,bounded concurrency model and unbounded concurrency model.As the concurrency grows,the set of solvable problems strictly shrinks.On the positive side,problems like collect,snapshot and renaming are proved solvable in the unbounded concurrency model.Meanwhile,whether the universal construction is solvable in the unbounded concurrency model is still an open problem.An universal construction is a general algorithm that convert any sequential object to the implementation of concurrent object,and the conversion should be waitfree.Research on universal construction has 20 years’ history,but all of the research is carried out under bounded concurrency model.So far there is no result about the universal construction under the unbounded concurrency model.On the basis of existing universal constructions,this paper have done the follow work: 1)We propose the first unbounded wait-free universal construction.Algorithm is based on the mechanism of helping.In order to guarantee the helping between processes can be finished in finite number of steps in unbounded concurrency model,we introduced a new queuing method,and the use of fact that the number of active processes during a period time is limited.2)We also prove the correctness of the algorithm in theory.We show that the algorithm is a wait-free one and it is linearizable.Algorithm proposed in this paper is theoretical.Its significance is the existence of universal construction under the unbounded concurrency model.There are still a lot to do about memory management in the future.