25 Search Results for "Abraham, Ittai"

Document
DOI: 10.4230/LIPIcs.SEA.2024.6
Faster Treewidth-Based Approximations for Wiener Index

Authors: Giovanna Kobus Conrado, Amir Kafshdar Goharshady, Pavel Hudec, Pingjiang Li, and Harshit Jitendra Motwani

Published in: LIPIcs, Volume 301, 22nd International Symposium on Experimental Algorithms (SEA 2024)

Abstract
The Wiener index of a graph G is the sum of distances between all pairs of its vertices. It is a widely-used graph property in chemistry, initially introduced to examine the link between boiling points and structural properties of alkanes, which later found notable applications in drug design. Thus, computing or approximating the Wiener index of molecular graphs, i.e. graphs in which every vertex models an atom of a molecule and every edge models a bond, is of significant interest to the computational chemistry community. In this work, we build upon the observation that molecular graphs are sparse and tree-like and focus on developing efficient algorithms parameterized by treewidth to approximate the Wiener index. We present a new randomized approximation algorithm using a combination of tree decompositions and centroid decompositions. Our algorithm approximates the Wiener index within any desired multiplicative factor (1 ± ε) in time O(n ⋅ log n ⋅ k³ + √n ⋅ k/ε²), where n is the number of vertices of the graph and k is the treewidth. This time bound is almost-linear in n. Finally, we provide experimental results over standard benchmark molecules from PubChem and the Protein Data Bank, showcasing the applicability and scalability of our approach on real-world chemical graphs and comparing it with previous methods.
Cite as

