On helping and stacks

Vitaly Aksenov; Petr Kuznetsov; Anatoly Shalyto

doi:10.1007/978-3-030-05529-5_8

On helping and stacks

Vitaly Aksenov
, Petr Kuznetsov
, Anatoly Shalyto

St. Petersburg National Research University of Information Technologies
INRIA-Paris
Université Paris-Saclay

Résultats de recherche: Le chapitre dans un livre, un rapport, une anthologie ou une collection › Contribution à une conférence › Revue par des pairs

Résumé

A concurrent algorithm exhibits helping when one process performs work on behalf of other processes. More formally, helping is observed when the order of some operation in a linearization is fixed by a step of another process. In this paper, we show that no wait-free linearizable implementation of a stack using read, write, compare&swap and fetch&add operations can be help-free, correcting a mistake in an earlier proof by Censor-Hillel et al.

langue originale	Anglais
titre	Networked Systems - 6th International Conference, NETYS 2018, Revised Selected Papers
rédacteurs en chef	Andreas Podelski, François Taïani
Editeur	Springer Verlag
Pages	107-121
Nombre de pages	15
ISBN (imprimé)	9783030055288
Les DOIs	https://doi.org/10.1007/978-3-030-05529-5_8
état	Publié - 1 janv. 2019
Modification externe	Oui
Evénement	6th International Conference on Networked Systems, NETYS 2018 - Essaouira, Maroc Durée: 9 mai 2018 → 11 mai 2018

Série de publications

Nom	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	11028 LNCS
ISSN (imprimé)	0302-9743
ISSN (Electronique)	1611-3349

Une conférence

Une conférence	6th International Conference on Networked Systems, NETYS 2018
Pays/Territoire	Maroc
La ville	Essaouira
période	9/05/18 → 11/05/18

Accès au document

10.1007/978-3-030-05529-5_8

Contient cette citation

Aksenov, V., Kuznetsov, P., & Shalyto, A. (2019). On helping and stacks. Dans A. Podelski, & F. Taïani (eds.), Networked Systems - 6th International Conference, NETYS 2018, Revised Selected Papers (p. 107-121). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol 11028 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-030-05529-5_8

Aksenov, Vitaly ; Kuznetsov, Petr ; Shalyto, Anatoly. / On helping and stacks. Networked Systems - 6th International Conference, NETYS 2018, Revised Selected Papers. Editeur / Andreas Podelski ; François Taïani. Springer Verlag, 2019. p. 107-121 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{ce2d9b6c77de41ec8a6deab9aa164d7b,

title = "On helping and stacks",

abstract = "A concurrent algorithm exhibits helping when one process performs work on behalf of other processes. More formally, helping is observed when the order of some operation in a linearization is fixed by a step of another process. In this paper, we show that no wait-free linearizable implementation of a stack using read, write, compare\&swap and fetch\&add operations can be help-free, correcting a mistake in an earlier proof by Censor-Hillel et al.",

author = "Vitaly Aksenov and Petr Kuznetsov and Anatoly Shalyto",

note = "Publisher Copyright: {\textcopyright} Springer Nature Switzerland AG 2019.; 6th International Conference on Networked Systems, NETYS 2018 ; Conference date: 09-05-2018 Through 11-05-2018",

year = "2019",

month = jan,

day = "1",

doi = "10.1007/978-3-030-05529-5\_8",

language = "English",

isbn = "9783030055288",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "107--121",

editor = "Andreas Podelski and Fran{\c c}ois Ta{\"i}ani",

booktitle = "Networked Systems - 6th International Conference, NETYS 2018, Revised Selected Papers",

}

Aksenov, V, Kuznetsov, P & Shalyto, A 2019, On helping and stacks. Dans A Podelski & F Taïani (eds), Networked Systems - 6th International Conference, NETYS 2018, Revised Selected Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), VOL. 11028 LNCS, Springer Verlag, p. 107-121, 6th International Conference on Networked Systems, NETYS 2018, Essaouira, Maroc, 9/05/18. https://doi.org/10.1007/978-3-030-05529-5_8

On helping and stacks. / Aksenov, Vitaly; Kuznetsov, Petr; Shalyto, Anatoly.
Networked Systems - 6th International Conference, NETYS 2018, Revised Selected Papers. Ed. / Andreas Podelski; François Taïani. Springer Verlag, 2019. p. 107-121 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol 11028 LNCS).

Résultats de recherche: Le chapitre dans un livre, un rapport, une anthologie ou une collection › Contribution à une conférence › Revue par des pairs

TY - GEN

T1 - On helping and stacks

AU - Aksenov, Vitaly

AU - Kuznetsov, Petr

AU - Shalyto, Anatoly

PY - 2019/1/1

Y1 - 2019/1/1

N2 - A concurrent algorithm exhibits helping when one process performs work on behalf of other processes. More formally, helping is observed when the order of some operation in a linearization is fixed by a step of another process. In this paper, we show that no wait-free linearizable implementation of a stack using read, write, compare&swap and fetch&add operations can be help-free, correcting a mistake in an earlier proof by Censor-Hillel et al.

AB - A concurrent algorithm exhibits helping when one process performs work on behalf of other processes. More formally, helping is observed when the order of some operation in a linearization is fixed by a step of another process. In this paper, we show that no wait-free linearizable implementation of a stack using read, write, compare&swap and fetch&add operations can be help-free, correcting a mistake in an earlier proof by Censor-Hillel et al.

U2 - 10.1007/978-3-030-05529-5_8

DO - 10.1007/978-3-030-05529-5_8

M3 - Conference contribution

AN - SCOPUS:85059952036

SN - 9783030055288

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 107

EP - 121

BT - Networked Systems - 6th International Conference, NETYS 2018, Revised Selected Papers

A2 - Podelski, Andreas

A2 - Taïani, François

PB - Springer Verlag

T2 - 6th International Conference on Networked Systems, NETYS 2018

Y2 - 9 May 2018 through 11 May 2018

ER -

Aksenov V, Kuznetsov P, Shalyto A. On helping and stacks. Dans Podelski A, Taïani F, rédacteurs en chef, Networked Systems - 6th International Conference, NETYS 2018, Revised Selected Papers. Springer Verlag. 2019. p. 107-121. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-05529-5_8

On helping and stacks

Résumé

Série de publications

Une conférence

Accès au document

Empreinte digitale

Contient cette citation