19 Search Results for "Cohen, Shir"

Document
DOI: 10.4230/LIPIcs.ITCS.2026.36
Beyond 2-Edge-Connectivity: Algorithms and Impossibility for Content-Oblivious Leader Election

Authors: Yi-Jun Chang, Lyuting Chen, and Haoran Zhou

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
The content-oblivious model, introduced by Censor-Hillel, Cohen, Gelles, and Sela (PODC 2022; Distributed Computing 2023), captures an extremely weak form of communication where nodes can only send asynchronous, content-less pulses. They showed that in 2-edge-connected networks, any distributed algorithm can be simulated in the content-oblivious model, provided that a unique leader is designated a priori. Subsequent works of Frei, Gelles, Ghazy, and Nolin (DISC 2024) and Chalopin et al. (DISC 2025) developed content-oblivious leader election algorithms, first for unoriented rings and then for general 2-edge-connected graphs. These results establish that all graph problems are solvable in content-oblivious, 2-edge-connected networks. Much less is known about networks that are not 2-edge-connected. Censor-Hillel, Cohen, Gelles, and Sela showed that no non-constant function f(x,y) can be computed correctly by two parties using content-oblivious communication over a single edge, where one party holds x and the other holds y. This seemingly ruled out many natural graph problems on non-2-edge-connected graphs. In this work, we show that, with the knowledge of network topology G, leader election is possible in a wide range of graphs. Our main contributions are as follows: Impossibility: Graphs symmetric about an edge admit no randomized terminating leader election algorithm, even when nodes have unique identifiers and full knowledge of G. Leader election algorithms: Trees that are not symmetric about any edge admit a quiescently terminating leader election algorithm with topology knowledge, even in anonymous networks, using O(n²) messages, where n is the number of nodes. Moreover, even-diameter trees admit a terminating leader election given only the knowledge of the network diameter D = 2r, with message complexity O(nr). Necessity of topology knowledge: In the family of graphs 𝒢 = {P₃, P₅}, both the 3-path P₃ and the 5-path P₅ admit a quiescently terminating leader election if nodes know the topology exactly. However, if nodes only know that the underlying topology belongs to 𝒢, then terminating leader election is impossible.
Cite as

