Abstract
Approximate agreement allows a set of n processes to obtain outputs that are within a specified distance ε > 0 of one another and within the convex hull of the inputs.
When the inputs are real numbers, there is a waitfree sharedmemory approximate agreement algorithm [Moran, 1995] whose step complexity is in O(n log(S/ε)), where S, the spread of the inputs, is the maximal distance between inputs. There is another waitfree algorithm [Schenk, 1995] that avoids the dependence on n and achieves O(log(M/ε)) step complexity where M, the magnitude of the inputs, is the absolute value of the maximal input.
This paper considers whether it is possible to obtain an approximate agreement algorithm whose step complexity depends on neither n nor the magnitude of the inputs, which can be much larger than their spread. On the negative side, we prove that Ω(min{(log M)/(log log M), (√log n)/(log log n)}) is a lower bound on the step complexity of approximate agreement, even when the inputs are real numbers. On the positive side, we prove that a polylogarithmic dependence on n and S/ε can be achieved, by presenting an approximate agreement algorithm with O(log n (log n + log(S/ε))) step complexity. Our algorithm works for multidimensional domains. The step complexity can be further restricted to be in O(min{log n (log n + log (S/ε)), log(M/ε)}) when the inputs are real numbers.
BibTeX  Entry
@InProceedings{attiya_et_al:LIPIcs.OPODIS.2022.6,
author = {Attiya, Hagit and Ellen, Faith},
title = {{The Step Complexity of Multidimensional Approximate Agreement}},
booktitle = {26th International Conference on Principles of Distributed Systems (OPODIS 2022)},
pages = {6:16:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772655},
ISSN = {18688969},
year = {2023},
volume = {253},
editor = {Hillel, Eshcar and Palmieri, Roberto and Rivi\`{e}re, Etienne},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/17626},
URN = {urn:nbn:de:0030drops176261},
doi = {10.4230/LIPIcs.OPODIS.2022.6},
annote = {Keywords: approximate agreement, conflict detection, shared memory, waitfreedom, step complexity}
}
Keywords: 

approximate agreement, conflict detection, shared memory, waitfreedom, step complexity 
Collection: 

26th International Conference on Principles of Distributed Systems (OPODIS 2022) 
Issue Date: 

2023 
Date of publication: 

15.02.2023 