Go home now Header Background Image
Submission Procedure
share: |
Follow us
Volume 2 / Issue 1

available in:   PDF (252 kB) PS (67 kB)
Similar Docs BibTeX   Write a comment
Links into Future
DOI:   10.3217/jucs-002-01-0002


Wait-Freedom vs. Bounded Wait Freedom in Public Data Structures

Hagit Brit (Computer Science Department, Technion, Israel)

Shlomo Moran (Computer Science Department, Technion, Israel)

Abstract: 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.