Yi-Jun Chang, Lyuting Chen, and Haoran Zhou. Beyond 2-Edge-Connectivity: Algorithms and Impossibility for Content-Oblivious Leader Election. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 36:1-36:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{chang_et_al:LIPIcs.ITCS.2026.36,
  author =	{Chang, Yi-Jun and Chen, Lyuting and Zhou, Haoran},
  title =	{{Beyond 2-Edge-Connectivity: Algorithms and Impossibility for Content-Oblivious Leader Election}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{36:1--36:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.36},
  URN =		{urn:nbn:de:0030-drops-253239},
  doi =		{10.4230/LIPIcs.ITCS.2026.36},
  annote =	{Keywords: Asynchronous model, fault tolerance, quiescent termination}
}
Document
DOI: 10.4230/LIPIcs.DISC.2025.6
Hierarchical Consensus: Scalability Through Optimism and Weak Liveness

Authors: Pedro Antonino, Antoine Durand, and A. W. Roscoe

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

Abstract
Scalability is a central concern of Byzantine Fault Tolerant (BFT) distributed protocols. The ubiquitous approach to work around the well-known Dolev-Reischuk Ω(n²) communication complexity lower bound is to use a random selection process to draw a hopefully small committee from a population of agents to run the communication-heavy protocol. We propose a notion of hierarchical consensus that combines two sub-protocols: an optimistic primary sub-protocol that can tolerate less than 1/2 failures and a fallback secondary protocol that can tolerate less than 1/3 failures; we achieve the higher failure threshold by requiring a weaker notion of liveness for the primary. This distinction between the level of fault tolerance between primary and secondary is reflected in the size of committees implementing these protocols. For a population of agents with close to 2/3 of honest agents, we need to select a committee with hundreds of agents to reach the level of tolerance expected for the primary, whereas we need thousands to reach the level expected for the secondary with a very small probability of error ε. Our hierarchical construct is such that if the primary comes to a decision, it can simply propagate it to the secondary protocol, so it does not need to properly engage in an agreement protocol independently. Our architecture is flexible and allows us to use our technique for most protocols that are based on random sampling. By studying hierarchical protocols, we discovered new theoretical results of independent interest. Specifically, the ability to handover from a primary protocol requires a new Justifiability property that allows agents to pre-decide on a value, such that if the protocol decides, it must be on that pre-decided value.
Cite as

Pedro Antonino, Antoine Durand, and A. W. Roscoe. Hierarchical Consensus: Scalability Through Optimism and Weak Liveness. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 6:1-6:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{antonino_et_al:LIPIcs.DISC.2025.6,
  author =	{Antonino, Pedro and Durand, Antoine and Roscoe, A. W.},
  title =	{{Hierarchical Consensus: Scalability Through Optimism and Weak Liveness}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{6:1--6:20},
  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.6},
  URN =		{urn:nbn:de:0030-drops-248232},
  doi =		{10.4230/LIPIcs.DISC.2025.6},
  annote =	{Keywords: Hierarchical, Handover, Justifiability, Consensus, Distributed Systems, Blockchain}
}
Document
DOI: 10.4230/LIPIcs.DISC.2025.21
Content-Oblivious Leader Election in 2-Edge-Connected Networks

Authors: Jérémie Chalopin, Yi-Jun Chang, Lyuting Chen, Giuseppe A. Di Luna, and Haoran Zhou

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

Abstract
Censor-Hillel, Cohen, Gelles, and Sela (PODC 2022 & Distributed Computing 2023) studied fully-defective asynchronous networks, where communication channels may arbitrarily corrupt messages. The model is equivalent to content-oblivious computation, where nodes communicate solely via pulses. They showed that if the network is 2-edge-connected, then any algorithm for a noiseless setting can be simulated in the fully-defective setting; otherwise, no non-trivial computation is possible in the fully-defective setting. However, their simulation requires a predesignated leader, which they conjectured to be necessary for any non-trivial content-oblivious task. Recently, Frei, Gelles, Ghazy, and Nolin (DISC 2024) refuted this conjecture for the special case of oriented ring topology. They designed two asynchronous content-oblivious leader election algorithms with message complexity O(n ⋅ ID_{max}), where n is the number of nodes and ID_{max} is the maximum ID. The first algorithm stabilizes in unoriented rings without termination detection. The second algorithm quiescently terminates in oriented rings, thus enabling the execution of the simulation algorithm after leader election. In this work, we present two results: General 2-edge-connected topologies: First, we show an asynchronous content-oblivious leader election algorithm that quiescently terminates in any 2-edge-connected network with message complexity O(m ⋅ N ⋅ ID_{min}), where m is the number of edges, N is a known upper bound on the number of nodes, and ID_{min} is the smallest ID. Combined with the above simulation, this result shows that whenever a size bound N is known, any noiseless algorithm can be simulated in the fully-defective model without a preselected leader, fully refuting the conjecture. Unoriented rings: We then show that the knowledge of N can be dropped in unoriented ring topologies by presenting a quiescently terminating election algorithm with message complexity O(n ⋅ ID_{max}) that matches the previous bound. Consequently, this result constitutes a strict improvement over the previous state of the art and shows that, on rings, fully-defective and noiseless communication are computationally equivalent, with no additional assumptions.
Cite as

Jérémie Chalopin, Yi-Jun Chang, Lyuting Chen, Giuseppe A. Di Luna, and Haoran Zhou. Content-Oblivious Leader Election in 2-Edge-Connected Networks. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 21:1-21:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{chalopin_et_al:LIPIcs.DISC.2025.21,
  author =	{Chalopin, J\'{e}r\'{e}mie and Chang, Yi-Jun and Chen, Lyuting and Di Luna, Giuseppe A. and Zhou, Haoran},
  title =	{{Content-Oblivious Leader Election in 2-Edge-Connected Networks}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{21:1--21:22},
  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.21},
  URN =		{urn:nbn:de:0030-drops-248385},
  doi =		{10.4230/LIPIcs.DISC.2025.21},
  annote =	{Keywords: Asynchronous model, fault tolerance, quiescent termination}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2025.45
Brief Announcement: DAGs for the Masses

Authors: Michael Anoprenko, Andrei Tonkikh, Alexander Spiegelman, and Petr Kuznetsov

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

Abstract
A recent approach to building consensus protocols on top of Directed Acyclic Graphs (DAGs) shows much promise due to its simplicity and stable throughput. However, as each node in the DAG typically includes a linear number of references to the nodes in the previous round, prior DAG protocols only scale up to a certain point when the overhead of maintaining the graph becomes the bottleneck. To enable large-scale deployments of DAG-based protocols, we propose a sparse DAG architecture, where each node includes only a constant number of references to random nodes in the previous round. We present a sparse version of Bullshark - one of the most prominent DAG-based consensus protocols - and demonstrate its improved scalability. Remarkably, unlike other protocols that use random sampling to reduce communication complexity, we manage to avoid sacrificing resilience: the protocol can tolerate up to f < n/3 Byzantine faults (where n is the number of participants), same as its less scalable deterministic counterpart. The proposed "sparse" methodology can be applied to any protocol that maintains disseminated system updates and causal relations between them in a graph-like structure. Our simulations show that the considerable reduction of transmitted metadata in sparse DAGs results in more efficient network utilization and better scalability.
Cite as

Michael Anoprenko, Andrei Tonkikh, Alexander Spiegelman, and Petr Kuznetsov. Brief Announcement: DAGs for the Masses. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 45:1-45:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{anoprenko_et_al:LIPIcs.DISC.2025.45,
  author =	{Anoprenko, Michael and Tonkikh, Andrei and Spiegelman, Alexander and Kuznetsov, Petr},
  title =	{{Brief Announcement: DAGs for the Masses}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{45:1--45:7},
  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.45},
  URN =		{urn:nbn:de:0030-drops-248617},
  doi =		{10.4230/LIPIcs.DISC.2025.45},
  annote =	{Keywords: Consensus, Atomic Broadcast, Byzantine Fault Tolerance, DAGs, Scalability, Sampling}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2025.52
Brief Announcement: From Few to Many Faults: Adaptive Byzantine Agreement with Optimal Communication

Authors: Andrei Constantinescu, Marc Dufay, Anton Paramonov, and Roger Wattenhofer

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

Abstract
We study the problem of Strong Byzantine Agreement and establish tight upper and lower bounds on communication complexity, parameterized by the actual number of Byzantine faults. Specifically, for a system of n parties tolerating up to t Byzantine faults, out of which only f ≤ t are actually faulty, we obtain the following results: In the partially synchronous setting, we present the first Byzantine Agreement protocol that achieves adaptive communication complexity of 𝒪(n + t ⋅ f) words, which is asymptotically optimal. Our protocol has an optimal resilience of t < n/3. In the asynchronous setting, we prove a lower bound of Ω(n + t²) on the expected number of messages, and design an almost matching protocol with an optimal resilience that solves agreement with 𝒪((n + t²)⋅ log n) words. Our main technical contribution in the asynchronous setting is the utilization of a bipartite expander graph that allows for low-cost information dissemination.
Cite as

Andrei Constantinescu, Marc Dufay, Anton Paramonov, and Roger Wattenhofer. Brief Announcement: From Few to Many Faults: Adaptive Byzantine Agreement with Optimal Communication. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 52:1-52:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{constantinescu_et_al:LIPIcs.DISC.2025.52,
  author =	{Constantinescu, Andrei and Dufay, Marc and Paramonov, Anton and Wattenhofer, Roger},
  title =	{{Brief Announcement: From Few to Many Faults: Adaptive Byzantine Agreement with Optimal Communication}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{52:1--52:8},
  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.52},
  URN =		{urn:nbn:de:0030-drops-248680},
  doi =		{10.4230/LIPIcs.DISC.2025.52},
  annote =	{Keywords: Byzantine Agreement, Communication Complexity, Adaptive Communication Complexity, Resilience}
}
Document
DOI: 10.4230/LIPIcs.AFT.2025.14
Optimistic Message Dissemination

Authors: Chen-Da Liu-Zhang, Christian Matt, and Søren Eller Thomsen

Published in: LIPIcs, Volume 354, 7th Conference on Advances in Financial Technologies (AFT 2025)

Abstract
Message dissemination is a fundamental building block in distributed systems and guarantees that any message sent eventually reaches all parties. State of the art provably secure protocols for disseminating messages have a per-party communication complexity that is linear in the inverse of the fraction of parties that are guaranteed to be honest in the worst case. Unfortunately, this per-party communication complexity arises even in cases where the actual fraction of parties that behave honestly is close to 1. In this paper, we propose an optimistic message dissemination protocol that adopts to the actual conditions in which it is deployed, with optimal worst-case per-party communication complexity. Our protocol cuts the complexity of prior provably secure protocols for 49% worst-case corruption almost in half under optimistic conditions and allows practitioners to combine efficient heuristics with secure fallback mechanisms.
Cite as

Chen-Da Liu-Zhang, Christian Matt, and Søren Eller Thomsen. Optimistic Message Dissemination. In 7th Conference on Advances in Financial Technologies (AFT 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 354, pp. 14:1-14:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{liuzhang_et_al:LIPIcs.AFT.2025.14,
  author =	{Liu-Zhang, Chen-Da and Matt, Christian and Thomsen, S{\o}ren Eller},
  title =	{{Optimistic Message Dissemination}},
  booktitle =	{7th Conference on Advances in Financial Technologies (AFT 2025)},
  pages =	{14:1--14:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-400-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{354},
  editor =	{Avarikioti, Zeta and Christin, Nicolas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AFT.2025.14},
  URN =		{urn:nbn:de:0030-drops-247332},
  doi =		{10.4230/LIPIcs.AFT.2025.14},
  annote =	{Keywords: flooding, message dissemination, optimistic}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.49
Pseudorandomness of Expander Walks via Fourier Analysis on Groups

Authors: Fernando Granha Jeronimo, Tushant Mittal, and Sourya Roy

Published in: LIPIcs, Volume 353, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)

Abstract
A long line of work has studied the pseudorandomness properties of walks on expander graphs. A central goal is to measure how closely the distribution over n-length walks on an expander approximates the uniform distribution of n-independent elements. One approach to do so is to label the vertices of an expander with elements from an alphabet Σ, and study closeness of the mean of functions over Σⁿ, under these two distributions. We say expander walks ε-fool a function if the expander walk mean is ε-close to the true mean. There has been a sequence of works studying this question for various functions, such as the XOR function, the AND function, etc. We show that: - The class of symmetric functions is O(|Σ|λ)-fooled by expander walks over any generic λ-expander, and any alphabet Σ . This generalizes the result of Cohen, Peri, Ta-Shma [STOC'21] which analyzes it for |Σ| = 2, and exponentially improves the previous bound of O(|Σ|^O(|Σ|) λ), by Golowich and Vadhan [CCC'22]. Moreover, if the expander is a Cayley graph over ℤ_|Σ|, we get a further improved bound of O(√{|Σ|} λ). Morever, when Σ is a finite group G, we show the following for functions over Gⁿ: - The class of symmetric class functions is O({√|G|}/D λ}-fooled by expander walks over "structured" λ-expanders, if G is D-quasirandom. - We show a lower bound of Ω(λ) for symmetric functions for any finite group G (even for "structured" λ-expanders). - We study the Fourier spectrum of a class of non-symmetric functions arising from word maps, and show that they are exponentially fooled by expander walks. Our proof employs Fourier analysis over general groups, which contrasts with earlier works that have studied either the case of ℤ₂ or ℤ. This enables us to get quantitatively better bounds even for unstructured sets.
Cite as

Fernando Granha Jeronimo, Tushant Mittal, and Sourya Roy. Pseudorandomness of Expander Walks via Fourier Analysis on Groups. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 49:1-49:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{jeronimo_et_al:LIPIcs.APPROX/RANDOM.2025.49,
  author =	{Jeronimo, Fernando Granha and Mittal, Tushant and Roy, Sourya},
  title =	{{Pseudorandomness of Expander Walks via Fourier Analysis on Groups}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{49:1--49:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-397-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{353},
  editor =	{Ene, Alina and Chattopadhyay, Eshan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.49},
  URN =		{urn:nbn:de:0030-drops-244157},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.49},
  annote =	{Keywords: Expander graphs, pseudorandomness}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2025.35
Unraveling Universally Closest Refinements via Symmetric Density Decomposition and Fisher Market Equilibrium

Authors: T-H. Hubert Chan and Quan Xue

Published in: LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)

Abstract
We investigate the closest distribution refinements problem, which involves a vertex-weighted bipartite graph as input, where the vertex weights on each side sum to 1 and represent a probability distribution. A refinement of one side’s distribution is an edge distribution that corresponds to distributing the weight of each vertex from that side to its incident edges. The objective is to identify a pair of distribution refinements for both sides of the bipartite graph such that the two edge distributions are as close as possible with respect to a specific divergence notion. This problem is a generalization of transportation, in which the special case occurs when the two closest distributions are identical. The problem has recently emerged in the context of composing differentially oblivious mechanisms. Our main result demonstrates that a universal refinement pair exists, which is simultaneously closest under all divergence notions that satisfy the data processing inequality. Since differential obliviousness can be examined using various divergence notions, such a universally closest refinement pair offers a powerful tool in relation to such applications. We discover that this pair can be achieved via locally verifiable optimality conditions. Specifically, we observe that it is equivalent to the following problems, which have been traditionally studied in distinct research communities: (1) hypergraph density decomposition, and (2) symmetric Fisher Market equilibrium. We adopt a symmetric perspective of hypergraph density decomposition, in which hyperedges and nodes play equivalent roles. This symmetric decomposition serves as a tool for deriving precise characterizations of optimal solutions for other problems and enables the application of algorithms from one problem to another. This connection allows existing algorithms for computing or approximating the Fisher market equilibrium to be adapted for all the aforementioned problems. For example, this approach allows the well-known iterative proportional response process to provide approximations for the corresponding problems with multiplicative error in distributed settings, whereas previously, only absolute error had been achieved in these contexts. Our study contributes to the understanding of various problems within a unified framework, which may serve as a foundation for connecting other problems in the future.
Cite as

T-H. Hubert Chan and Quan Xue. Unraveling Universally Closest Refinements via Symmetric Density Decomposition and Fisher Market Equilibrium. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 35:1-35:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{chan_et_al:LIPIcs.ITCS.2025.35,
  author =	{Chan, T-H. Hubert and Xue, Quan},
  title =	{{Unraveling Universally Closest Refinements via Symmetric Density Decomposition and Fisher Market Equilibrium}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{35:1--35:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-361-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{325},
  editor =	{Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.35},
  URN =		{urn:nbn:de:0030-drops-226633},
  doi =		{10.4230/LIPIcs.ITCS.2025.35},
  annote =	{Keywords: closest distribution refinements, density decomposition, Fisher market equilibrium}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2024.14
Near-Optimal Communication Byzantine Reliable Broadcast Under a Message Adversary

Authors: Timothé Albouy, Davide Frey, Ran Gelles, Carmit Hazay, Michel Raynal, Elad Michael Schiller, François Taïani, and Vassilis Zikas

Published in: LIPIcs, Volume 324, 28th International Conference on Principles of Distributed Systems (OPODIS 2024)

Abstract
We address the problem of Reliable Broadcast in asynchronous message-passing systems with n nodes, of which up to t are malicious (faulty), in addition to a message adversary that can drop some of the messages sent by correct (non-faulty) nodes. We present a Message-Adversary-Tolerant Byzantine Reliable Broadcast (MBRB) algorithm that communicates O(|m|+nκ) bits per node, where |m| represents the length of the application message and κ = Ω(log n) is a security parameter. This communication complexity is optimal up to the parameter κ. This significantly improves upon the state-of-the-art MBRB solution (Albouy, Frey, Raynal, and Taïani, TCS 2023), which incurs communication of O(n|m|+n²κ) bits per node. Our solution sends at most 4n² messages overall, which is asymptotically optimal. Reduced communication is achieved by employing coding techniques that replace the need for all nodes to (re-)broadcast the entire application message m. Instead, nodes forward authenticated fragments of the encoding of m using an erasure-correcting code. Under the cryptographic assumptions of threshold signatures and vector commitments, and assuming n > 3t+2d, where the adversary drops at most d messages per broadcast, our algorithm allows at least 𝓁 = n - t - (1 + ε)d (for any arbitrarily low ε > 0) correct nodes to reconstruct m, despite missing fragments caused by the malicious nodes and the message adversary.
Cite as

Timothé Albouy, Davide Frey, Ran Gelles, Carmit Hazay, Michel Raynal, Elad Michael Schiller, François Taïani, and Vassilis Zikas. Near-Optimal Communication Byzantine Reliable Broadcast Under a Message Adversary. In 28th International Conference on Principles of Distributed Systems (OPODIS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 324, pp. 14:1-14:29, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{albouy_et_al:LIPIcs.OPODIS.2024.14,
  author =	{Albouy, Timoth\'{e} and Frey, Davide and Gelles, Ran and Hazay, Carmit and Raynal, Michel and Schiller, Elad Michael and Ta\"{i}ani, Fran\c{c}ois and Zikas, Vassilis},
  title =	{{Near-Optimal Communication Byzantine Reliable Broadcast Under a Message Adversary}},
  booktitle =	{28th International Conference on Principles of Distributed Systems (OPODIS 2024)},
  pages =	{14:1--14:29},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-360-7},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{324},
  editor =	{Bonomi, Silvia and Galletta, Letterio and Rivi\`{e}re, Etienne and Schiavoni, Valerio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2024.14},
  URN =		{urn:nbn:de:0030-drops-225503},
  doi =		{10.4230/LIPIcs.OPODIS.2024.14},
  annote =	{Keywords: Asynchronous message-passing, Byzantine fault-tolerance, Message adversary, Reliable broadcast, Erasure-correction codes, \{Threshold\} signatures, \{Vector commitments\}}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2024.23
Distributed Recoverable Sketches

Authors: Diana Cohen, Roy Friedman, and Rana Shahout

Published in: LIPIcs, Volume 324, 28th International Conference on Principles of Distributed Systems (OPODIS 2024)

Abstract
Sketches are commonly used in computer systems and network monitoring tools to provide efficient query executions while maintaining a compact data representation. Switches and routers maintain sketches to track statistical characteristics of the network traffic. The availability of such data is essential for the network analysis as a whole. Consequently, being able to recover sketches is critical following a switch crash. In this paper, we explore how nodes in a network environment can cooperate to recover sketch data whenever any of them crashes. In particular, we focus on frequency estimation linear sketches, such as the Count-Min Sketch. We consider various approaches to ensure data reliability and explore the trade-offs between space consumption, runtime overheads, and traffic during recovery, which we point out as design guidelines. Besides different aspects of efficacy, we design a modular system for ease of maintenance and further scaling. A key aspect we examine is how nodes update each other about their sketch content as it evolves over time. In particular, we compare between periodic full updates vs. incremental updates. We also examine several data structures to economically represent and encode a batch of latest changes. Our framework is generic, and other data structures can be plugged-in via an abstract API as long as they implement the corresponding API methods.
Cite as

Diana Cohen, Roy Friedman, and Rana Shahout. Distributed Recoverable Sketches. In 28th International Conference on Principles of Distributed Systems (OPODIS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 324, pp. 23:1-23:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{cohen_et_al:LIPIcs.OPODIS.2024.23,
  author =	{Cohen, Diana and Friedman, Roy and Shahout, Rana},
  title =	{{Distributed Recoverable Sketches}},
  booktitle =	{28th International Conference on Principles of Distributed Systems (OPODIS 2024)},
  pages =	{23:1--23:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-360-7},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{324},
  editor =	{Bonomi, Silvia and Galletta, Letterio and Rivi\`{e}re, Etienne and Schiavoni, Valerio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2024.23},
  URN =		{urn:nbn:de:0030-drops-225594},
  doi =		{10.4230/LIPIcs.OPODIS.2024.23},
  annote =	{Keywords: Sketches, Stream Processing, Distributed Recovery, Incremental Updates, Sketch Partitioning}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2024.31
Dynamic Probabilistic Reliable Broadcast

Authors: João Paulo Bezerra, Veronika Anikina, Petr Kuznetsov, Liron Schiff, and Stefan Schmid

Published in: LIPIcs, Volume 324, 28th International Conference on Principles of Distributed Systems (OPODIS 2024)

Abstract
Byzantine reliable broadcast is a fundamental primitive in distributed systems that allows a set of processes to agree on a message broadcast by a dedicated process, even when some of them are malicious (Byzantine). It guarantees that no two correct processes deliver different messages, and if a message is delivered by a correct process, every correct process eventually delivers one. Byzantine reliable broadcast protocols are known to scale poorly, as they require Ω(n²) message exchanges, where n is the number of system members. The quadratic cost can be explained by the inherent need for every process to relay a message to every other process. In this paper, we explore ways to overcome this limitation by casting the problem to the probabilistic setting. We propose a solution in which every broadcast message is validated by a small set of witnesses, which allows us to maintain low latency and small communication complexity. In order to tolerate the slow adaptive adversary, we dynamically select the witnesses through a novel stream-local hash function: given a stream of inputs, it generates a stream of output hashed values that adapts to small deviations of the inputs. Our performance analysis shows that the proposed solution exhibits significant scalability gains over state-of-the-art protocols.
Cite as

João Paulo Bezerra, Veronika Anikina, Petr Kuznetsov, Liron Schiff, and Stefan Schmid. Dynamic Probabilistic Reliable Broadcast. In 28th International Conference on Principles of Distributed Systems (OPODIS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 324, pp. 31:1-31:30, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bezerra_et_al:LIPIcs.OPODIS.2024.31,
  author =	{Bezerra, Jo\~{a}o Paulo and Anikina, Veronika and Kuznetsov, Petr and Schiff, Liron and Schmid, Stefan},
  title =	{{Dynamic Probabilistic Reliable Broadcast}},
  booktitle =	{28th International Conference on Principles of Distributed Systems (OPODIS 2024)},
  pages =	{31:1--31:30},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-360-7},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{324},
  editor =	{Bonomi, Silvia and Galletta, Letterio and Rivi\`{e}re, Etienne and Schiavoni, Valerio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2024.31},
  URN =		{urn:nbn:de:0030-drops-225679},
  doi =		{10.4230/LIPIcs.OPODIS.2024.31},
  annote =	{Keywords: Reliable broadcast, probabilistic algorithms, witness sets, stream-local hashing, cryptocurrencies, accountability}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2024.4
AMECOS: A Modular Event-Based Framework for Concurrent Object Specification

Authors: Timothé Albouy, Antonio Fernández Anta, Chryssis Georgiou, Mathieu Gestin, Nicolas Nicolaou, and Junlang Wang

Published in: LIPIcs, Volume 324, 28th International Conference on Principles of Distributed Systems (OPODIS 2024)

Abstract
In this work, we introduce a modular framework for specifying distributed systems that we call AMECOS. Specifically, our framework departs from the traditional use of sequential specification, which presents limitations both on the specification expressiveness and implementation efficiency of inherently concurrent objects, as documented by Castañeda, Rajsbaum and Raynal in CACM 2023. Our framework focuses on the interactions between the various system components, specified as concurrent objects. Interactions are described with sequences of object events. This provides a modular way of specifying distributed systems and separates legality (object semantics) from other issues, such as consistency. We demonstrate the usability of our framework by (i) specifying various well-known concurrent objects, such as registers, shared memory, message-passing, reliable broadcast, and consensus, (ii) providing hierarchies of ordering semantics (namely, consistency hierarchy, memory hierarchy, and reliable broadcast hierarchy), and (iii) presenting a novel axiomatic proof of the impossibility of the well-known Consensus problem.
Cite as

Timothé Albouy, Antonio Fernández Anta, Chryssis Georgiou, Mathieu Gestin, Nicolas Nicolaou, and Junlang Wang. AMECOS: A Modular Event-Based Framework for Concurrent Object Specification. In 28th International Conference on Principles of Distributed Systems (OPODIS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 324, pp. 4:1-4:29, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{albouy_et_al:LIPIcs.OPODIS.2024.4,
  author =	{Albouy, Timoth\'{e} and Fern\'{a}ndez Anta, Antonio and Georgiou, Chryssis and Gestin, Mathieu and Nicolaou, Nicolas and Wang, Junlang},
  title =	{{AMECOS: A Modular Event-Based Framework for Concurrent Object Specification}},
  booktitle =	{28th International Conference on Principles of Distributed Systems (OPODIS 2024)},
  pages =	{4:1--4:29},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-360-7},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{324},
  editor =	{Bonomi, Silvia and Galletta, Letterio and Rivi\`{e}re, Etienne and Schiavoni, Valerio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2024.4},
  URN =		{urn:nbn:de:0030-drops-225409},
  doi =		{10.4230/LIPIcs.OPODIS.2024.4},
  annote =	{Keywords: Concurrency, Object specification, Consistency conditions, Consensus impossibility}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2023.39
Brief Announcement: Subquadratic Multivalued Asynchronous Byzantine Agreement WHP

Authors: Shir Cohen and Idit Keidar

Published in: LIPIcs, Volume 281, 37th International Symposium on Distributed Computing (DISC 2023)

Abstract
There have been several reductions from multivalued consensus to binary consensus over the past 20 years. To the best of our knowledge, none of them solved it for Byzantine asynchronous settings. In this short paper, we close this gap. Moreover, we do so in subquadratic communication, using newly developed subquadratic binary Byzantine Agreement techniques.
Cite as

Shir Cohen and Idit Keidar. Brief Announcement: Subquadratic Multivalued Asynchronous Byzantine Agreement WHP. In 37th International Symposium on Distributed Computing (DISC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 281, pp. 39:1-39:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{cohen_et_al:LIPIcs.DISC.2023.39,
  author =	{Cohen, Shir and Keidar, Idit},
  title =	{{Brief Announcement: Subquadratic Multivalued Asynchronous Byzantine Agreement WHP}},
  booktitle =	{37th International Symposium on Distributed Computing (DISC 2023)},
  pages =	{39:1--39:6},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-301-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{281},
  editor =	{Oshman, Rotem},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2023.39},
  URN =		{urn:nbn:de:0030-drops-191658},
  doi =		{10.4230/LIPIcs.DISC.2023.39},
  annote =	{Keywords: Byzantine agreement, subquadratic communication, fault tolerance in distributed systems}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2022.18
Make Every Word Count: Adaptive Byzantine Agreement with Fewer Words

Authors: Shir Cohen, Idit Keidar, and Alexander Spiegelman

Published in: LIPIcs, Volume 253, 26th International Conference on Principles of Distributed Systems (OPODIS 2022)

Abstract
Byzantine Agreement (BA) is a key component in many distributed systems. While Dolev and Reischuk have proven a long time ago that quadratic communication complexity is necessary for worst-case runs, the question of what can be done in practically common runs with fewer failures remained open. In this paper we present the first Byzantine Broadcast algorithm with O(n(f+1)) communication complexity in a model with resilience of n = 2t+1, where 0 ≤ f ≤ t is the actual number of process failures in a run. And for BA with strong unanimity, we present the first optimal-resilience algorithm that has linear communication complexity in the failure-free case and a quadratic cost otherwise.
Cite as

Shir Cohen, Idit Keidar, and Alexander Spiegelman. Make Every Word Count: Adaptive Byzantine Agreement with Fewer Words. In 26th International Conference on Principles of Distributed Systems (OPODIS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 253, pp. 18:1-18:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{cohen_et_al:LIPIcs.OPODIS.2022.18,
  author =	{Cohen, Shir and Keidar, Idit and Spiegelman, Alexander},
  title =	{{Make Every Word Count: Adaptive Byzantine Agreement with Fewer Words}},
  booktitle =	{26th International Conference on Principles of Distributed Systems (OPODIS 2022)},
  pages =	{18:1--18:21},
  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/entities/document/10.4230/LIPIcs.OPODIS.2022.18},
  URN =		{urn:nbn:de:0030-drops-176385},
  doi =		{10.4230/LIPIcs.OPODIS.2022.18},
  annote =	{Keywords: Byzantine Agreement, Byzantine Broadcast, Adaptive communication}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2022.43
Expander Random Walks: The General Case and Limitations

Authors: Gil Cohen, Dor Minzer, Shir Peleg, Aaron Potechin, and Amnon Ta-Shma

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)

Abstract
Cohen, Peri and Ta-Shma [Gil Cohen et al., 2021] considered the following question: Assume the vertices of an expander graph are labelled by ± 1. What "test" functions f : {±1}^t → {±1} can or cannot distinguish t independent samples from those obtained by a random walk? [Gil Cohen et al., 2021] considered only balanced labellings, and proved that for all symmetric functions the distinguishability goes down to zero with the spectral gap λ of the expander G. In addition, [Gil Cohen et al., 2021] show that functions computable by AC⁰ circuits are fooled by expanders with vanishing spectral expansion. We continue the study of this question. We generalize the result to all labelling, not merely balanced ones. We also improve the upper bound on the error of symmetric functions. More importantly, we give a matching lower bound and show a symmetric function with distinguishability going down to zero with λ but not with t. Moreover, we prove a lower bound on the error of functions in AC⁰ in particular, we prove that a random walk on expanders with constant spectral gap does not fool AC⁰.
Cite as

Gil Cohen, Dor Minzer, Shir Peleg, Aaron Potechin, and Amnon Ta-Shma. Expander Random Walks: The General Case and Limitations. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 43:1-43:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{cohen_et_al:LIPIcs.ICALP.2022.43,
  author =	{Cohen, Gil and Minzer, Dor and Peleg, Shir and Potechin, Aaron and Ta-Shma, Amnon},
  title =	{{Expander Random Walks: The General Case and Limitations}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{43:1--43:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.43},
  URN =		{urn:nbn:de:0030-drops-163849},
  doi =		{10.4230/LIPIcs.ICALP.2022.43},
  annote =	{Keywords: Expander Graphs, Random Walks, Lower Bounds}
}
  • Refine by Type
  • 19 Document/PDF
  • 12 Document/HTML

  • Refine by Publication Year
  • 1 2026
  • 11 2025
  • 2 2023
  • 1 2022
  • 3 2021
  • Show More...

  • Refine by Author
  • 5 Keidar, Idit
  • 4 Cohen, Shir
  • 3 Spiegelman, Alexander
  • 2 Albouy, Timothé
  • 2 Chang, Yi-Jun
  • Show More...

  • Refine by Series/Journal
  • 19 LIPIcs

  • Refine by Classification
  • 10 Theory of computation → Distributed algorithms
  • 2 Mathematics of computing → Probabilistic algorithms
  • 2 Theory of computation → Cryptographic primitives
  • 1 Computer systems organization → Dependable and fault-tolerant systems and networks
  • 1 Computer systems organization → Reliability
  • Show More...

  • Refine by Keyword
  • 4 Byzantine Agreement
  • 2 Asynchronous model
  • 2 Consensus
  • 2 Reliable broadcast
  • 2 fault tolerance
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact