Search Results

Documents authored by Pignolet, Yvonne-Anne

Document
Invited Talk
DOI: 10.4230/LIPIcs.OPODIS.2025.2
From Principles to Practice: Algorithmic Insights from Building the Internet Computer (Invited Talk)

Authors: Yvonne-Anne Pignolet

Published in: LIPIcs, Volume 361, 29th International Conference on Principles of Distributed Systems (OPODIS 2025)

Abstract
The theoretical bedrock of distributed computing rests on foundational primitives: peer-to-peer protocols, Byzantine fault tolerance, state machine replication. But what happens when these principles are stretched to a global, evolving, decentralized compute platform intended to host arbitrary applications? For the past seven years, our work has been dedicated to answering that question through the Internet Computer (IC), a public blockchain network designed for large-scale, general-purpose computation. The IC acts as a stateful serverless cloud[Maksym Arutyunyan et al., 2023], running over 900K applications for millions of users by implementing the Internet Computer Protocol (ICP)[Jan Camenisch et al., 2022] in a sharded, Byzantine-fault-tolerant setup. This talk explores the algorithmic insights gained from this journey. We will confront where our cherished theoretical models were challenged and had to be radically adapted, composed, or re-imagined. Specifically, we will dive into core problems like: - Scalable orchestration: Asynchronous and trustless composition of independent state machines. - Taming Non-Determinism: Designing protocols that allow deterministic replicated state machines to securely query external data. - The Paradox of Immutability: Enabling stateful upgrades for decentralized applications and even the underlying protocol stack without sacrificing security. I will share the successful design patterns that emerged, detail which core protocols stood the test of time, and which others we overhauled. Finally, I will discuss the hard and sometimes surprising trade-offs we made and pose open research questions to address when designing the next generation of decentralized systems.
Cite as

