17 Search Results for "Fujiwara, Hiroshi"


Document
Cordial Miners: Fast and Efficient Consensus for Every Eventuality

Authors: Idit Keidar, Oded Naor, Ouri Poupko, and Ehud Shapiro

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


Abstract
Cordial Miners are a family of efficient Byzantine Atomic Broadcast protocols, with instances for asynchrony and eventual synchrony. They improve the latency of state-of-the-art DAG-based protocols by almost 2× and achieve optimal good-case complexity of O(n) by forgoing Reliable Broadcast as a building block. Rather, Cordial Miners use the blocklace - a partially-ordered counterpart of the totally-ordered blockchain data structure - to implement the three algorithmic components of consensus: Dissemination, equivocation-exclusion, and ordering.

Cite as

Idit Keidar, Oded Naor, Ouri Poupko, and Ehud Shapiro. Cordial Miners: Fast and Efficient Consensus for Every Eventuality. In 37th International Symposium on Distributed Computing (DISC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 281, pp. 26:1-26:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{keidar_et_al:LIPIcs.DISC.2023.26,
  author =	{Keidar, Idit and Naor, Oded and Poupko, Ouri and Shapiro, Ehud},
  title =	{{Cordial Miners: Fast and Efficient Consensus for Every Eventuality}},
  booktitle =	{37th International Symposium on Distributed Computing (DISC 2023)},
  pages =	{26:1--26: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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2023.26},
  URN =		{urn:nbn:de:0030-drops-191525},
  doi =		{10.4230/LIPIcs.DISC.2023.26},
  annote =	{Keywords: Byzantine Fault Tolerance, State Machine Replication, DAG, Consensus, Blockchain, Blocklace, Cordial Dissemination}
}
Document
Beeping Shortest Paths via Hypergraph Bipartite Decomposition

Authors: Fabien Dufoulon, Yuval Emek, and Ran Gelles

Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)


Abstract
Constructing a shortest path between two network nodes is a fundamental task in distributed computing. This work develops schemes for the construction of shortest paths in randomized beeping networks between a predetermined source node and an arbitrary set of destination nodes. Our first scheme constructs a (single) shortest path to an arbitrary destination in O(D log log n + log³ n) rounds with high probability. Our second scheme constructs multiple shortest paths, one per each destination, in O(D log² n + log³ n) rounds with high probability. Our schemes are based on a reduction of the above shortest path construction tasks to a decomposition of hypergraphs into bipartite hypergraphs: We develop a beeping procedure that partitions the hyperedge set of a hypergraph H = (V_H, E_H) into k = Θ (log² n) disjoint subsets F₁ ∪ ⋯ ∪ F_k = E_H such that the (sub-)hypergraph (V_H, F_i) is bipartite in the sense that there exists a vertex subset U ⊆ V such that |U ∩ e| = 1 for every e ∈ F_i. This procedure turns out to be instrumental in speeding up shortest path constructions under the beeping model.

Cite as

