License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.OPODIS.2022.6
URN: urn:nbn:de:0030-drops-176261
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/17626/
Attiya, Hagit ;
Ellen, Faith
The Step Complexity of Multidimensional Approximate Agreement
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 wait-free shared-memory 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 wait-free 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:1--6:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-265-5},
ISSN = {1868-8969},
year = {2023},
volume = {253},
editor = {Hillel, Eshcar and Palmieri, Roberto and Rivi\`{e}re, Etienne},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/17626},
URN = {urn:nbn:de:0030-drops-176261},
doi = {10.4230/LIPIcs.OPODIS.2022.6},
annote = {Keywords: approximate agreement, conflict detection, shared memory, wait-freedom, step complexity}
}
|
Keywords: |
|
approximate agreement, conflict detection, shared memory, wait-freedom, step complexity |
|
Collection: |
|
26th International Conference on Principles of Distributed Systems (OPODIS 2022) |
|
Issue Date: |
|
2023 |
|
Date of publication: |
|
15.02.2023 |
