DROPS

Artifact

Software

DOI: 10.4230/artifacts.24587

Weight reduction

Authors: Anatoliy Zinovyev

Abstract

Cite as

Anatoliy Zinovyev. Weight reduction (Software, Source Code). Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@misc{dagstuhl-artifact-24587,
   title = {{Weight reduction}}, 
   author = {Zinovyev, Anatoliy},
   note = {Software, DARPA under Agreements No. HR00112020021, HR00112020023 and HR001120C0085, swhId: \href{https://archive.softwareheritage.org/swh:1:dir:a48c33feba04bc98c7013c4c88b174f5e461a392;origin=https://github.com/tolikzinovyev/weight-reduction;visit=swh:1:snp:d379c595c3c1a7cf8ed2e52faed4d8656d733f23;anchor=swh:1:rev:f1b5ce44aab9e4809bff67c5c6bff4acf1f82cb1}{\texttt{swh:1:dir:a48c33feba04bc98c7013c4c88b174f5e461a392}} (visited on 2025-10-22)},
   url = {https://github.com/tolikzinovyev/weight-reduction/tree/f1b5ce44aab9e4809bff67c5c6bff4acf1f82cb1},
   doi = {10.4230/artifacts.24587},
}

Document

DOI: 10.4230/LIPIcs.DISC.2025.43

Weight Reduction in Distributed Protocols: New Algorithms and Analysis

Authors: Anatoliy Zinovyev

Published in: LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025)

Abstract

We study the problem of minimizing the total weight of (potentially many) participants of a distributed protocol, a necessary step when the original values are large but the scheme to be deployed scales poorly with the weights. We assume that α fraction of the original weights can be corrupted and we must output new weights with at most β adversarial fraction, for α < β. This problem can be viewed from the prism of electing a small committee that does the heavy work, a powerful tool for making distributed protocols scalable. We solve the variant that requires giving parties potentially multiple seats in the committee and counting each seat towards the cost of the solution. Moreover, we focus on the "deterministic" version of the problem where the computed committee must be secure for any subset of parties that can be corrupted by the adversary; such a committee can be smaller than a randomly sampled one in some cases and is useful when security against adaptive corruptions is desired but parties in the sub-protocol speak multiple times. Presented are new algorithms for the problem as well as analysis of prior work. We give two variants of the algorithm Swiper (PODC 2024), one that significantly improves the running time without sacrificing the quality of the output and the other improving the output for a reasonable increase in the running time. We prove, however, that all known algorithms, including our two variants of Swiper, have worst case approximation ratio Ω(n). To counter that, we give the first polynomial time algorithm with approximation factor n / log² n and also the first sub-exponential time exact algorithm, practical for some real-world inputs. Of theoretical interest is another polytime algorithm that we present, based on linear programming, whose output is no worse than an optimal solution to the problem with slightly different parameters. We implemented and tested previous and new algorithms, comparing them on the stake distributions of popular proof-of-stake blockchains, and found that our second variant of Swiper computes solutions extremely close to the optimal, confirmed by our exact algorithm.

Cite as

Anatoliy Zinovyev. Weight Reduction in Distributed Protocols: New Algorithms and Analysis. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 43:1-43:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{zinovyev:LIPIcs.DISC.2025.43,
  author =	{Zinovyev, Anatoliy},
  title =	{{Weight Reduction in Distributed Protocols: New Algorithms and Analysis}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{43:1--43:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-402-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{356},
  editor =	{Kowalski, Dariusz R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.43},
  URN =		{urn:nbn:de:0030-drops-248600},
  doi =		{10.4230/LIPIcs.DISC.2025.43},
  annote =	{Keywords: Weight reduction, distributed protocols, weighted cryptography, threshold cryptography, consensus, committee selection, adaptive corruptions, approximation algorithms, linear programming, rounding}
}

Document

DOI: 10.4230/LIPIcs.DISC.2022.37

Space-Stretch Tradeoff in Routing Revisited

Authors: Anatoliy Zinovyev

Published in: LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022)

Abstract

We present several new proofs of lower bounds for the space-stretch tradeoff in labeled network routing. First, we give a new proof of an important result of Cyril Gavoille and Marc Gengler that any routing scheme with stretch < 3 must use Ω(n) bits of space at some node on some network with n vertices, even if port numbers can be changed. Compared to the original proof, our proof is significantly shorter and, we believe, conceptually and technically simpler. A small extension of the proof can show that, in fact, any constant fraction of the n nodes must use Ω(n) bits of space on some graph. Our main contribution is a new result that if port numbers are chosen adversarially, then stretch < 2k+1 implies some node must use Ω(n^(1/k) log n) bits of space on some graph, assuming a girth conjecture by Erdős. We conclude by showing that all known methods of proving a space lower bound in the labeled setting, in fact, require the girth conjecture.

Cite as

Anatoliy Zinovyev. Space-Stretch Tradeoff in Routing Revisited. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 37:1-37:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{zinovyev:LIPIcs.DISC.2022.37,
  author =	{Zinovyev, Anatoliy},
  title =	{{Space-Stretch Tradeoff in Routing Revisited}},
  booktitle =	{36th International Symposium on Distributed Computing (DISC 2022)},
  pages =	{37:1--37:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-255-6},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{246},
  editor =	{Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2022.37},
  URN =		{urn:nbn:de:0030-drops-172281},
  doi =		{10.4230/LIPIcs.DISC.2022.37},
  annote =	{Keywords: Compact routing, labeled network routing, lower bounds}
}

Search Results

Documents authored by Zinovyev, Anatoliy

Weight reduction

Abstract

Cite as

Weight Reduction in Distributed Protocols: New Algorithms and Analysis

Abstract

Cite as

Space-Stretch Tradeoff in Routing Revisited

Abstract

Cite as

Thanks for your feedback!

Could not send message