2026-07-21T03:13:38Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17626 2024-03-06T11:00:09Z ddc:004 open_access

The Step Complexity of Multidimensional Approximate Agreement Attiya, Hagit Ellen, Faith approximate agreement conflict detection shared memory wait-freedom step complexity 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Hagit Attiya and Faith Ellen 2023 Is Part Of LIPIcs, Volume 253, 26th International Conference on Principles of Distributed Systems (OPODIS 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.OPODIS.2022.6 urn:nbn:de:0030-drops-176261 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2022.6 eng https://creativecommons.org/licenses/by/4.0/legalcode