Search Results

Documents authored by Malkhi, Dahlia

Document
DOI: 10.4230/OASIcs.Tokenomics.2022.6
Maximal Extractable Value (MEV) Protection on a DAG

Authors: Dahlia Malkhi and Pawel Szalachowski

Published in: OASIcs, Volume 110, 4th International Conference on Blockchain Economics, Security and Protocols (Tokenomics 2022)

Abstract
Many cryptocurrency platforms are vulnerable to Maximal Extractable Value (MEV) attacks [Daian et al., 2020], where a malicious consensus leader can inject transactions or change the order of user transactions to maximize its profit. A promising line of research in MEV mitigation is to enhance the Byzantine fault tolerance (BFT) consensus core of blockchains by new functionalities, like hiding transaction contents, such that malicious parties cannot analyze and exploit them until they are ordered. An orthogonal line of research demonstrates excellent performance for BFT protocols designed around Directed Acyclic Graphs (DAG). They provide high throughput by keeping high network utilization, decoupling transactions' dissemination from their metadata ordering, and encoding consensus logic efficiently over a DAG representing a causal ordering of disseminated messages. This paper explains how to combine these two advances. It introduces a DAG-based protocol called Fino, that integrates MEV-resistance features into DAG-based BFT without delaying the steady spreading of transactions by the DAG transport and with zero message overhead. The scheme operates without complex secret share verifiability or recoverability, and avoids costly threshold encryption.
Cite as

Dahlia Malkhi and Pawel Szalachowski. Maximal Extractable Value (MEV) Protection on a DAG. In 4th International Conference on Blockchain Economics, Security and Protocols (Tokenomics 2022). Open Access Series in Informatics (OASIcs), Volume 110, pp. 6:1-6:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{malkhi_et_al:OASIcs.Tokenomics.2022.6,
  author =	{Malkhi, Dahlia and Szalachowski, Pawel},
  title =	{{Maximal Extractable Value (MEV) Protection on a DAG}},
  booktitle =	{4th International Conference on Blockchain Economics, Security and Protocols (Tokenomics 2022)},
  pages =	{6:1--6:17},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-274-7},
  ISSN =	{2190-6807},
  year =	{2023},
  volume =	{110},
  editor =	{Amoussou-Guenou, Yackolley and Kiayias, Aggelos and Verdier, Marianne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Tokenomics.2022.6},
  URN =		{urn:nbn:de:0030-drops-184231},
  doi =		{10.4230/OASIcs.Tokenomics.2022.6},
  annote =	{Keywords: DAG, MEV, consensus, BFT}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2021.7
Twins: BFT Systems Made Robust

Authors: Shehar Bano, Alberto Sonnino, Andrey Chursin, Dmitri Perelman, Zekun Li, Avery Ching, and Dahlia Malkhi

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

Abstract
This paper presents Twins, an automated unit test generator of Byzantine attacks. Twins implements three types of Byzantine behaviors: (i) leader equivocation, (ii) double voting, and (iii) losing internal state such as forgetting "locks" guarding voted values. To emulate interesting attacks by a Byzantine node, it instantiates twin copies of the node instead of one, giving both twins the same identities and network credentials. To the rest of the system, the twins appear indistinguishable from a single node behaving in a "questionable" manner. Twins can systematically generate Byzantine attack scenarios at scale, execute them in a controlled manner, and examine their behavior. Twins scenarios iterate over protocol rounds and vary the communication patterns among nodes. Twins runs in a production setting within DiemBFT where it can execute 44M Twins-generated scenarios daily. Whereas the system at hand did not manifest errors, subtle safety bugs that were deliberately injected for the purpose of validating the implementation of Twins itself were exposed within minutes. Twins can prevent developers from regressing correctness when updating the codebase, introducing new features, or performing routine maintenance tasks. Twins only requires a thin wrapper over DiemBFT, we thus envision other systems using it. Building on this idea, one new attack and several known attacks against other BFT protocols were materialized as Twins scenarios. In all cases, the target protocols break within fewer than a dozen protocol rounds, hence it is realistic for the Twins approach to expose the problems.
Cite as

