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

Простая страница элемента
dc.creatorBrit,Hagit
dc.creatorMoran,Shlomo
dc.date1996
dc.date.accessioned2024-02-06T12:48:09Z
dc.date.available2024-02-06T12:48:09Z
dc.descriptionIn 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.
dc.formattext/html
dc.identifierhttps://doi.org/10.3217/jucs-002-01-0002
dc.identifierhttps://lib.jucs.org/article/27203/
dc.identifier.urihttps://openrepository.mephi.ru/handle/123456789/6918
dc.languageen
dc.publisherJournal of Universal Computer Science
dc.relationinfo:eu-repo/semantics/altIdentifier/eissn/0948-6968
dc.relationinfo:eu-repo/semantics/altIdentifier/pissn/0948-695X
dc.rightsinfo:eu-repo/semantics/openAccess
dc.rightsJ.UCS License
dc.sourceJUCS - Journal of Universal Computer Science 2(1): 2-19
dc.titleWait-Freedom vs. Bounded Wait Freedom in Public Data Structures
dc.typeResearch Article
Файлы
Коллекции
Публикации в журналах НИЯУ МИФИ