Yvonne-Anne Pignolet. From Principles to Practice: Algorithmic Insights from Building the Internet Computer (Invited Talk). In 29th International Conference on Principles of Distributed Systems (OPODIS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 361, p. 2:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{pignolet:LIPIcs.OPODIS.2025.2,
  author =	{Pignolet, Yvonne-Anne},
  title =	{{From Principles to Practice: Algorithmic Insights from Building the Internet Computer}},
  booktitle =	{29th International Conference on Principles of Distributed Systems (OPODIS 2025)},
  pages =	{2:1--2:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-409-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{361},
  editor =	{Arusoaie, Andrei and Onica, Emanuel and Spear, Michael 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/LIPIcs.OPODIS.2025.2},
  URN =		{urn:nbn:de:0030-drops-251756},
  doi =		{10.4230/LIPIcs.OPODIS.2025.2},
  annote =	{Keywords: Internet Computer Protocol, blockchain, state machine replication, Byzantine fault tolerance}
}
Document
DOI: 10.4230/LIPIcs.DISC.2021.28
Permissionless and Asynchronous Asset Transfer

Authors: Petr Kuznetsov, Yvonne-Anne Pignolet, Pavel Ponomarev, and Andrei Tonkikh

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

Abstract
Most modern asset transfer systems use consensus to maintain a totally ordered chain of transactions. It was recently shown that consensus is not always necessary for implementing asset transfer. More efficient, asynchronous solutions can be built using reliable broadcast instead of consensus. This approach has been originally used in the closed (permissioned) setting. In this paper, we extend it to the open (permissionless) environment. We present {Pastro}, a permissionless and asynchronous asset-transfer implementation, in which quorum systems, traditionally used in reliable broadcast, are replaced with a weighted Proof-of-Stake mechanism. {Pastro} tolerates a dynamic adversary that is able to adaptively corrupt participants based on the assets owned by them.
Cite as

Petr Kuznetsov, Yvonne-Anne Pignolet, Pavel Ponomarev, and Andrei Tonkikh. Permissionless and Asynchronous Asset Transfer. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 28:1-28:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{kuznetsov_et_al:LIPIcs.DISC.2021.28,
  author =	{Kuznetsov, Petr and Pignolet, Yvonne-Anne and Ponomarev, Pavel and Tonkikh, Andrei},
  title =	{{Permissionless and Asynchronous Asset Transfer}},
  booktitle =	{35th International Symposium on Distributed Computing (DISC 2021)},
  pages =	{28:1--28:19},
  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.28},
  URN =		{urn:nbn:de:0030-drops-148307},
  doi =		{10.4230/LIPIcs.DISC.2021.28},
  annote =	{Keywords: Asset transfer, permissionless, asynchronous, dynamic adversary}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2020.23
Dynamic Byzantine Reliable Broadcast

Authors: Rachid Guerraoui, Jovan Komatovic, Petr Kuznetsov, Yvonne-Anne Pignolet, Dragos-Adrian Seredinschi, and Andrei Tonkikh

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

Abstract
Reliable broadcast is a communication primitive guaranteeing, intuitively, that all processes in a distributed system deliver the same set of messages. The reason why this primitive is appealing is twofold: (i) we can implement it deterministically in a completely asynchronous environment, unlike stronger primitives like consensus and total-order broadcast, and yet (ii) reliable broadcast is powerful enough to implement important applications like payment systems. The problem we tackle in this paper is that of dynamic reliable broadcast, i.e., enabling processes to join or leave the system. This property is desirable for long-lived applications (aiming to be highly available), yet has been precluded in previous asynchronous reliable broadcast protocols. We study this property in a general adversarial (i.e., Byzantine) environment. We introduce the first specification of a dynamic Byzantine reliable broadcast (dbrb) primitive that is amenable to an asynchronous implementation. We then present an algorithm implementing this specification in an asynchronous network. Our dbrb algorithm ensures that if any correct process in the system broadcasts a message, then every correct process delivers that message unless it leaves the system. Moreover, if a correct process delivers a message, then every correct process that has not expressed its will to leave the system delivers that message. We assume that more than 2/3 of processes in the system are correct at all times, which is tight in our context. We also show that if only one process in the system can fail - and it can fail only by crashing - then it is impossible to implement a stronger primitive, ensuring that if any correct process in the system broadcasts or delivers a message, then every correct process in the system delivers that message - including those that leave.
Cite as

Rachid Guerraoui, Jovan Komatovic, Petr Kuznetsov, Yvonne-Anne Pignolet, Dragos-Adrian Seredinschi, and Andrei Tonkikh. Dynamic Byzantine Reliable Broadcast. In 24th International Conference on Principles of Distributed Systems (OPODIS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 184, pp. 23:1-23:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{guerraoui_et_al:LIPIcs.OPODIS.2020.23,
  author =	{Guerraoui, Rachid and Komatovic, Jovan and Kuznetsov, Petr and Pignolet, Yvonne-Anne and Seredinschi, Dragos-Adrian and Tonkikh, Andrei},
  title =	{{Dynamic Byzantine Reliable Broadcast}},
  booktitle =	{24th International Conference on Principles of Distributed Systems (OPODIS 2020)},
  pages =	{23:1--23: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.23},
  URN =		{urn:nbn:de:0030-drops-135087},
  doi =		{10.4230/LIPIcs.OPODIS.2020.23},
  annote =	{Keywords: Byzantine reliable broadcast, deterministic distributed algorithms, dynamic distributed systems}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2020.46
Brief Announcement: What Can(Not) Be Perfectly Rerouted Locally

Authors: Klaus-Tycho Foerster, Juho Hirvonen, Yvonne-Anne Pignolet, Stefan Schmid, and Gilles Tredan

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

Abstract
In order to provide a high resilience and to react quickly to link failures, modern computer networks support fully decentralized flow rerouting, also known as local fast failover. In a nutshell, the task of a local fast failover algorithm is to pre-define fast failover rules for each node using locally available information only. Ideally, such a local fast failover algorithm provides a perfect resilience deterministically: a packet emitted from any source can reach any target, as long as the underlying network remains connected. Feigenbaum et al. showed [Feigenbaum and others, 2012] that it is not always possible to provide perfect resilience; on the positive side, the authors also presented an efficient algorithm which achieves at least 1-resilience, tolerating a single failure in any network. Interestingly, not much more is known currently about the feasibility of perfect resilience. This brief announcement revisits perfect resilience with local fast failover, both in a model where the source can and cannot be used for forwarding decisions. By establishing a connection between graph minors and resilience, we prove that it is impossible to achieve perfect resilience on any non-planar graph; On the positive side, we can derive perfect resilience for outerplanar and some planar graphs.
Cite as

Klaus-Tycho Foerster, Juho Hirvonen, Yvonne-Anne Pignolet, Stefan Schmid, and Gilles Tredan. Brief Announcement: What Can(Not) Be Perfectly Rerouted Locally. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 46:1-46:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{foerster_et_al:LIPIcs.DISC.2020.46,
  author =	{Foerster, Klaus-Tycho and Hirvonen, Juho and Pignolet, Yvonne-Anne and Schmid, Stefan and Tredan, Gilles},
  title =	{{Brief Announcement: What Can(Not) Be Perfectly Rerouted Locally}},
  booktitle =	{34th International Symposium on Distributed Computing (DISC 2020)},
  pages =	{46:1--46:3},
  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.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2020.46},
  URN =		{urn:nbn:de:0030-drops-131244},
  doi =		{10.4230/LIPIcs.DISC.2020.46},
  annote =	{Keywords: Resilience, Local Failover}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2018.19
You Only Live Multiple Times: A Blackbox Solution for Reusing Crash-Stop Algorithms In Realistic Crash-Recovery Settings

Authors: David Kozhaya, Ognjen Maric, and Yvonne-Anne Pignolet

Published in: LIPIcs, Volume 125, 22nd International Conference on Principles of Distributed Systems (OPODIS 2018)

Abstract
Distributed agreement-based algorithms are often specified in a crash-stop asynchronous model augmented by Chandra and Toueg's unreliable failure detectors. In such models, correct nodes stay up forever, incorrect nodes eventually crash and remain down forever, and failure detectors behave correctly forever eventually, However, in reality, nodes as well as communication links both crash and recover without deterministic guarantees to remain in some state forever. In this paper, we capture this realistic temporary and probabilitic behaviour in a simple new system model. Moreover, we identify a large algorithm class for which we devise a property-preserving transformation. Using this transformation, many algorithms written for the asynchronous crash-stop model run correctly and unchanged in real systems.
Cite as

David Kozhaya, Ognjen Maric, and Yvonne-Anne Pignolet. You Only Live Multiple Times: A Blackbox Solution for Reusing Crash-Stop Algorithms In Realistic Crash-Recovery Settings. In 22nd International Conference on Principles of Distributed Systems (OPODIS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 125, pp. 19:1-19:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{kozhaya_et_al:LIPIcs.OPODIS.2018.19,
  author =	{Kozhaya, David and Maric, Ognjen and Pignolet, Yvonne-Anne},
  title =	{{You Only Live Multiple Times: A Blackbox Solution for Reusing Crash-Stop Algorithms In Realistic Crash-Recovery Settings}},
  booktitle =	{22nd International Conference on Principles of Distributed Systems (OPODIS 2018)},
  pages =	{19:1--19:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-098-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{125},
  editor =	{Cao, Jiannong and Ellen, Faith and Rodrigues, Luis and Ferreira, Bernardo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2018.19},
  URN =		{urn:nbn:de:0030-drops-100792},
  doi =		{10.4230/LIPIcs.OPODIS.2018.19},
  annote =	{Keywords: Crash recovery, consensus, asynchrony}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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