文章基本信息

标题：Wait-Freedom vs. Bounded Wait Freedom in Public Data Structures
本地全文：下载
作者：Hagit Brit ; Shlomo Moran
期刊名称：Journal of Universal Computer Science
印刷版ISSN：0948-6968
出版年度：1996
卷号：2
期号：1
页码：2-19
出版社：Graz University of Technology and Know-Center
摘要：In this paper we define and study public data structures, which are concurrent data structures in the shared memory environment, which enable access to an unknown (and possibly infinite) set of identical processes. Specific cases of such data structures (like counting networks and concurrent counters) have been studied recently, and such data structures seem to model concurrent systems like client-server applications, in which the identities of the clients, and sometimes also their number, are not known apriori. Specifically, we study the relation between wait-free and bounded wait-free public data structures - the former guarantees that every operation performed on the data structure always terminates, regardless of the relative speed of the processes, the latter guarantees that every such operation is terminated within a fixed number of steps. We present an example of a public data structure which is wait-free but not bounded wait-free, and then we show that if all the concurrent objects of the data structure are periodic, then wait-freedom implies bounded wait-freedom.