Fabien Dufoulon, Yuval Emek, and Ran Gelles. Beeping Shortest Paths via Hypergraph Bipartite Decomposition. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 45:1-45:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{dufoulon_et_al:LIPIcs.ITCS.2023.45,
  author =	{Dufoulon, Fabien and Emek, Yuval and Gelles, Ran},
  title =	{{Beeping Shortest Paths via Hypergraph Bipartite Decomposition}},
  booktitle =	{14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
  pages =	{45:1--45:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-263-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{251},
  editor =	{Tauman Kalai, Yael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.45},
  URN =		{urn:nbn:de:0030-drops-175485},
  doi =		{10.4230/LIPIcs.ITCS.2023.45},
  annote =	{Keywords: Beeping Networks, Shortest Paths, Hypergraph Bipartite Decomposition}
}
Document
Locally Restricted Proof Labeling Schemes

Authors: Yuval Emek, Yuval Gil, and Shay Kutten

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


Abstract
Introduced by Korman, Kutten, and Peleg (PODC 2005), a proof labeling scheme (PLS) is a distributed verification system dedicated to evaluating if a given configured graph satisfies a certain property. It involves a centralized prover, whose role is to provide proof that a given configured graph is a yes-instance by means of assigning labels to the nodes, and a distributed verifier, whose role is to verify the validity of the given proof via local access to the assigned labels. In this paper, we introduce the notion of a locally restricted PLS in which the prover’s power is restricted to that of a LOCAL algorithm with a polylogarithmic number of rounds. To circumvent inherent impossibilities of PLSs in the locally restricted setting, we turn to models that relax the correctness requirements by allowing the verifier to accept some no-instances as long as they are not "too far" from satisfying the property in question. To this end, we evaluate (1) distributed graph optimization problems (OptDGPs) based on the notion of an approximate proof labeling scheme (APLS) (analogous to the type of relaxation used in sequential approximation algorithms); and (2) configured graph families (CGFs) based on the notion of a testing proof labeling schemes (TPLS) (analogous to the type of relaxation used in property testing algorithms). The main contribution of the paper comes in the form of two generic compilers, one for OptDGPs and one for CGFs: given a black-box access to an APLS (resp., PLS) for a large class of OptDGPs (resp., CGFs), the compiler produces a locally restricted APLS (resp., TPLS) for the same problem, while losing at most a (1 + ε) factor in the scheme’s relaxation guarantee. An appealing feature of the two compilers is that they only require a logarithmic additive label size overhead.

Cite as

Yuval Emek, Yuval Gil, and Shay Kutten. Locally Restricted Proof Labeling Schemes. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 20:1-20:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{emek_et_al:LIPIcs.DISC.2022.20,
  author =	{Emek, Yuval and Gil, Yuval and Kutten, Shay},
  title =	{{Locally Restricted Proof Labeling Schemes}},
  booktitle =	{36th International Symposium on Distributed Computing (DISC 2022)},
  pages =	{20:1--20:22},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2022.20},
  URN =		{urn:nbn:de:0030-drops-172111},
  doi =		{10.4230/LIPIcs.DISC.2022.20},
  annote =	{Keywords: proof labeling schemes, generic compilers, SLOCAL algorithms}
}
Document
On Payment Channels in Asynchronous Money Transfer Systems

Authors: Oded Naor and Idit Keidar

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


Abstract
Money transfer is an abstraction that realizes the core of cryptocurrencies. It has been shown that, contrary to common belief, money transfer in the presence of Byzantine faults can be implemented in asynchronous networks and does not require consensus. Nonetheless, existing implementations of money transfer still require a quadratic message complexity per payment, making attempts to scale hard. In common blockchains, such as Bitcoin and Ethereum, this cost is mitigated by payment channels implemented as a second layer on top of the blockchain allowing to make many off-chain payments between two users who share a channel. Such channels require only on-chain transactions for channel opening and closing, while the intermediate payments are done off-chain with constant message complexity. But payment channels in-use today require synchrony; therefore, they are inadequate for asynchronous money transfer systems. In this paper, we provide a series of possibility and impossibility results for payment channels in asynchronous money transfer systems. We first prove a quadratic lower bound on the message complexity of on-chain transfers. Then, we explore two types of payment channels, unidirectional and bidirectional. We define them as shared memory abstractions and prove that in certain cases they can be implemented as a second layer on top of an asynchronous money transfer system whereas in other cases it is impossible.

Cite as

Oded Naor and Idit Keidar. On Payment Channels in Asynchronous Money Transfer Systems. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 29:1-29:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{naor_et_al:LIPIcs.DISC.2022.29,
  author =	{Naor, Oded and Keidar, Idit},
  title =	{{On Payment Channels in Asynchronous Money Transfer Systems}},
  booktitle =	{36th International Symposium on Distributed Computing (DISC 2022)},
  pages =	{29:1--29:20},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2022.29},
  URN =		{urn:nbn:de:0030-drops-172201},
  doi =		{10.4230/LIPIcs.DISC.2022.29},
  annote =	{Keywords: Blockchains, Asynchrony, Byzantine faults, Payment channels}
}
Document
Brief Announcement
Brief Announcement: Null Messages, Information and Coordination

Authors: Raïssa Nataf, Guy Goren, and Yoram Moses

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


Abstract
This paper investigates how null messages can transfer information in fault-prone synchronous systems. The notion of an f-resilient message block is defined and is shown to capture the fundamental communication pattern for knowledge transfer. In general, this pattern combines both null messages and explicit messages. It thus provides a fault-tolerant extension of the classic notion of a message-chain. Based on the above, we provide tight necessary and sufficient characterizations of the generalized communication patterns that can serve to solve the distributed tasks of (nice-run) Signalling and Ordered Response.