Shehar Bano, Alberto Sonnino, Andrey Chursin, Dmitri Perelman, Zekun Li, Avery Ching, and Dahlia Malkhi. Twins: BFT Systems Made Robust. In 25th International Conference on Principles of Distributed Systems (OPODIS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 217, pp. 7:1-7:29, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bano_et_al:LIPIcs.OPODIS.2021.7,
  author =	{Bano, Shehar and Sonnino, Alberto and Chursin, Andrey and Perelman, Dmitri and Li, Zekun and Ching, Avery and Malkhi, Dahlia},
  title =	{{Twins: BFT Systems Made Robust}},
  booktitle =	{25th International Conference on Principles of Distributed Systems (OPODIS 2021)},
  pages =	{7:1--7:29},
  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.7},
  URN =		{urn:nbn:de:0030-drops-157825},
  doi =		{10.4230/LIPIcs.OPODIS.2021.7},
  annote =	{Keywords: Distributed Systems, Byzantine Fault Tolerance, Real-World Deployment}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.DISC.2021.2
Tech Transfer Stories and Takeaways (Invited Talk)

Authors: Dahlia Malkhi

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

Abstract
In this talk, I will share impressions from several industrial research project experiences that reached production and became part of successful products. I will go through four stories of how these systems transpired and their journey to impact. All of the stories are in the distributed computing arena, and more specifically, they revolve around the state-machine-replication paradigm. Yet, I hope that the take-aways from the experience of building foundations for these systems may be of interest and value to everyone, no matter the discipline.
Cite as

Dahlia Malkhi. Tech Transfer Stories and Takeaways (Invited Talk). In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, p. 2:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{malkhi:LIPIcs.DISC.2021.2,
  author =	{Malkhi, Dahlia},
  title =	{{Tech Transfer Stories and Takeaways}},
  booktitle =	{35th International Symposium on Distributed Computing (DISC 2021)},
  pages =	{2:1--2:1},
  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.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2021.2},
  URN =		{urn:nbn:de:0030-drops-148045},
  doi =		{10.4230/LIPIcs.DISC.2021.2},
  annote =	{Keywords: Tech Transfer, Distributed Systems}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2021.46
Brief Announcement: Twins – BFT Systems Made Robust

Authors: Shehar Bano, Alberto Sonnino, Andrey Chursin, Dmitri Perelman, Zekun Li, Avery Ching, and Dahlia Malkhi

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

Abstract
Twins is an effective strategy for generating test scenarios with Byzantine [Lamport et al., 1982] nodes in order to find flaws in Byzantine Fault Tolerant (BFT) systems. Twins finds flaws in the design or implementation of BFT protocols that may cause correctness issues. The main idea of Twins is the following: running twin instances of a node that use correct, unmodified code and share the same network identity and credentials allows to emulate most interesting Byzantine behaviors. Because a twin executes normal, unmodified node code, building Twins only requires a thin wrapper over an existing distributed system designed for Byzantine tolerance. To emulate material, interesting scenarios with Byzantine nodes, it instantiates one or more twin copies of the node, giving the twins the same identities and network credentials as the original node. To the rest of the system, the node and all its twins appear indistinguishable from a single node behaving in a "questionable" manner. This approach generates many interesting Byzantine behaviors, including equivocation, double voting, and losing internal state, while forgoing uninteresting behavior scenarios that can be filtered at the transport layer, such as producing semantically invalid messages. Building on configurations with twin nodes, Twins systematically generates scenarios with Byzantine nodes via enumeration over protocol rounds and communication patterns among nodes. Despite this being inherently exponential, one new flaw and several known flaws were materialized by Twins in the arena of BFT consensus protocols. In all cases, protocols break within fewer than a dozen protocol rounds, hence it is realistic for the Twins approach to expose the problems. In two of these cases, it took the community more than a decade to discover protocol flaws that Twins would have surfaced within minutes. Additionally, Twins has been incorporated into the continuous release testing process of a production setting (DiemBFT) in which it can execute 44M Twins-generated scenarios daily.
Cite as

