2026-07-24T21:21:13Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:21253 2024-10-24T07:40:08Z ddc:004 open_access

Sorting in One and Two Rounds Using t-Comparators Gelles, Ran Lotker, Zvi Mallmann-Trenn, Frederik Sorting Steiner-System Round Complexity Deferred Randomness We examine sorting algorithms for n elements whose basic operation is comparing t elements simultaneously (a t-comparator). We focus on algorithms that use only a single round or two rounds - comparisons performed in the second round depend on the outcomes of the first round comparators. Algorithms with a small number of rounds are well-suited to distributed settings in which communication rounds are costly. We design deterministic and randomized algorithms. In the deterministic case, we show an interesting relation to design theory (namely, to 2-Steiner systems), which yields a single-round optimal algorithm for n = t^{2^k} with any k ≥ 1 and a variety of possible values of t. For some values of t, however, no algorithm can reach the optimal (information-theoretic) bound on the number of comparators. For this case (and any other n and t), we show an algorithm that uses at most three times as many comparators as the theoretical bound. We also design a randomized Las-Vegas two-round sorting algorithm for any n and t. Our algorithm uses an asymptotically optimal number of O(max(n^{3/2}/t²,n/t)) comparators, with high probability, i.e., with probability at least 1-1/n. The analysis of this algorithm involves the gradual unveiling of randomness, using a novel technique which we coin the binary tree of deferred randomness. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ran Gelles and Zvi Lotker and Frederik Mallmann-Trenn 2024 Is Part Of LIPIcs, Volume 319, 38th International Symposium on Distributed Computing (DISC 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.DISC.2024.27 urn:nbn:de:0030-drops-212539 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2024.27 eng https://creativecommons.org/licenses/by/4.0/legalcode