Cite as

Raïssa Nataf, Guy Goren, and Yoram Moses. Brief Announcement: Null Messages, Information and Coordination. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 49:1-49:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{nataf_et_al:LIPIcs.DISC.2022.49,
  author =	{Nataf, Ra\"{i}ssa and Goren, Guy and Moses, Yoram},
  title =	{{Brief Announcement: Null Messages, Information and Coordination}},
  booktitle =	{36th International Symposium on Distributed Computing (DISC 2022)},
  pages =	{49:1--49: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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2022.49},
  URN =		{urn:nbn:de:0030-drops-172409},
  doi =		{10.4230/LIPIcs.DISC.2022.49},
  annote =	{Keywords: null messages, fault tolerance, coordination, information flow}
}
Document
Tuning PoW with Hybrid Expenditure

Authors: Itay Tsabary, Alexander Spiegelman, and Ittay Eyal

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


Abstract
Proof of Work (PoW) is a Sybil-deterrence security mechanism. It introduces an external cost to system participation by requiring computational effort to perform actions. However, since its inception, a central challenge was to tune this cost. Initial designs for deterring spam email and DoS attacks applied overhead equally to honest participants and attackers. Requiring too little effort does not deter attacks, whereas too much encumbers honest participation. This might be the reason it was never widely adopted. Nakamoto overcame this trade-off in Bitcoin by distinguishing desired from malicious behavior and introducing internal rewards for the former. This mechanism gained popularity in securing permissionless cryptocurrencies, using virtual internally-minted tokens for rewards. However, in existing blockchain protocols the internal rewards directly compensate users for (almost) the same value of external expenses. Thus, as the token value soars, so does the PoW expenditure. Bitcoin PoW, for example, already expends as much electricity as Colombia or Switzerland. This amount of resource-guzzling is unsustainable, and hinders even wider adoption of these systems. As such, a prominent alternative named Proof of Stake (PoS) replaces the expenditure requirement with token possession. However, PoS is shun by many cryptocurrency projects, as it is only secure under qualitatively-different assumptions, and the resultant systems are not permissionless. In this work we present Hybrid Expenditure Blockchain (HEB), a novel PoW mechanism. HEB is a generalization of Nakamoto’s protocol that enables tuning the external expenditure by introducing a complementary internal-expenditure mechanism. Thus, for the first time, HEB decouples external expenditure from the reward value. We show a practical parameter choice by which HEB requires significantly less external consumption compare to Nakamoto’s protocol, its resilience against rational attackers is similar, and it retains the decentralized and permissionless nature of the system. Taking the Bitcoin ecosystem as an example, HEB cuts the electricity consumption by half.

Cite as

Itay Tsabary, Alexander Spiegelman, and Ittay Eyal. Tuning PoW with Hybrid Expenditure. In 3rd International Conference on Blockchain Economics, Security and Protocols (Tokenomics 2021). Open Access Series in Informatics (OASIcs), Volume 97, pp. 3:1-3:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{tsabary_et_al:OASIcs.Tokenomics.2021.3,
  author =	{Tsabary, Itay and Spiegelman, Alexander and Eyal, Ittay},
  title =	{{Tuning PoW with Hybrid Expenditure}},
  booktitle =	{3rd International Conference on Blockchain Economics, Security and Protocols (Tokenomics 2021)},
  pages =	{3:1--3:17},
  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-dev.dagstuhl.de/entities/document/10.4230/OASIcs.Tokenomics.2021.3},
  URN =		{urn:nbn:de:0030-drops-159008},
  doi =		{10.4230/OASIcs.Tokenomics.2021.3},
  annote =	{Keywords: Blockchain, Proof of work, Cryptocurrency, Environmental impact}
}
Document
PCPs and Instance Compression from a Cryptographic Lens

Authors: Liron Bronfman and Ron D. Rothblum

Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)