Shehar Bano, Alberto Sonnino, Andrey Chursin, Dmitri Perelman, Zekun Li, Avery Ching, and Dahlia Malkhi. Brief Announcement: Twins – BFT Systems Made Robust. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 46:1-46:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{bano_et_al:LIPIcs.DISC.2021.46,
  author =	{Bano, Shehar and Sonnino, Alberto and Chursin, Andrey and Perelman, Dmitri and Li, Zekun and Ching, Avery and Malkhi, Dahlia},
  title =	{{Brief Announcement: Twins – BFT Systems Made Robust}},
  booktitle =	{35th International Symposium on Distributed Computing (DISC 2021)},
  pages =	{46:1--46: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.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2021.46},
  URN =		{urn:nbn:de:0030-drops-148485},
  doi =		{10.4230/LIPIcs.DISC.2021.46},
  annote =	{Keywords: Distributed Systems, Byzantine Fault Tolerance, Real-World Deployment}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2020.9
ACE: Abstract Consensus Encapsulation for Liveness Boosting of State Machine Replication

Authors: Alexander Spiegelman, Arik Rinberg, and Dahlia Malkhi

Published in: LIPIcs, Volume 184, 24th International Conference on Principles of Distributed Systems (OPODIS 2020)

Abstract
With the emergence of attack-prone cross-organization systems, providing asynchronous state machine replication (SMR) solutions is no longer a theoretical concern. This paper presents ACE, a framework for the design of such fault tolerant systems. Leveraging a known paradigm for randomized consensus solutions, ACE wraps existing practical solutions and real-life systems, boosting their liveness under adversarial conditions and, at the same time, promoting load balancing and fairness. Boosting is achieved without modifying the overall design or the engineering of these solutions. ACE is aimed at boosting the prevailing approach for practical fault tolerance. This approach, often named partial synchrony, is based on a leader-based paradigm: a good leader makes progress and a bad leader does no harm. The partial synchrony approach focuses on safety and forgoes liveness under targeted and dynamic attacks. Specifically, an attacker might block specific leaders, e.g., through a denial of service, to prevent progress. ACE provides boosting by running waves of parallel leaders and selecting a winning leader only retroactively, achieving boosting at a linear communication cost increase. ACE is agnostic to the fault model, inheriting it s failure model from the wrapped solution assumptions. As our evaluation shows, an asynchronous Byzantine fault tolerance (BFT) replication system built with ACE around an existing partially synchronous BFT protocol demonstrates reasonable slow-down compared with the base BFT protocol during faultless synchronous scenarios, yet exhibits significant speedup while the system is under attack.
Cite as

Alexander Spiegelman, Arik Rinberg, and Dahlia Malkhi. ACE: Abstract Consensus Encapsulation for Liveness Boosting of State Machine Replication. In 24th International Conference on Principles of Distributed Systems (OPODIS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 184, pp. 9:1-9:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{spiegelman_et_al:LIPIcs.OPODIS.2020.9,
  author =	{Spiegelman, Alexander and Rinberg, Arik and Malkhi, Dahlia},
  title =	{{ACE: Abstract Consensus Encapsulation for Liveness Boosting of State Machine Replication}},
  booktitle =	{24th International Conference on Principles of Distributed Systems (OPODIS 2020)},
  pages =	{9:1--9:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-176-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{184},
  editor =	{Bramas, Quentin and Oshman, Rotem and Romano, Paolo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2020.9},
  URN =		{urn:nbn:de:0030-drops-134948},
  doi =		{10.4230/LIPIcs.OPODIS.2020.9},
  annote =	{Keywords: Framework, Asynchronous, Consensus boosting, State Machine Replication}
}
Document
Keynote Lecture
DOI: 10.4230/OASIcs.Tokenomics.2019.2
Flexible BFT: Separating BFT Protocol Design from the Fault Model (Keynote Lecture)

Authors: Dahlia Malkhi

Published in: OASIcs, Volume 71, International Conference on Blockchain Economics, Security and Protocols (Tokenomics 2019)

Abstract
Byzantine Fault Tolerant (BFT) protocols designed for building replicated services collapse if deployed under settings that differ from the fault model they are designed for. For example, in a partial-synchrony model, a known lower bound for BFT is 1/3. Optimal-resilience solutions completely break if the fraction of Byzantine faults exceeds 1/3. The only way we know to achieve > 1/3 resilience is by assuming synchrony, but this requires the protocol to be designed with that assumption. Flexible BFT is a new approach to BFT protocol design that separates between the fault model and the solution. Clients in Flexible BFT specify (i) the adversarial threshold they need to tolerate, and (ii) whether they believe in synchrony (and the presumed bound on transmission delays). We present a Flexible BFT solution that simultaneously supports different clients, who differ simply by the number of messages and/or time the clients are willing to wait for. At an even finer grain, Flexible BFT supports under the same solution high-value and low-value transactions, each tolerating a different threat model.
Cite as

Dahlia Malkhi. Flexible BFT: Separating BFT Protocol Design from the Fault Model (Keynote Lecture). In International Conference on Blockchain Economics, Security and Protocols (Tokenomics 2019). Open Access Series in Informatics (OASIcs), Volume 71, p. 2:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{malkhi:OASIcs.Tokenomics.2019.2,
  author =	{Malkhi, Dahlia},
  title =	{{Flexible BFT: Separating BFT Protocol Design from the Fault Model}},
  booktitle =	{International Conference on Blockchain Economics, Security and Protocols (Tokenomics 2019)},
  pages =	{2:1--2:1},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-108-5},
  ISSN =	{2190-6807},
  year =	{2020},
  volume =	{71},
  editor =	{Danos, Vincent and Herlihy, Maurice and Potop-Butucaru, Maria and Prat, Julien and Tucci-Piergiovanni, Sara},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Tokenomics.2019.2},
  URN =		{urn:nbn:de:0030-drops-119660},
  doi =		{10.4230/OASIcs.Tokenomics.2019.2},
  annote =	{Keywords: Byzantine fault-tolerance, blockchains}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2019.4
FairLedger: A Fair Blockchain Protocol for Financial Institutions

Authors: Kfir Lev-Ari, Alexander Spiegelman, Idit Keidar, and Dahlia Malkhi

Published in: LIPIcs, Volume 153, 23rd International Conference on Principles of Distributed Systems (OPODIS 2019)

Abstract
Financial institutions nowadays are looking into technologies for permissioned blockchains. A major effort in this direction is Hyperledger, an open source project hosted by the Linux Foundation and backed by a consortium of over a hundred companies. A key component in permissioned blockchain protocols is a byzantine fault tolerant (BFT) consensus engine that orders transactions. However, currently available BFT solutions in Hyperledger (as well as in the literature at large) are inadequate for financial settings; they are not designed to ensure fairness or to tolerate the selfish behavior that inevitably arises when financial institutions strive to maximize their own profit. We present FairLedger, a permissioned BFT blockchain protocol, which is fair, deigned to deal with rational behavior, and, no less important, easy to understand and implement. Our secret sauce is a new communication abstraction called detectable all-to-all (DA2A), which allows us to detect players (byzantine or rational) that deviate from the protocol and punish them. We implement FairLedger in the Hyperledger open source project using the Iroha framework - one of the biggest projects therein. To evaluate FairLegder’s performance, we also implement it in the PBFT framework and compare the two protocols. Our results show that in failure-free scenarios in wide-area settings, FairLedger achieves better throughput than both Iroha’s implementation and PBFT.
Cite as

Kfir Lev-Ari, Alexander Spiegelman, Idit Keidar, and Dahlia Malkhi. FairLedger: A Fair Blockchain Protocol for Financial Institutions. In 23rd International Conference on Principles of Distributed Systems (OPODIS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 153, pp. 4:1-4:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{levari_et_al:LIPIcs.OPODIS.2019.4,
  author =	{Lev-Ari, Kfir and Spiegelman, Alexander and Keidar, Idit and Malkhi, Dahlia},
  title =	{{FairLedger: A Fair Blockchain Protocol for Financial Institutions}},
  booktitle =	{23rd International Conference on Principles of Distributed Systems (OPODIS 2019)},
  pages =	{4:1--4:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-133-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{153},
  editor =	{Felber, Pascal and Friedman, Roy and Gilbert, Seth and Miller, Avery},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2019.4},
  URN =		{urn:nbn:de:0030-drops-117904},
  doi =		{10.4230/LIPIcs.OPODIS.2019.4},
  annote =	{Keywords: Blockchain, Fairness, Byzantine fault tolerance, Rational players, Equilibrium}
}
Document
DOI: 10.4230/LIPIcs.DISC.2018.7
State Machine Replication Is More Expensive Than Consensus

Authors: Karolos Antoniadis, Rachid Guerraoui, Dahlia Malkhi, and Dragos-Adrian Seredinschi

Published in: LIPIcs, Volume 121, 32nd International Symposium on Distributed Computing (DISC 2018)

Abstract
Consensus and State Machine Replication (SMR) are generally considered to be equivalent problems. In certain system models, indeed, the two problems are computationally equivalent: any solution to the former problem leads to a solution to the latter, and vice versa. In this paper, we study the relation between consensus and SMR from a complexity perspective. We find that, surprisingly, completing an SMR command can be more expensive than solving a consensus instance. Specifically, given a synchronous system model where every instance of consensus always terminates in constant time, completing an SMR command does not necessarily terminate in constant time. This result naturally extends to partially synchronous models. Besides theoretical interest, our result also corresponds to practical phenomena we identify empirically. We experiment with two well-known SMR implementations (Multi-Paxos and Raft) and show that, indeed, SMR is more expensive than consensus in practice. One important implication of our result is that - even under synchrony conditions - no SMR algorithm can ensure bounded response times.
Cite as

Karolos Antoniadis, Rachid Guerraoui, Dahlia Malkhi, and Dragos-Adrian Seredinschi. State Machine Replication Is More Expensive Than Consensus. In 32nd International Symposium on Distributed Computing (DISC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 121, pp. 7:1-7:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{antoniadis_et_al:LIPIcs.DISC.2018.7,
  author =	{Antoniadis, Karolos and Guerraoui, Rachid and Malkhi, Dahlia and Seredinschi, Dragos-Adrian},
  title =	{{State Machine Replication Is More Expensive Than Consensus}},
  booktitle =	{32nd International Symposium on Distributed Computing (DISC 2018)},
  pages =	{7:1--7:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-092-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{121},
  editor =	{Schmid, Ulrich and Widder, Josef},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2018.7},
  URN =		{urn:nbn:de:0030-drops-97961},
  doi =		{10.4230/LIPIcs.DISC.2018.7},
  annote =	{Keywords: Consensus, State machine replication, Synchronous model}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2017.25
Solida: A Blockchain Protocol Based on Reconfigurable Byzantine Consensus

Authors: Ittai Abraham, Dahlia Malkhi, Kartik Nayak, Ling Ren, and Alexander Spiegelman

Published in: LIPIcs, Volume 95, 21st International Conference on Principles of Distributed Systems (OPODIS 2017)

Abstract
The decentralized cryptocurrency Bitcoin has experienced great success but also encountered many challenges. One of the challenges has been the long confirmation time. Another chal- lenge is the lack of incentives at certain steps of the protocol, raising concerns for transaction withholding, selfish mining, etc. To address these challenges, we propose Solida, a decentralized blockchain protocol based on reconfigurable Byzantine consensus augmented by proof-of-work. Solida improves on Bitcoin in confirmation time, and provides safety and liveness assuming the adversary control less than (roughly) one-third of the total mining power.
Cite as

Ittai Abraham, Dahlia Malkhi, Kartik Nayak, Ling Ren, and Alexander Spiegelman. Solida: A Blockchain Protocol Based on Reconfigurable Byzantine Consensus. In 21st International Conference on Principles of Distributed Systems (OPODIS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 95, pp. 25:1-25:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{abraham_et_al:LIPIcs.OPODIS.2017.25,
  author =	{Abraham, Ittai and Malkhi, Dahlia and Nayak, Kartik and Ren, Ling and Spiegelman, Alexander},
  title =	{{Solida: A Blockchain Protocol Based on Reconfigurable Byzantine Consensus}},
  booktitle =	{21st International Conference on Principles of Distributed Systems (OPODIS 2017)},
  pages =	{25:1--25:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-061-3},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{95},
  editor =	{Aspnes, James and Bessani, Alysson and Felber, Pascal and Leit\~{a}o, Jo\~{a}o},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2017.25},
  URN =		{urn:nbn:de:0030-drops-86409},
  doi =		{10.4230/LIPIcs.OPODIS.2017.25},
  annote =	{Keywords: Cryptocurrency, Blockchain, Byzantine fault tolerance, Reconfiguration}
}
Document
DOI: 10.4230/LIPIcs.DISC.2017.40
Dynamic Reconfiguration: Abstraction and Optimal Asynchronous Solution

Authors: Alexander Spiegelman, Idit Keidar, and Dahlia Malkhi

Published in: LIPIcs, Volume 91, 31st International Symposium on Distributed Computing (DISC 2017)

Abstract
Providing clean and efficient foundations and tools for reconfiguration is a crucial enabler for distributed system management today. This work takes a step towards developing such foundations. It considers classic fault-tolerant atomic objects emulated on top of a static set of fault-prone servers, and turns them into dynamic ones. The specification of a dynamic object extends the corresponding static (non-dynamic) one with an API for changing the underlying set of fault-prone servers. Thus, in a dynamic model, an object can start in some configuration and continue in a different one. Its liveness is preserved through the reconfigurations it undergoes, tolerating a versatile set of faults as it shifts from one configuration to another. In this paper we present a general abstraction for asynchronous reconfiguration, and exemplify its usefulness for building two dynamic objects: a read/write register and a max-register. We first define a dynamic model with a clean failure condition that allows an administrator to reconfigure the system and switch off a server once the reconfiguration operation removing it completes. We then define the Reconfiguration abstraction and show how it can be used to build dynamic registers and max-registers. Finally, we give an optimal asynchronous algorithm implementing the Reconfiguration abstraction, which in turn leads to the first asynchronous (consensus-free) dynamic register emulation with optimal complexity. More concretely, faced with n requests for configuration changes, the number of configurations that the dynamic register is implemented over is n; and the complexity of each client operation is O(n).
Cite as

Alexander Spiegelman, Idit Keidar, and Dahlia Malkhi. Dynamic Reconfiguration: Abstraction and Optimal Asynchronous Solution. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 40:1-40:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{spiegelman_et_al:LIPIcs.DISC.2017.40,
  author =	{Spiegelman, Alexander and Keidar, Idit and Malkhi, Dahlia},
  title =	{{Dynamic Reconfiguration: Abstraction and Optimal Asynchronous Solution}},
  booktitle =	{31st International Symposium on Distributed Computing (DISC 2017)},
  pages =	{40:1--40:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-053-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{91},
  editor =	{Richa, Andr\'{e}a},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.40},
  URN =		{urn:nbn:de:0030-drops-79673},
  doi =		{10.4230/LIPIcs.DISC.2017.40},
  annote =	{Keywords: Reconfiguration, Dynamic Objects, Optimal Algorithm}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2016.25
Flexible Paxos: Quorum Intersection Revisited

Authors: Heidi Howard, Dahlia Malkhi, and Alexander Spiegelman

Published in: LIPIcs, Volume 70, 20th International Conference on Principles of Distributed Systems (OPODIS 2016)

Abstract
Distributed consensus is integral to modern distributed systems. The widely adopted Paxos algorithm uses two phases, each requiring majority agreement, to reliably reach consensus. In this paper, we demonstrate that Paxos, which lies at the foundation of many production systems, is conservative. Specifically, we observe that each of the phases of Paxos may use non-intersecting quorums. Majority quorums are not necessary as intersection is required only across phases. Using this weakening of the requirements made in the original formulation, we propose Flexible Paxos, which generalizes over the Paxos algorithm to provide flexible quorums. We show that Flexible Paxos is safe, e cient and easy to utilize in existing distributed systems. We discuss far reaching implications of this result. For example, improved availability results from reducing the size of second phase quorums by one when the system size is even, while keeping majority quorums in the first phase. Another example is improved throughput of replication by using much smaller phase 2 quorums, while increasing the leader election (phase 1) quorums. Finally, non intersecting quorums in either first or second phases may enhance the efficiency of both.
Cite as

Heidi Howard, Dahlia Malkhi, and Alexander Spiegelman. Flexible Paxos: Quorum Intersection Revisited. In 20th International Conference on Principles of Distributed Systems (OPODIS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 70, pp. 25:1-25:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{howard_et_al:LIPIcs.OPODIS.2016.25,
  author =	{Howard, Heidi and Malkhi, Dahlia and Spiegelman, Alexander},
  title =	{{Flexible Paxos: Quorum Intersection Revisited}},
  booktitle =	{20th International Conference on Principles of Distributed Systems (OPODIS 2016)},
  pages =	{25:1--25:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-031-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{70},
  editor =	{Fatourou, Panagiota and Jim\'{e}nez, Ernesto and Pedone, Fernando},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2016.25},
  URN =		{urn:nbn:de:0030-drops-70947},
  doi =		{10.4230/LIPIcs.OPODIS.2016.25},
  annote =	{Keywords: Paxos, Distributed Consensus, Quorums}
}
Document
Tutorial
DOI: 10.4230/LIPIcs.OPODIS.2015.2
Dynamic Reconfiguration: A Tutorial (Tutorial)

Authors: Alexander Spiegelman, Idit Keidar, and Dahlia Malkhi

Published in: LIPIcs, Volume 46, 19th International Conference on Principles of Distributed Systems (OPODIS 2015)

Abstract
A key challenge for distributed systems is the problem of reconfiguration. Clearly, any production storage system that provides data reliability and availability for long periods must be able to reconfigure in order to remove failed or old servers and add healthy or new ones. This is far from trivial since we do not want the reconfiguration management to be centralized or cause a system shutdown. In this tutorial we look into existing reconfigurable storage algorithms. We propose a common model and failure condition capturing their guarantees. We define a reconfiguration problem around which dynamic object solutions may be designed. To demonstrate its strength, we use it to implement dynamic atomic storage. We present a generic framework for solving the reconfiguration problem, show how to recast existing algorithms in terms of this framework, and compare among them.
Cite as

Alexander Spiegelman, Idit Keidar, and Dahlia Malkhi. Dynamic Reconfiguration: A Tutorial (Tutorial). In 19th International Conference on Principles of Distributed Systems (OPODIS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 46, pp. 2:1-2:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{spiegelman_et_al:LIPIcs.OPODIS.2015.2,
  author =	{Spiegelman, Alexander and Keidar, Idit and Malkhi, Dahlia},
  title =	{{Dynamic Reconfiguration: A Tutorial}},
  booktitle =	{19th International Conference on Principles of Distributed Systems (OPODIS 2015)},
  pages =	{2:1--2:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-98-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{46},
  editor =	{Anceaume, Emmanuelle and Cachin, Christian and Potop-Butucaru, Maria},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2015.2},
  URN =		{urn:nbn:de:0030-drops-65938},
  doi =		{10.4230/LIPIcs.OPODIS.2015.2},
  annote =	{Keywords: Dynamic reconfiguration}
}
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
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact