License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.DISC.2019.21
URN: urn:nbn:de:0030-drops-113288
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11328/
Goubault, Éric ;
Lazic, Marijana ;
Ledent, Jérémy ;
Rajsbaum, Sergio
Wait-Free Solvability of Equality Negation Tasks
Abstract
We introduce a family of tasks for n processes, as a generalization of the two process equality negation task of Lo and Hadzilacos (SICOMP 2000). Each process starts the computation with a private input value taken from a finite set of possible inputs. After communicating with the other processes using immediate snapshots, the process must decide on a binary output value, 0 or 1. The specification of the task is the following: in an execution, if the set of input values is large enough, the processes should agree on the same output; if the set of inputs is small enough, the processes should disagree; and in-between these two cases, any output is allowed. Formally, this specification depends on two threshold parameters k and l, with k<l, indicating when the cardinality of the set of inputs becomes "small" or "large", respectively. We study the solvability of this task depending on those two parameters. First, we show that the task is solvable whenever k+2 <= l. For the remaining cases (l = k+1), we use various combinatorial topology techniques to obtain two impossibility results: the task is unsolvable if either k <= n/2 or n-k is odd. The remaining cases are still open.
BibTeX - Entry
@InProceedings{goubault_et_al:LIPIcs:2019:11328,
author = {{\'E}ric Goubault and Marijana Lazic and J{\'e}r{\'e}my Ledent and Sergio Rajsbaum},
title = {{Wait-Free Solvability of Equality Negation Tasks}},
booktitle = {33rd International Symposium on Distributed Computing (DISC 2019)},
pages = {21:1--21:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-126-9},
ISSN = {1868-8969},
year = {2019},
volume = {146},
editor = {Jukka Suomela},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/11328},
URN = {urn:nbn:de:0030-drops-113288},
doi = {10.4230/LIPIcs.DISC.2019.21},
annote = {Keywords: Equality negation, distributed computability, combinatorial topology}
}
|
Keywords: |
|
Equality negation, distributed computability, combinatorial topology |
|
Collection: |
|
33rd International Symposium on Distributed Computing (DISC 2019) |
|
Issue Date: |
|
2019 |
|
Date of publication: |
|
08.10.2019 |
