Goubault, Éric ;
Lazic, Marijana ;
Ledent, Jérémy ;
Rajsbaum, Sergio
WaitFree 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 inbetween 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 nk 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 = {{WaitFree Solvability of Equality Negation Tasks}},
booktitle = {33rd International Symposium on Distributed Computing (DISC 2019)},
pages = {21:121:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771269},
ISSN = {18688969},
year = {2019},
volume = {146},
editor = {Jukka Suomela},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/11328},
URN = {urn:nbn:de:0030drops113288},
doi = {10.4230/LIPIcs.DISC.2019.21},
annote = {Keywords: Equality negation, distributed computability, combinatorial topology}
}
08.10.2019
Keywords: 

Equality negation, distributed computability, combinatorial topology 
Seminar: 

33rd International Symposium on Distributed Computing (DISC 2019)

Issue date: 

2019 
Date of publication: 

08.10.2019 