Abstract
Modern cryptography fundamentally relies on the assumption that the adversary trying to break the scheme is computationally bounded. This assumption lets us construct cryptographic protocols and primitives that are known to be impossible otherwise. In this work we explore the effect of bounding the adversary’s power in other information theoretic proof-systems and show how to use this assumption to bypass impossibility results. We first consider the question of constructing succinct PCPs. These are PCPs whose length is polynomial only in the length of the original NP witness (in contrast to standard PCPs whose length is proportional to the non-deterministic verification time). Unfortunately, succinct PCPs are known to be impossible to construct under standard complexity assumptions. Assuming the sub-exponential hardness of the learning with errors (LWE) problem, we construct succinct probabilistically checkable arguments or PCAs (Kalai and Raz 2009), which are PCPs in which soundness is guaranteed against efficiently generated false proofs. Our PCA construction is for every NP relation that can be verified by a small-depth circuit (e.g., SAT, clique, TSP, etc.) and in contrast to prior work is publicly verifiable and has constant query complexity. Curiously, we also show, as a proof-of-concept, that such publicly-verifiable PCAs can be used to derive hardness of approximation results. Second, we consider the notion of Instance Compression (Harnik and Naor, 2006). An instance compression scheme lets one compress, for example, a CNF formula φ on m variables and n ≫ m clauses to a new formula φ' with only poly(m) clauses, so that φ is satisfiable if and only if φ' is satisfiable. Instance compression has been shown to be closely related to succinct PCPs and is similarly highly unlikely to exist. We introduce a computational analog of instance compression in which we require that if φ is unsatisfiable then φ' is effectively unsatisfiable, in the sense that it is computationally infeasible to find a satisfying assignment for φ' (although such an assignment may exist). Assuming the same sub-exponential LWE assumption, we construct such computational instance compression schemes for every bounded-depth NP relation. As an application, this lets one compress k formulas ϕ₁,… ,ϕ_k into a single short formula ϕ that is effectively satisfiable if and only if at least one of the original formulas was satisfiable.

Cite as

Liron Bronfman and Ron D. Rothblum. PCPs and Instance Compression from a Cryptographic Lens. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 30:1-30:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{bronfman_et_al:LIPIcs.ITCS.2022.30,
  author =	{Bronfman, Liron and Rothblum, Ron D.},
  title =	{{PCPs and Instance Compression from a Cryptographic Lens}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{30:1--30:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.30},
  URN =		{urn:nbn:de:0030-drops-156269},
  doi =		{10.4230/LIPIcs.ITCS.2022.30},
  annote =	{Keywords: PCP, Succinct Arguments, Instance Compression}
}
Document
Brief Announcement
Brief Announcement: Probabilistic Indistinguishability and The Quality of Validity in Byzantine Agreement

Authors: Guy Goren, Yoram Moses, and Alexander Spiegelman

Published in: LIPIcs, Volume 209, 35th International Symposium on Distributed Computing (DISC 2021)


Abstract
Lower bounds and impossibility results in distributed computing are both intellectually challenging and practically important. Hundreds if not thousands of proofs appear in the literature, but surprisingly, the vast majority of them apply to deterministic algorithms only. Probabilistic protocols have been around for at least four decades and are receiving a lot of attention with the emergence of blockchain systems. Nonetheless, we are aware of only a handful of randomized lower bounds. In this work we provide a formal framework for reasoning about randomized distributed algorithms. We generalize the notion of indistinguishability, the most useful tool in deterministic lower bounds, to apply to a probabilistic setting. We apply this framework to prove a result of independent interest. Namely, we completely characterize the quality of decisions that protocols for a randomized multi-valued Consensus problem can guarantee in an asynchronous environment with Byzantine faults. We use the new notion to prove a lower bound on the guaranteed probability that honest parties will not decide on a possibly bogus value proposed by a malicious party. Finally, we show that the bound is tight by providing a protocol that matches it. This brief announcement consists of an introduction to the full paper [Guy Goren et al., 2020] by the same title. The interested reader is advised to consult the full paper for a detailed exposition.

Cite as

Guy Goren, Yoram Moses, and Alexander Spiegelman. Brief Announcement: Probabilistic Indistinguishability and The Quality of Validity in Byzantine Agreement. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 57:1-57:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{goren_et_al:LIPIcs.DISC.2021.57,
  author =	{Goren, Guy and Moses, Yoram and Spiegelman, Alexander},
  title =	{{Brief Announcement: Probabilistic Indistinguishability and The Quality of Validity in Byzantine Agreement}},
  booktitle =	{35th International Symposium on Distributed Computing (DISC 2021)},
  pages =	{57:1--57:4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-210-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{209},
  editor =	{Gilbert, Seth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2021.57},
  URN =		{urn:nbn:de:0030-drops-148596},
  doi =		{10.4230/LIPIcs.DISC.2021.57},
  annote =	{Keywords: Indistinguishability, probabilistic lower bounds, Byzantine agreement}
}
Document
Communication Efficient Self-Stabilizing Leader Election

Authors: Xavier Défago, Yuval Emek, Shay Kutten, Toshimitsu Masuzawa, and Yasumasa Tamura

Published in: LIPIcs, Volume 179, 34th International Symposium on Distributed Computing (DISC 2020)


Abstract
This paper presents a randomized self-stabilizing algorithm that elects a leader r in a general n-node undirected graph and constructs a spanning tree T rooted at r. The algorithm works under the synchronous message passing network model, assuming that the nodes know a linear upper bound on n and that each edge has a unique ID known to both its endpoints (or, alternatively, assuming the KT₁ model). The highlight of this algorithm is its superior communication efficiency: It is guaranteed to send a total of Õ (n) messages, each of constant size, till stabilization, while stabilizing in Õ (n) rounds, in expectation and with high probability. After stabilization, the algorithm sends at most one constant size message per round while communicating only over the (n - 1) edges of T. In all these aspects, the communication overhead of the new algorithm is far smaller than that of the existing (mostly deterministic) self-stabilizing leader election algorithms. The algorithm is relatively simple and relies mostly on known modules that are common in the fault free leader election literature; these modules are enhanced in various subtle ways in order to assemble them into a communication efficient self-stabilizing algorithm.

Cite as

Xavier Défago, Yuval Emek, Shay Kutten, Toshimitsu Masuzawa, and Yasumasa Tamura. Communication Efficient Self-Stabilizing Leader Election. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 11:1-11:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{defago_et_al:LIPIcs.DISC.2020.11,
  author =	{D\'{e}fago, Xavier and Emek, Yuval and Kutten, Shay and Masuzawa, Toshimitsu and Tamura, Yasumasa},
  title =	{{Communication Efficient Self-Stabilizing Leader Election}},
  booktitle =	{34th International Symposium on Distributed Computing (DISC 2020)},
  pages =	{11:1--11:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-168-9},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{179},
  editor =	{Attiya, Hagit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2020.11},
  URN =		{urn:nbn:de:0030-drops-130892},
  doi =		{10.4230/LIPIcs.DISC.2020.11},
  annote =	{Keywords: self-stabilization, leader election, communication overhead}
}
Document
Distributed Dispatching in the Parallel Server Model

Authors: Guy Goren, Shay Vargaftik, and Yoram Moses

Published in: LIPIcs, Volume 179, 34th International Symposium on Distributed Computing (DISC 2020)


Abstract
With the rapid increase in the size and volume of cloud services and data centers, architectures with multiple job dispatchers are quickly becoming the norm. Load balancing is a key element of such systems. Nevertheless, current solutions to load balancing in such systems admit a paradoxical behavior in which more accurate information regarding server queue lengths degrades performance due to herding and detrimental incast effects. Indeed, both in theory and in practice, there is a common doubt regarding the value of information in the context of multi-dispatcher load balancing. As a result, both researchers and system designers resort to more straightforward solutions, such as the power-of-two-choices to avoid worst-case scenarios, potentially sacrificing overall resource utilization and system performance. A principal focus of our investigation concerns the value of information about queue lengths in the multi-dispatcher setting. We argue that, at its core, load balancing with multiple dispatchers is a distributed computing task. In that light, we propose a new job dispatching approach, called Tidal Water Filling, which addresses the distributed nature of the system. Specifically, by incorporating the existence of other dispatchers into the decision-making process, our protocols outperform previous solutions in many scenarios. In particular, when the dispatchers have complete and accurate information regarding the server queue lengths, our policies significantly outperform all existing solutions.

Cite as

Guy Goren, Shay Vargaftik, and Yoram Moses. Distributed Dispatching in the Parallel Server Model. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 14:1-14:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{goren_et_al:LIPIcs.DISC.2020.14,
  author =	{Goren, Guy and Vargaftik, Shay and Moses, Yoram},
  title =	{{Distributed Dispatching in the Parallel Server Model}},
  booktitle =	{34th International Symposium on Distributed Computing (DISC 2020)},
  pages =	{14:1--14:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-168-9},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{179},
  editor =	{Attiya, Hagit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2020.14},
  URN =		{urn:nbn:de:0030-drops-130929},
  doi =		{10.4230/LIPIcs.DISC.2020.14},
  annote =	{Keywords: Distributed load balancing, Join the Shortest Queue, Tidal Water Filling,  Parallel Server Model}
}
Document
The Shapley Value of Tuples in Query Answering

Authors: Ester Livshits, Leopoldo Bertossi, Benny Kimelfeld, and Moshe Sebag

Published in: LIPIcs, Volume 155, 23rd International Conference on Database Theory (ICDT 2020)


Abstract
We investigate the application of the Shapley value to quantifying the contribution of a tuple to a query answer. The Shapley value is a widely known numerical measure in cooperative game theory and in many applications of game theory for assessing the contribution of a player to a coalition game. It has been established already in the 1950s, and is theoretically justified by being the very single wealth-distribution measure that satisfies some natural axioms. While this value has been investigated in several areas, it received little attention in data management. We study this measure in the context of conjunctive and aggregate queries by defining corresponding coalition games. We provide algorithmic and complexity-theoretic results on the computation of Shapley-based contributions to query answers; and for the hard cases we present approximation algorithms.

Cite as

Ester Livshits, Leopoldo Bertossi, Benny Kimelfeld, and Moshe Sebag. The Shapley Value of Tuples in Query Answering. In 23rd International Conference on Database Theory (ICDT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 155, pp. 20:1-20:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{livshits_et_al:LIPIcs.ICDT.2020.20,
  author =	{Livshits, Ester and Bertossi, Leopoldo and Kimelfeld, Benny and Sebag, Moshe},
  title =	{{The Shapley Value of Tuples in Query Answering}},
  booktitle =	{23rd International Conference on Database Theory (ICDT 2020)},
  pages =	{20:1--20:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-139-9},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{155},
  editor =	{Lutz, Carsten and Jung, Jean Christoph},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2020.20},
  URN =		{urn:nbn:de:0030-drops-119442},
  doi =		{10.4230/LIPIcs.ICDT.2020.20},
  annote =	{Keywords: Shapley value, query answering, conjunctive queries, aggregate queries}
}
Document
Hard Properties with (Very) Short PCPPs and Their Applications

Authors: Omri Ben-Eliezer, Eldar Fischer, Amit Levi, and Ron D. Rothblum

Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)


Abstract
We show that there exist properties that are maximally hard for testing, while still admitting PCPPs with a proof size very close to linear. Specifically, for every fixed ℓ, we construct a property P^(ℓ)⊆ {0,1}^n satisfying the following: Any testing algorithm for P^(ℓ) requires Ω(n) many queries, and yet P^(ℓ) has a constant query PCPP whose proof size is O(n⋅log^(ℓ)n), where log^(ℓ) denotes the ℓ times iterated log function (e.g., log^(2)n = log log n). The best previously known upper bound on the PCPP proof size for a maximally hard to test property was O(n⋅polylog(n)). As an immediate application, we obtain stronger separations between the standard testing model and both the tolerant testing model and the erasure-resilient testing model: for every fixed ℓ, we construct a property that has a constant-query tester, but requires Ω(n/log^(ℓ)(n)) queries for every tolerant or erasure-resilient tester.

Cite as

Omri Ben-Eliezer, Eldar Fischer, Amit Levi, and Ron D. Rothblum. Hard Properties with (Very) Short PCPPs and Their Applications. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 9:1-9:27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{beneliezer_et_al:LIPIcs.ITCS.2020.9,
  author =	{Ben-Eliezer, Omri and Fischer, Eldar and Levi, Amit and Rothblum, Ron D.},
  title =	{{Hard Properties with (Very) Short PCPPs and Their Applications}},
  booktitle =	{11th Innovations in Theoretical Computer Science Conference (ITCS 2020)},
  pages =	{9:1--9:27},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-134-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{151},
  editor =	{Vidick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.9},
  URN =		{urn:nbn:de:0030-drops-116949},
  doi =		{10.4230/LIPIcs.ITCS.2020.9},
  annote =	{Keywords: PCPP, Property testing, Tolerant testing, Erasure resilient testing, Randomized encoding, Coding theory}
}
Document
Optimal Distributed Covering Algorithms

Authors: Ran Ben-Basat, Guy Even, Ken-ichi Kawarabayashi, and Gregory Schwartzman

Published in: LIPIcs, Volume 146, 33rd International Symposium on Distributed Computing (DISC 2019)


Abstract
We present a time-optimal deterministic distributed algorithm for approximating a minimum weight vertex cover in hypergraphs of rank f. This problem is equivalent to the Minimum Weight Set Cover problem in which the frequency of every element is bounded by f. The approximation factor of our algorithm is (f+epsilon). Let Delta denote the maximum degree in the hypergraph. Our algorithm runs in the congest model and requires O(log{Delta} / log log Delta) rounds, for constants epsilon in (0,1] and f in N^+. This is the first distributed algorithm for this problem whose running time does not depend on the vertex weights nor the number of vertices. Thus adding another member to the exclusive family of provably optimal distributed algorithms. For constant values of f and epsilon, our algorithm improves over the (f+epsilon)-approximation algorithm of [Fabian Kuhn et al., 2006] whose running time is O(log Delta + log W), where W is the ratio between the largest and smallest vertex weights in the graph. Our algorithm also achieves an f-approximation for the problem in O(f log n) rounds, improving over the classical result of [Samir Khuller et al., 1994] that achieves a running time of O(f log^2 n). Finally, for weighted vertex cover (f=2) our algorithm achieves a deterministic running time of O(log n), matching the randomized previously best result of [Koufogiannakis and Young, 2011]. We also show that integer covering-programs can be reduced to the Minimum Weight Set Cover problem in the distributed setting. This allows us to achieve an (f+epsilon)-approximate integral solution in O((1+f/log n)* ((log Delta)/(log log Delta) + (f * log M)^{1.01}* log epsilon^{-1}* (log Delta)^{0.01})) rounds, where f bounds the number of variables in a constraint, Delta bounds the number of constraints a variable appears in, and M=max {1, ceil[1/a_{min}]}, where a_{min} is the smallest normalized constraint coefficient. This improves over the results of [Fabian Kuhn et al., 2006] for the integral case, which combined with rounding achieves the same guarantees in O(epsilon^{-4}* f^4 * log f * log(M * Delta)) rounds.

Cite as

Ran Ben-Basat, Guy Even, Ken-ichi Kawarabayashi, and Gregory Schwartzman. Optimal Distributed Covering Algorithms. In 33rd International Symposium on Distributed Computing (DISC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 146, pp. 5:1-5:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{benbasat_et_al:LIPIcs.DISC.2019.5,
  author =	{Ben-Basat, Ran and Even, Guy and Kawarabayashi, Ken-ichi and Schwartzman, Gregory},
  title =	{{Optimal Distributed Covering Algorithms}},
  booktitle =	{33rd International Symposium on Distributed Computing (DISC 2019)},
  pages =	{5:1--5:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-126-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{146},
  editor =	{Suomela, Jukka},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2019.5},
  URN =		{urn:nbn:de:0030-drops-113129},
  doi =		{10.4230/LIPIcs.DISC.2019.5},
  annote =	{Keywords: Distributed Algorithms, Approximation Algorithms, Vertex Cover, Set Cover}
}
Document
Parameterized Distributed Algorithms

Authors: Ran Ben-Basat, Ken-ichi Kawarabayashi, and Gregory Schwartzman

Published in: LIPIcs, Volume 146, 33rd International Symposium on Distributed Computing (DISC 2019)


Abstract
In this work, we initiate a thorough study of graph optimization problems parameterized by the output size in the distributed setting. In such a problem, an algorithm decides whether a solution of size bounded by k exists and if so, it finds one. We study fundamental problems, including Minimum Vertex Cover (MVC), Maximum Independent Set (MaxIS), Maximum Matching (MaxM), and many others, in both the LOCAL and CONGEST distributed computation models. We present lower bounds for the round complexity of solving parameterized problems in both models, together with optimal and near-optimal upper bounds. Our results extend beyond the scope of parameterized problems. We show that any LOCAL (1+epsilon)-approximation algorithm for the above problems must take Omega(epsilon^{-1}) rounds. Joined with the (epsilon^{-1}log n)^{O(1)} rounds algorithm of [Ghaffari et al., 2017] and the Omega (sqrt{(log n)/(log log n)}) lower bound of [Fabian Kuhn et al., 2016], the lower bounds match the upper bound up to polynomial factors in both parameters. We also show that our parameterized approach reduces the runtime of exact and approximate CONGEST algorithms for MVC and MaxM if the optimal solution is small, without knowing its size beforehand. Finally, we propose the first o(n^2) rounds CONGEST algorithms that approximate MVC within a factor strictly smaller than 2.

Cite as

Ran Ben-Basat, Ken-ichi Kawarabayashi, and Gregory Schwartzman. Parameterized Distributed Algorithms. In 33rd International Symposium on Distributed Computing (DISC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 146, pp. 6:1-6:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{benbasat_et_al:LIPIcs.DISC.2019.6,
  author =	{Ben-Basat, Ran and Kawarabayashi, Ken-ichi and Schwartzman, Gregory},
  title =	{{Parameterized Distributed Algorithms}},
  booktitle =	{33rd International Symposium on Distributed Computing (DISC 2019)},
  pages =	{6:1--6:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-126-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{146},
  editor =	{Suomela, Jukka},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2019.6},
  URN =		{urn:nbn:de:0030-drops-113135},
  doi =		{10.4230/LIPIcs.DISC.2019.6},
  annote =	{Keywords: Distributed Algorithms, Approximation Algorithms, Parameterized Algorithms}
}
Document
Recursive Programs for Document Spanners

Authors: Liat Peterfreund, Balder ten Cate, Ronald Fagin, and Benny Kimelfeld

Published in: LIPIcs, Volume 127, 22nd International Conference on Database Theory (ICDT 2019)


Abstract
A document spanner models a program for Information Extraction (IE) as a function that takes as input a text document (string over a finite alphabet) and produces a relation of spans (intervals in the document) over a predefined schema. A well-studied language for expressing spanners is that of the regular spanners: relational algebra over regex formulas, which are regular expressions with capture variables. Equivalently, the regular spanners are the ones expressible in non-recursive Datalog over regex formulas (which extract relations that constitute the extensional database). This paper explores the expressive power of recursive Datalog over regex formulas. We show that such programs can express precisely the document spanners computable in polynomial time. We compare this expressiveness to known formalisms such as the closure of regex formulas under the relational algebra and string equality. Finally, we extend our study to a recently proposed framework that generalizes both the relational model and the document spanners.

Cite as

Liat Peterfreund, Balder ten Cate, Ronald Fagin, and Benny Kimelfeld. Recursive Programs for Document Spanners. In 22nd International Conference on Database Theory (ICDT 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 127, pp. 13:1-13:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{peterfreund_et_al:LIPIcs.ICDT.2019.13,
  author =	{Peterfreund, Liat and Cate, Balder ten and Fagin, Ronald and Kimelfeld, Benny},
  title =	{{Recursive Programs for Document Spanners}},
  booktitle =	{22nd International Conference on Database Theory (ICDT 2019)},
  pages =	{13:1--13:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-101-6},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{127},
  editor =	{Barcelo, Pablo and Calautti, Marco},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2019.13},
  URN =		{urn:nbn:de:0030-drops-103155},
  doi =		{10.4230/LIPIcs.ICDT.2019.13},
  annote =	{Keywords: Information Extraction, Document Spanners, Polynomial Time, Recursion, Regular Expressions, Datalog}
}
  • Refine by Author
  • 3 Emek, Yuval
  • 3 Goren, Guy
  • 3 Moses, Yoram
  • 2 Ben-Basat, Ran
  • 2 Kawarabayashi, Ken-ichi
  • Show More...

  • Refine by Classification
  • 6 Theory of computation → Distributed algorithms
  • 3 Computing methodologies → Distributed algorithms
  • 2 Security and privacy → Distributed systems security
  • 2 Theory of computation → Interactive proof systems
  • 1 Computer systems organization → Fault-tolerant network topologies
  • Show More...

  • Refine by Keyword
  • 2 Approximation Algorithms
  • 2 Blockchain
  • 2 Distributed Algorithms
  • 1 Algorithms
  • 1 Asynchrony
  • Show More...

  • Refine by Type
  • 17 document

  • Refine by Publication Year
  • 5 2022
  • 4 2020
  • 3 2019
  • 2 2023
  • 1 2005
  • Show More...

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail