2026-07-21T14:16:29Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25175 2026-03-19T12:59:11Z ddc:004 open_access

From Principles to Practice: Algorithmic Insights from Building the Internet Computer (Invited Talk) Pignolet, Yvonne-Anne Internet Computer Protocol blockchain state machine replication Byzantine fault tolerance 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Yvonne-Anne Pignolet 2026 Is Part Of LIPIcs, Volume 361, 29th International Conference on Principles of Distributed Systems (OPODIS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.OPODIS.2025.2 urn:nbn:de:0030-drops-251756 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2025.2 eng https://creativecommons.org/licenses/by/4.0/legalcode