Giovanna Kobus Conrado, Amir Kafshdar Goharshady, Pavel Hudec, Pingjiang Li, and Harshit Jitendra Motwani. Faster Treewidth-Based Approximations for Wiener Index. In 22nd International Symposium on Experimental Algorithms (SEA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 301, pp. 6:1-6:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{conrado_et_al:LIPIcs.SEA.2024.6,
  author =	{Conrado, Giovanna Kobus and Goharshady, Amir Kafshdar and Hudec, Pavel and Li, Pingjiang and Motwani, Harshit Jitendra},
  title =	{{Faster Treewidth-Based Approximations for Wiener Index}},
  booktitle =	{22nd International Symposium on Experimental Algorithms (SEA 2024)},
  pages =	{6:1--6:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-325-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{301},
  editor =	{Liberti, Leo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2024.6},
  URN =		{urn:nbn:de:0030-drops-203718},
  doi =		{10.4230/LIPIcs.SEA.2024.6},
  annote =	{Keywords: Computational Chemistry, Treewidth, Wiener Index}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.27
The Discrepancy of Shortest Paths

Authors: Greg Bodwin, Chengyuan Deng, Jie Gao, Gary Hoppenworth, Jalaj Upadhyay, and Chen Wang

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
The hereditary discrepancy of a set system is a quantitative measure of the pseudorandom properties of the system. Roughly speaking, hereditary discrepancy measures how well one can 2-color the elements of the system so that each set contains approximately the same number of elements of each color. Hereditary discrepancy has numerous applications in computational geometry, communication complexity and derandomization. More recently, the hereditary discrepancy of the set system of shortest paths has found applications in differential privacy [Chen et al. SODA 23]. The contribution of this paper is to improve the upper and lower bounds on the hereditary discrepancy of set systems of unique shortest paths in graphs. In particular, we show that any system of unique shortest paths in an undirected weighted graph has hereditary discrepancy O(n^{1/4}), and we construct lower bound examples demonstrating that this bound is tight up to polylog n factors. Our lower bounds hold even for planar graphs and bipartite graphs, and improve a previous lower bound of Ω(n^{1/6}) obtained by applying the trace bound of Chazelle and Lvov [SoCG'00] to a classical point-line system of Erdős. As applications, we improve the lower bound on the additive error for differentially-private all pairs shortest distances from Ω(n^{1/6}) [Chen et al. SODA 23] to Ω̃(n^{1/4}), and we improve the lower bound on additive error for the differentially-private all sets range queries problem to Ω̃(n^{1/4}), which is tight up to polylog n factors [Deng et al. WADS 23].
Cite as

Greg Bodwin, Chengyuan Deng, Jie Gao, Gary Hoppenworth, Jalaj Upadhyay, and Chen Wang. The Discrepancy of Shortest Paths. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 27:1-27:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bodwin_et_al:LIPIcs.ICALP.2024.27,
  author =	{Bodwin, Greg and Deng, Chengyuan and Gao, Jie and Hoppenworth, Gary and Upadhyay, Jalaj and Wang, Chen},
  title =	{{The Discrepancy of Shortest Paths}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{27:1--27:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.27},
  URN =		{urn:nbn:de:0030-drops-201705},
  doi =		{10.4230/LIPIcs.ICALP.2024.27},
  annote =	{Keywords: Discrepancy, hereditary discrepancy, shortest paths, differential privacy}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.58
New Tradeoffs for Decremental Approximate All-Pairs Shortest Paths

Authors: Michal Dory, Sebastian Forster, Yasamin Nazari, and Tijn de Vos

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
We provide new tradeoffs between approximation and running time for the decremental all-pairs shortest paths (APSP) problem. For undirected graphs with m edges and n nodes undergoing edge deletions, we provide four new approximate decremental APSP algorithms, two for weighted and two for unweighted graphs. Our first result is (2+ε)-APSP with total update time Õ(m^{1/2}n^{3/2}) (when m = n^{1+c} for any constant 0 < c < 1). Prior to our work the fastest algorithm for weighted graphs with approximation at most 3 had total Õ(mn) update time for (1+ε)-APSP [Bernstein, SICOMP 2016]. Our second result is (2+ε, W_{u,v})-APSP with total update time Õ(nm^{3/4}), where the second term is an additive stretch with respect to W_{u,v}, the maximum weight on the shortest path from u to v. Our third result is (2+ε)-APSP for unweighted graphs in Õ(m^{7/4}) update time, which for sparse graphs (m = o(n^{8/7})) is the first subquadratic (2+ε)-approximation. Our last result for unweighted graphs is (1+ε, 2(k-1))-APSP, for k ≥ 2, with Õ(n^{2-1/k}m^{1/k}) total update time (when m = n^{1+c} for any constant c > 0). For comparison, in the special case of (1+ε, 2)-approximation, this improves over the state-of-the-art algorithm by [Henzinger, Krinninger, Nanongkai, SICOMP 2016] with total update time of Õ(n^{2.5}). All of our results are randomized, work against an oblivious adversary, and have constant query time.
Cite as

Michal Dory, Sebastian Forster, Yasamin Nazari, and Tijn de Vos. New Tradeoffs for Decremental Approximate All-Pairs Shortest Paths. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 58:1-58:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{dory_et_al:LIPIcs.ICALP.2024.58,
  author =	{Dory, Michal and Forster, Sebastian and Nazari, Yasamin and de Vos, Tijn},
  title =	{{New Tradeoffs for Decremental Approximate All-Pairs Shortest Paths}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{58:1--58:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.58},
  URN =		{urn:nbn:de:0030-drops-202012},
  doi =		{10.4230/LIPIcs.ICALP.2024.58},
  annote =	{Keywords: Decremental Shortest Path, All-Pairs Shortest Paths}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.97
Cut Sparsification and Succinct Representation of Submodular Hypergraphs

Authors: Yotam Kenneth and Robert Krauthgamer

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
In cut sparsification, all cuts of a hypergraph H = (V,E,w) are approximated within 1±ε factor by a small hypergraph H'. This widely applied method was generalized recently to a setting where the cost of cutting each hyperedge e is provided by a splitting function g_e: 2^e → ℝ_+. This generalization is called a submodular hypergraph when the functions {g_e}_{e ∈ E} are submodular, and it arises in machine learning, combinatorial optimization, and algorithmic game theory. Previous work studied the setting where H' is a reweighted sub-hypergraph of H, and measured the size of H' by the number of hyperedges in it. In this setting, we present two results: (i) all submodular hypergraphs admit sparsifiers of size polynomial in n = |V| and ε^{-1}; (ii) we propose a new parameter, called spread, and use it to obtain smaller sparsifiers in some cases. We also show that for a natural family of splitting functions, relaxing the requirement that H' be a reweighted sub-hypergraph of H yields a substantially smaller encoding of the cuts of H (almost a factor n in the number of bits). This is in contrast to graphs, where the most succinct representation is attained by reweighted subgraphs. A new tool in our construction of succinct representation is the notion of deformation, where a splitting function g_e is decomposed into a sum of functions of small description, and we provide upper and lower bounds for deformation of common splitting functions.
Cite as

Yotam Kenneth and Robert Krauthgamer. Cut Sparsification and Succinct Representation of Submodular Hypergraphs. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 97:1-97:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{kenneth_et_al:LIPIcs.ICALP.2024.97,
  author =	{Kenneth, Yotam and Krauthgamer, Robert},
  title =	{{Cut Sparsification and Succinct Representation of Submodular Hypergraphs}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{97:1--97:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.97},
  URN =		{urn:nbn:de:0030-drops-202406},
  doi =		{10.4230/LIPIcs.ICALP.2024.97},
  annote =	{Keywords: Cut Sparsification, Submodular Hypergraphs, Succinct Representation}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.101
On the Space Usage of Approximate Distance Oracles with Sub-2 Stretch

Authors: Tsvi Kopelowitz, Ariel Korin, and Liam Roditty

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
For an undirected unweighted graph G = (V,E) with n vertices and m edges, let d(u,v) denote the distance from u ∈ V to v ∈ V in G. An (α,β)-stretch approximate distance oracle (ADO) for G is a data structure that given u,v ∈ V returns in constant (or near constant) time a value dˆ(u,v) such that d(u,v) ≤ dˆ(u,v) ≤ α⋅ d(u,v) + β, for some reals α > 1, β. Thorup and Zwick [Mikkel Thorup and Uri Zwick, 2005] showed that one cannot beat stretch 3 with subquadratic space (in terms of n) for general graphs. Pǎtraşcu and Roditty [Mihai Pǎtraşcu and Liam Roditty, 2010] showed that one can obtain stretch 2 using O(m^{1/3}n^{4/3}) space, and so if m is subquadratic in n then the space usage is also subquadratic. Moreover, Pǎtraşcu and Roditty [Mihai Pǎtraşcu and Liam Roditty, 2010] showed that one cannot beat stretch 2 with subquadratic space even for graphs where m = Õ(n), based on the set-intersection hypothesis. In this paper we explore the conditions for which an ADO can beat stretch 2 while using subquadratic space. In particular, we show that if the maximum degree in G is Δ_G ≤ O(n^{1/k-ε}) for some 0 < ε ≤ 1/k, then there exists an ADO for G that uses Õ(n^{2-(kε)/3) space and has a (2,1-k)-stretch. For k = 2 this result implies a subquadratic sub-2 stretch ADO for graphs with Δ_G ≤ O(n^{1/2-ε}). Moreover, we prove a conditional lower bound, based on the set intersection hypothesis, which states that for any positive integer k ≤ log n, obtaining a sub-(k+2)/k stretch for graphs with Δ_G = Θ(n^{1/k}) requires Ω̃(n²) space. Thus, for graphs with maximum degree Θ(n^{1/2}), obtaining a sub-2 stretch requires Ω̃(n²) space.
Cite as

Tsvi Kopelowitz, Ariel Korin, and Liam Roditty. On the Space Usage of Approximate Distance Oracles with Sub-2 Stretch. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 101:1-101:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{kopelowitz_et_al:LIPIcs.ICALP.2024.101,
  author =	{Kopelowitz, Tsvi and Korin, Ariel and Roditty, Liam},
  title =	{{On the Space Usage of Approximate Distance Oracles with Sub-2 Stretch}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{101:1--101:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.101},
  URN =		{urn:nbn:de:0030-drops-202443},
  doi =		{10.4230/LIPIcs.ICALP.2024.101},
  annote =	{Keywords: Graph algorithms, Approximate distance oracle, data structures, shortest path}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2023.14
Fever: Optimal Responsive View Synchronisation

Authors: Andrew Lewis-Pye and Ittai Abraham

Published in: LIPIcs, Volume 286, 27th International Conference on Principles of Distributed Systems (OPODIS 2023)

Abstract
View synchronisation is an important component of many modern Byzantine Fault Tolerant State Machine Replication (SMR) systems in the partial synchrony model. Roughly, the efficiency of view synchronisation is measured as the word complexity and latency required for moving from being synchronised in a view of one correct leader to being synchronised in the view of the next correct leader. The efficiency of view synchronisation has emerged as a major bottleneck in the efficiency of SMR systems as a whole. A key question remained open: Do there exist view synchronisation protocols with asymptotically optimal quadratic worst-case word complexity that also obtain linear complexity and responsiveness when moving between consecutive correct leaders? We answer this question affirmatively with a new view synchronisation protocol for partial synchrony assuming partial initial clock synchronisation, called Fever. If n is the number of processors and t is the largest integer < n/3, then Fever has resilience t, and in all executions with at most 0 ≤ f ≤ t Byzantine parties and network delays of at most δ ≤ Δ after GST (where f and δ are unknown), Fever has worst-case word complexity O(fn+n) and worst-case latency O(Δ f + δ).
Cite as

Andrew Lewis-Pye and Ittai Abraham. Fever: Optimal Responsive View Synchronisation. In 27th International Conference on Principles of Distributed Systems (OPODIS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 286, pp. 14:1-14:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{lewispye_et_al:LIPIcs.OPODIS.2023.14,
  author =	{Lewis-Pye, Andrew and Abraham, Ittai},
  title =	{{Fever: Optimal Responsive View Synchronisation}},
  booktitle =	{27th International Conference on Principles of Distributed Systems (OPODIS 2023)},
  pages =	{14:1--14:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-308-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{286},
  editor =	{Bessani, Alysson and D\'{e}fago, Xavier and Nakamura, Junya and Wada, Koichi and Yamauchi, Yukiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2023.14},
  URN =		{urn:nbn:de:0030-drops-195041},
  doi =		{10.4230/LIPIcs.OPODIS.2023.14},
  annote =	{Keywords: Distributed Systems, State Machine Replication}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2023.29
On the Round Complexity of Asynchronous Crusader Agreement

Authors: Ittai Abraham, Naama Ben-David, Gilad Stern, and Sravya Yandamuri

Published in: LIPIcs, Volume 286, 27th International Conference on Principles of Distributed Systems (OPODIS 2023)

Abstract
We present new lower and upper bounds on the number of communication rounds required for asynchronous Crusader Agreement (CA) and Binding Crusader Agreement (BCA), two primitives that are used for solving binary consensus. We show results for the information theoretic and authenticated settings. In doing so, we present a generic model for proving round complexity lower bounds in the asynchronous setting. In some settings, our attempts to prove lower bounds on round complexity fail. Instead, we show new, tight, rather surprising round complexity upper bounds for Byzantine fault tolerant BCA with and without a PKI setup.
Cite as

Ittai Abraham, Naama Ben-David, Gilad Stern, and Sravya Yandamuri. On the Round Complexity of Asynchronous Crusader Agreement. In 27th International Conference on Principles of Distributed Systems (OPODIS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 286, pp. 29:1-29:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{abraham_et_al:LIPIcs.OPODIS.2023.29,
  author =	{Abraham, Ittai and Ben-David, Naama and Stern, Gilad and Yandamuri, Sravya},
  title =	{{On the Round Complexity of Asynchronous Crusader Agreement}},
  booktitle =	{27th International Conference on Principles of Distributed Systems (OPODIS 2023)},
  pages =	{29:1--29:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-308-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{286},
  editor =	{Bessani, Alysson and D\'{e}fago, Xavier and Nakamura, Junya and Wada, Koichi and Yamauchi, Yukiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2023.29},
  URN =		{urn:nbn:de:0030-drops-195195},
  doi =		{10.4230/LIPIcs.OPODIS.2023.29},
  annote =	{Keywords: lower bounds, asynchronous protocols, round complexity}
}
Document
DOI: 10.4230/LIPIcs.DISC.2023.1
Colordag: An Incentive-Compatible Blockchain

Authors: Ittai Abraham, Danny Dolev, Ittay Eyal, and Joseph Y. Halpern

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

Abstract
We present Colordag, a blockchain protocol where following the prescribed strategy is, with high probability, a best response as long as all miners have less than 1/2 of the mining power. We prove the correctness of Colordag even if there is an extremely powerful adversary who knows future actions of the scheduler: specifically, when agents will generate blocks and when messages will arrive. The state-of-the-art protocol, Fruitchain, is an ε-Nash equilibrium as long as all miners have less than 1/2 of the mining power. However, there is a simple deviation that guarantees that deviators are never worse off than they would be by following Fruitchain, and can sometimes do better. Thus, agents are motivated to deviate. Colordag implements a solution concept that we call ε-sure Nash equilibrium and does not suffer from this problem. Because it is an ε-sure Nash equilibrium, Colordag is an ε-Nash equilibrium and with probability 1-ε is a best response.
Cite as

Ittai Abraham, Danny Dolev, Ittay Eyal, and Joseph Y. Halpern. Colordag: An Incentive-Compatible Blockchain. In 37th International Symposium on Distributed Computing (DISC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 281, pp. 1:1-1:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{abraham_et_al:LIPIcs.DISC.2023.1,
  author =	{Abraham, Ittai and Dolev, Danny and Eyal, Ittay and Halpern, Joseph Y.},
  title =	{{Colordag: An Incentive-Compatible Blockchain}},
  booktitle =	{37th International Symposium on Distributed Computing (DISC 2023)},
  pages =	{1:1--1:22},
  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.1},
  URN =		{urn:nbn:de:0030-drops-191272},
  doi =		{10.4230/LIPIcs.DISC.2023.1},
  annote =	{Keywords: Game theory, incentives, blockchain}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2022.16
New Dolev-Reischuk Lower Bounds Meet Blockchain Eclipse Attacks

Authors: Ittai Abraham and Gilad Stern

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

Abstract
In 1985, Dolev and Reischuk proved a fundamental communication lower bounds on protocols achieving fault tolerant synchronous broadcast and consensus: any deterministic protocol solving those tasks (even against omission faults) requires at least a quadratic number of messages to be sent by nonfaulty parties. In contrast, many blockchain systems achieve consensus with seemingly linear communication per instance against Byzantine faults. We explore this dissonance in three main ways. First, we extend the Dolev-Reischuk family of lower bounds and prove a new lower bound for Crusader Broadcast protocols. Our lower bound for crusader broadcast requires non-trivial extensions and a much stronger Byzantine adversary with the ability to simulate honest parties. Secondly, we extend our lower bounds to all-but-m Crusader Broadcast, in which up to m parties are allowed to output a different value. Finally, we discuss the ways in which these lower bounds relate to the security of blockchain systems. We show how Eclipse-style attacks in such systems can be viewed as specific instances of the attacks used in our lower bound for Crusader Broadcast. This connection suggests a more systematic way of analyzing and reasoning about Eclipse-style attacks through the lens of the Dolev-Reischuk family of attacks.
Cite as

Ittai Abraham and Gilad Stern. New Dolev-Reischuk Lower Bounds Meet Blockchain Eclipse Attacks. In 26th International Conference on Principles of Distributed Systems (OPODIS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 253, pp. 16:1-16:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{abraham_et_al:LIPIcs.OPODIS.2022.16,
  author =	{Abraham, Ittai and Stern, Gilad},
  title =	{{New Dolev-Reischuk Lower Bounds Meet Blockchain Eclipse Attacks}},
  booktitle =	{26th International Conference on Principles of Distributed Systems (OPODIS 2022)},
  pages =	{16:1--16:18},
  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.16},
  URN =		{urn:nbn:de:0030-drops-176368},
  doi =		{10.4230/LIPIcs.OPODIS.2022.16},
  annote =	{Keywords: consensus, crusader broadcast, Byzantine fault tolerance, blockchain, synchrony, lower bounds}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2022.24
Communication-Efficient BFT Using Small Trusted Hardware to Tolerate Minority Corruption

Authors: Sravya Yandamuri, Ittai Abraham, Kartik Nayak, and Michael K. Reiter

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

Abstract
Agreement protocols for partially synchronous networks tolerate fewer than one-third Byzantine faults. If parties are equipped with trusted hardware that prevents equivocation, then fault tolerance can be improved to fewer than one-half Byzantine faults, but typically at the cost of increased communication complexity. In this work, we present results that use small trusted hardware without worsening communication complexity assuming the adversary controls a fraction of the network that is less than one-half. In particular, we show a version of HotStuff that retains linear communication complexity in each view, leveraging trusted hardware to tolerate a minority of corruptions. Our result uses expander graph techniques to achieve efficient communication in a manner that may be of independent interest.
Cite as

Sravya Yandamuri, Ittai Abraham, Kartik Nayak, and Michael K. Reiter. Communication-Efficient BFT Using Small Trusted Hardware to Tolerate Minority Corruption. In 26th International Conference on Principles of Distributed Systems (OPODIS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 253, pp. 24:1-24:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{yandamuri_et_al:LIPIcs.OPODIS.2022.24,
  author =	{Yandamuri, Sravya and Abraham, Ittai and Nayak, Kartik and Reiter, Michael K.},
  title =	{{Communication-Efficient BFT Using Small Trusted Hardware to Tolerate Minority Corruption}},
  booktitle =	{26th International Conference on Principles of Distributed Systems (OPODIS 2022)},
  pages =	{24:1--24:23},
  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.24},
  URN =		{urn:nbn:de:0030-drops-176448},
  doi =		{10.4230/LIPIcs.OPODIS.2022.24},
  annote =	{Keywords: communication complexity, consensus, trusted hardware}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2022.38
Brief Announcement: Authenticated Consensus in Synchronous Systems with Mixed Faults

Authors: Ittai Abraham, Danny Dolev, Alon Kagan, and Gilad Stern

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

Abstract
Protocols solving authenticated consensus in synchronous networks with Byzantine faults have been widely researched and known to exists if and only if n > 2f for f Byzantine faults. Similarly, protocols solving authenticated consensus in partially synchronous networks are known to exist if n > 3f+2k for f Byzantine faults and k crash faults. In this work we fill a natural gap in our knowledge by presenting MixSync, an authenticated consensus protocol in synchronous networks resilient to f Byzantine faults and k crash faults if n > 2f+k. As a basic building block, we first define and then construct a publicly verifiable crusader agreement protocol with the same resilience. The protocol uses a simple double-send round to guarantee non-equivocation, a technique later used in the MixSync protocol. We then discuss how to construct a state machine replication protocol using these ideas, and how they can be used in general to make such protocols resilient to crash faults. Finally, we prove lower bounds showing that n > 2f+k is optimally resilient for consensus and state machine replication protocols.
Cite as

Ittai Abraham, Danny Dolev, Alon Kagan, and Gilad Stern. Brief Announcement: Authenticated Consensus in Synchronous Systems with Mixed Faults. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 38:1-38:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{abraham_et_al:LIPIcs.DISC.2022.38,
  author =	{Abraham, Ittai and Dolev, Danny and Kagan, Alon and Stern, Gilad},
  title =	{{Brief Announcement: Authenticated Consensus in Synchronous Systems with Mixed Faults}},
  booktitle =	{36th International Symposium on Distributed Computing (DISC 2022)},
  pages =	{38:1--38:3},
  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.38},
  URN =		{urn:nbn:de:0030-drops-172292},
  doi =		{10.4230/LIPIcs.DISC.2022.38},
  annote =	{Keywords: consensus, state machine replication, mixed faults, synchrony, lower bounds}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2022.39
Brief Announcement: It’s not easy to relax: liveness in chained BFT protocols

Authors: Ittai Abraham, Natacha Crooks, Neil Giridharan, Heidi Howard, and Florian Suri-Payer

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

Abstract
Modern chained BFT SMR protocols have poor liveness under failures as they require multiple consecutive honest leaders to commit a single block. Siesta, our proposed new BFT SMR protocol, is instead able to commit a block that spans multiple non-consecutive honest leaders. Siesta reduces the expected commit latency of HotStuff by a factor of three under failures, and the worst-case latency by a factor of eight.
Cite as

Ittai Abraham, Natacha Crooks, Neil Giridharan, Heidi Howard, and Florian Suri-Payer. Brief Announcement: It’s not easy to relax: liveness in chained BFT protocols. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 39:1-39:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{abraham_et_al:LIPIcs.DISC.2022.39,
  author =	{Abraham, Ittai and Crooks, Natacha and Giridharan, Neil and Howard, Heidi and Suri-Payer, Florian},
  title =	{{Brief Announcement: It’s not easy to relax: liveness in chained BFT protocols}},
  booktitle =	{36th International Symposium on Distributed Computing (DISC 2022)},
  pages =	{39:1--39:3},
  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.39},
  URN =		{urn:nbn:de:0030-drops-172305},
  doi =		{10.4230/LIPIcs.DISC.2022.39},
  annote =	{Keywords: Consensus, blockchain, BFT}
}
Document
Invited Talk
DOI: 10.4230/OASIcs.FAB.2022.1
Reflections on the Past, Present and Future of Blockchain Foundations and Applications (Invited Talk)

Authors: Ittai Abraham

Published in: OASIcs, Volume 101, 5th International Symposium on Foundations and Applications of Blockchain 2022 (FAB 2022)

Abstract
We survey some of the amazing progress in Blockchain technology in the last 5 years: from foundations like consensus protocols, execution models, and zero-knowledge proofs, to why these foundations are critical for applications like decentralized finance and web3. The main part of the talk will try to envision the future of Blockchains: how will the "Endgame" look like? What foundations are we still missing? We argue that for Blockchains to thrive and reach Billions of users, we should expect a much more regulated landscape to emerge and discuss some exciting opportunities in reg-crypto and RegDeFi. An example of this direction is our new work on UTT which is a decentralized Ecash system with accountable privacy.
Cite as

Ittai Abraham. Reflections on the Past, Present and Future of Blockchain Foundations and Applications (Invited Talk). In 5th International Symposium on Foundations and Applications of Blockchain 2022 (FAB 2022). Open Access Series in Informatics (OASIcs), Volume 101, p. 1:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{abraham:OASIcs.FAB.2022.1,
  author =	{Abraham, Ittai},
  title =	{{Reflections on the Past, Present and Future of Blockchain Foundations and Applications}},
  booktitle =	{5th International Symposium on Foundations and Applications of Blockchain 2022 (FAB 2022)},
  pages =	{1:1--1:1},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-248-8},
  ISSN =	{2190-6807},
  year =	{2022},
  volume =	{101},
  editor =	{Tucci-Piergiovanni, Sara and Crooks, Natacha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.FAB.2022.1},
  URN =		{urn:nbn:de:0030-drops-162686},
  doi =		{10.4230/OASIcs.FAB.2022.1},
  annote =	{Keywords: Blockchain}
}
Document
Invited Talk
DOI: 10.4230/OASIcs.Tokenomics.2021.1
Distributed Computing Meets Game Theory: Fault Tolerance and Implementation with Cheap Talk (Invited Talk)

Authors: Joseph Y. Halpern

Published in: OASIcs, Volume 97, 3rd International Conference on Blockchain Economics, Security and Protocols (Tokenomics 2021)

Abstract
Traditionally, work in distributed computing has divided the agents into "good guys" and "bad guys". The good guys follow the protocol; the bad guys do everything in their power to make sure it does not work. By way of contrast, game theory has focused on "rational" agents, who try to maximize their utilities. Here I try to combine these viewpoints. Specifically, following the work of Abraham et al. [I. Abraham et al., 2006], I consider (k,t)-robust protocols/strategies, which tolerate coalitions of rational players of size up to k and up to t malicious players. I focus in particular on the problem that economists have called implementing a mediator. That is, can the players in the system, just talking among themselves (using what economists call "cheap talk") simulate the effects of the mediator (see, e.g., [I. Barany, 1992; E. Ben-Porath, 2003; Forges, 1990; D. Gerardi, 2004; Y. Heller, 2005; A. Urbano and J. E. Vila, 2002; A. Urbano and J. E. Vila, 2004]). In computer science, this essentially amounts to multiparty computation [O. Goldreich et al., 1987; A. Shamir et al., 1981; A. Yao, 1982]. Ideas from cryptography and distributed computing allow us to prove results on how many agents are required to implement a (k,t)-robust mediator just using cheap talk. These results subsume (and, in some cases, correct) results from the game theory literature. The results of Abraham et al. [I. Abraham et al., 2006] were proved for what are called synchronous systems in the distributed computing community; this is also the case for all the results in the economics literature cited above. In synchronous systems, communication proceeds in atomic rounds, and all messages sent during round r are received by round r + 1. But many systems in the real world are asynchronous. In an asynchronous setting, there are no rounds; messages sent by the players may take arbitrarily long to get to their recipients. Markets and the internet are best viewed as asynchronous. Blockchain implementations assume partial synchrony, where there is an upper bound on how long messages take to arrive. The partial synchronous setting already shows some of the difficulty of moving away from synchrony: An agent i can wait to take its action until it receives a message from j (on which its action can depend). This cannot happen in a synchronous setting. Abraham, Dolev, Geffner, abnd Halpern [I. Abraham et al., 2019] extend the results on implementing mediators to the asynchronous setting.
Cite as

Joseph Y. Halpern. Distributed Computing Meets Game Theory: Fault Tolerance and Implementation with Cheap Talk (Invited Talk). In 3rd International Conference on Blockchain Economics, Security and Protocols (Tokenomics 2021). Open Access Series in Informatics (OASIcs), Volume 97, pp. 1:1-1:2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{halpern:OASIcs.Tokenomics.2021.1,
  author =	{Halpern, Joseph Y.},
  title =	{{Distributed Computing Meets Game Theory: Fault Tolerance and Implementation with Cheap Talk}},
  booktitle =	{3rd International Conference on Blockchain Economics, Security and Protocols (Tokenomics 2021)},
  pages =	{1:1--1:2},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-220-4},
  ISSN =	{2190-6807},
  year =	{2022},
  volume =	{97},
  editor =	{Gramoli, Vincent and Halaburda, Hanna and Pass, Rafael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Tokenomics.2021.1},
  URN =		{urn:nbn:de:0030-drops-158981},
  doi =		{10.4230/OASIcs.Tokenomics.2021.1},
  annote =	{Keywords: robust equilibrium, implementing mediators, asynchronous systems}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2021.5
Good-Case and Bad-Case Latency of Unauthenticated Byzantine Broadcast: A Complete Categorization

Authors: Ittai Abraham, Ling Ren, and Zhuolun Xiang

Published in: LIPIcs, Volume 217, 25th International Conference on Principles of Distributed Systems (OPODIS 2021)

Abstract
This paper studies the good-case latency of unauthenticated Byzantine fault-tolerant broadcast, which measures the time it takes for all non-faulty parties to commit given a non-faulty broadcaster. For both asynchrony and synchrony, we show that n ≥ 4f is the tight resilience threshold that separates good-case 2 rounds and 3 rounds. For asynchronous Byzantine reliable broadcast (BRB), we also investigate the bad-case latency for all non-faulty parties to commit when the broadcaster is faulty but some non-faulty party commits. We provide matching upper and lower bounds on the resilience threshold of bad-case latency for BRB protocols with optimal good-case latency of 2 rounds. In particular, we show 2 impossibility results and propose 4 asynchronous BRB protocols.
Cite as

Ittai Abraham, Ling Ren, and Zhuolun Xiang. Good-Case and Bad-Case Latency of Unauthenticated Byzantine Broadcast: A Complete Categorization. In 25th International Conference on Principles of Distributed Systems (OPODIS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 217, pp. 5:1-5:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{abraham_et_al:LIPIcs.OPODIS.2021.5,
  author =	{Abraham, Ittai and Ren, Ling and Xiang, Zhuolun},
  title =	{{Good-Case and Bad-Case Latency of Unauthenticated Byzantine Broadcast: A Complete Categorization}},
  booktitle =	{25th International Conference on Principles of Distributed Systems (OPODIS 2021)},
  pages =	{5:1--5:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-219-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{217},
  editor =	{Bramas, Quentin and Gramoli, Vincent and Milani, Alessia},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2021.5},
  URN =		{urn:nbn:de:0030-drops-157806},
  doi =		{10.4230/LIPIcs.OPODIS.2021.5},
  annote =	{Keywords: Byzantine broadcast, asynchrony, synchrony, latency, good-case, optimal}
}
  • Refine by Author
  • 18 Abraham, Ittai
  • 6 Nayak, Kartik
  • 4 Ren, Ling
  • 4 Stern, Gilad
  • 3 Yandamuri, Sravya
  • Show More...

  • Refine by Classification
  • 11 Theory of computation → Distributed algorithms
  • 4 Security and privacy → Distributed systems security
  • 2 Theory of computation → Communication complexity
  • 2 Theory of computation → Shortest paths
  • 1 Applied computing → Digital cash
  • Show More...

  • Refine by Keyword
  • 5 consensus
  • 5 synchrony
  • 3 Blockchain
  • 3 Byzantine fault tolerance
  • 3 blockchain
  • Show More...

  • Refine by Type
  • 25 document

  • Refine by Publication Year
  • 7 2024
  • 6 2022
  • 3 2021
  • 3 2023
  • 2 2020
  • Show More...

© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact