Brief announcement: Anonymous obstruction-free (n, k)-set agreement with n − k + 1 atomic read/write registers

Zohir Bouzid; Michel Raynal; Pierre Sutra

Brief announcement: Anonymous obstruction-free (n, k)-set agreement with n − k + 1 atomic read/write registers

Zohir Bouzid, Michel Raynal, Pierre Sutra

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Abstract

This paper presents an obstruction-free solution to the (n, k)- set agreement problem in an asynchronous anonymous read/write system using solely (n-k+1) registers. We then extend this algorithm into (i) a space-optimal solution for the repeated version of (n, k)-set agreement, and (ii) an x-obstruction-free solution using (n-k +x) atomic registers (with 1 ≤ x ≤ k < n).

Original language	English
Title of host publication	Distributed Computing - 29th International Symposium, DISC 2015, Proceedings
Editors	Yoram Moses
Publisher	Springer Verlag
Pages	669-670
Number of pages	2
ISBN (Print)	9783662486528
Publication status	Published - 1 Jan 2015
Externally published	Yes
Event	29th International Symposium on Distributed Computing, DISC 2015 - Tokyo, Japan Duration: 7 Oct 2015 → 9 Oct 2015

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	9363
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	29th International Symposium on Distributed Computing, DISC 2015
Country/Territory	Japan
City	Tokyo
Period	7/10/15 → 9/10/15

Cite this

Bouzid, Z., Raynal, M., & Sutra, P. (2015). Brief announcement: Anonymous obstruction-free (n, k)-set agreement with n − k + 1 atomic read/write registers. In Y. Moses (Ed.), Distributed Computing - 29th International Symposium, DISC 2015, Proceedings (pp. 669-670). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9363). Springer Verlag.

Bouzid, Zohir ; Raynal, Michel ; Sutra, Pierre. / Brief announcement : Anonymous obstruction-free (n, k)-set agreement with n − k + 1 atomic read/write registers. Distributed Computing - 29th International Symposium, DISC 2015, Proceedings. editor / Yoram Moses. Springer Verlag, 2015. pp. 669-670 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{54c81b0acc4d405782393359de478ee3,

title = "Brief announcement: Anonymous obstruction-free (n, k)-set agreement with n − k + 1 atomic read/write registers",

abstract = "This paper presents an obstruction-free solution to the (n, k)- set agreement problem in an asynchronous anonymous read/write system using solely (n-k+1) registers. We then extend this algorithm into (i) a space-optimal solution for the repeated version of (n, k)-set agreement, and (ii) an x-obstruction-free solution using (n-k +x) atomic registers (with 1 ≤ x ≤ k < n).",

author = "Zohir Bouzid and Michel Raynal and Pierre Sutra",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 2015.; 29th International Symposium on Distributed Computing, DISC 2015 ; Conference date: 07-10-2015 Through 09-10-2015",

year = "2015",

month = jan,

day = "1",

language = "English",

isbn = "9783662486528",

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

publisher = "Springer Verlag",

pages = "669--670",

editor = "Yoram Moses",

booktitle = "Distributed Computing - 29th International Symposium, DISC 2015, Proceedings",

}

Bouzid, Z, Raynal, M & Sutra, P 2015, Brief announcement: Anonymous obstruction-free (n, k)-set agreement with n − k + 1 atomic read/write registers. in Y Moses (ed.), Distributed Computing - 29th International Symposium, DISC 2015, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 9363, Springer Verlag, pp. 669-670, 29th International Symposium on Distributed Computing, DISC 2015, Tokyo, Japan, 7/10/15.

Brief announcement: Anonymous obstruction-free (n, k)-set agreement with n − k + 1 atomic read/write registers. / Bouzid, Zohir; Raynal, Michel; Sutra, Pierre.
Distributed Computing - 29th International Symposium, DISC 2015, Proceedings. ed. / Yoram Moses. Springer Verlag, 2015. p. 669-670 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9363).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Brief announcement

T2 - 29th International Symposium on Distributed Computing, DISC 2015

AU - Bouzid, Zohir

AU - Raynal, Michel

AU - Sutra, Pierre

PY - 2015/1/1

Y1 - 2015/1/1

N2 - This paper presents an obstruction-free solution to the (n, k)- set agreement problem in an asynchronous anonymous read/write system using solely (n-k+1) registers. We then extend this algorithm into (i) a space-optimal solution for the repeated version of (n, k)-set agreement, and (ii) an x-obstruction-free solution using (n-k +x) atomic registers (with 1 ≤ x ≤ k < n).

AB - This paper presents an obstruction-free solution to the (n, k)- set agreement problem in an asynchronous anonymous read/write system using solely (n-k+1) registers. We then extend this algorithm into (i) a space-optimal solution for the repeated version of (n, k)-set agreement, and (ii) an x-obstruction-free solution using (n-k +x) atomic registers (with 1 ≤ x ≤ k < n).

M3 - Conference contribution

AN - SCOPUS:84946101228

SN - 9783662486528

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

SP - 669

EP - 670

BT - Distributed Computing - 29th International Symposium, DISC 2015, Proceedings

A2 - Moses, Yoram

PB - Springer Verlag

Y2 - 7 October 2015 through 9 October 2015

ER -

Bouzid Z, Raynal M, Sutra P. Brief announcement: Anonymous obstruction-free (n, k)-set agreement with n − k + 1 atomic read/write registers. In Moses Y, editor, Distributed Computing - 29th International Symposium, DISC 2015, Proceedings. Springer Verlag. 2015. p. 669-670. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

Brief announcement: Anonymous obstruction-free (n, k)-set agreement with n − k + 1 atomic read/write registers

Abstract

Publication series

Conference

Fingerprint

Cite this