Accompanist: A Runtime for Resilient Choreographic Programming DOI: XXXXXXX.XXXXXXX
Viktor Strate Kløvedal, Dan Plyukhin, Marco Peressotti, Fabrizio Montesi · 2026
Read Accompanist: A Runtime for Resilient Choreographic Programming DOI: XXXXXXX.XXXXXXX by Viktor Strate Kløvedal, Dan Plyukhin, Marco Peressotti, Fabrizio Montesi (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-20942.txt.
Introduction
Kløvedal and co-authors present Accompanist, a runtime that makes choreographic programs fault tolerant. Services usually coordinate through an orchestrator, whose central state eases recovery. Hardware limits and security rules can rule that option out. Choreographic programming gives a global view without a center, but assumes reliable networks. Accompanist instead replays computation at run time to mask faults, which keeps programs simple. It targets the Choral language and runs as sidecars next to existing services, with a correctness proof.
Catalog record
| CREATOR | Viktor Strate Kløvedal, Dan Plyukhin, Marco Peressotti, Fabrizio Montesi |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 85224 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.20942
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Accompanist: A Runtime for Resilient Choreographic Programming DOI: XXXXXXX.XXXXXXX Viktor Strate Kløvedal, Dan Plyukhin, Marco Peressotti, Fabrizio Montesi Abstract . In service-oriented architecture, services coordinate in one of two ways: directly, using point-to-point communication, or indirectly, through an intermediary called the orchestrator . Orchestrators tend to be more popular because their local state is a ‘single source of truth’ for the status of ongoing workflows, which simplifies fault recovery and rollback for distributed transactions that use the ‘saga’ pattern. But orchestration is not always an option because of hardware constraints and security policies. Without a central orchestrator, resilient saga transactions are hard to implement correctly. A natural idea is to use choreographic programming , a paradigm that brings the ‘global view’ of orchestrators to a decentralised setting. Unfortunately, choreographic programming relies on strong assumptions about network reliability and service uptime that often do not hold. Recent work weakens some of these assumptions with ‘failure-aware’ language features, but these features make programs more complex. We propose a complementary approach: to co-design the programming interface with a customizable runtime that can replay computation to mask faults. Our approach keeps programs simple, does not require modifying the compiler, and lends itself to a clean separation of concerns in formal proofs. We present Accompanist , a resilient runtime for the Choral choreographic programming language. With Accompanist , programmers can implement decentralised saga transactions as choreographic programs and deploy the compiled code to ‘sidecars’ that run alongside services in a pre-existing codebase. Our key assumptions are that choreographic programs should be deterministic, transactions within a saga should be idempotent, and messages should be written to a durable message queue. Based on these assumptions, we present a formal model and prove that target code is correct-by-construction: choreographic sagas are deadlock-free, terminate under bounded restarts, and upon termination their participants have all succeeded or all invoked compensating transactions to undo the workflow. avacode]java bgcolor=codebg, fontsize= , horalcode]’choral.py:ChoralLexer -x’ bgcolor=codebg, fontsize= , 1. Introduction There are many reasons to split a single ‘monolithic’ application into distinct services ( Dragoni et al. 2017 ; Quigley et al. 2009 ) . Services can be developed, deployed, and scaled independently. Services can also be written in different programming languages, giving organizations access to a larger software ecosystem and talent pool. By making services simple and small ( micro services), programmers can make their applications more resilient to hardware and software faults ( Newman 2021 ) . However, writing workflows to coordinate services is not always an easy feat. There are two ways to coordinate services: orchestration and choreography ( Heinrichs [n. d.] ) . In orchestration, a central ‘orchestrator’ service makes remote procedure calls (RPCs) to ‘worker’ services that handle domain logic (c.f. Figure 1 a). Many organizations cite that orchestration makes complex workflows easy to monitor and maintain ( Netflix Technology Blog 2016 ; De Giosa [n. d.] ) . The key advantages are: A1. (Global view) The entire workflow lives at one service—perhaps even one procedure. A2. (One language) Workers may use different languages, but the orchestrator uses one language. A3. (Safety) Deadlock-freedom, determinism, and message type safety are easy to check statically. A4. (Separate deployment) New workflows can be deployed without redeploying the workers. A5. (Single source of truth) In case of faults, workflows can be resumed by querying the orchestrator’s local database. However, making all interactions go through a single service can incur unnecessary network hops, with each hop ranging from microseconds to hundreds of milliseconds ( Seemakhupt et al. 2023 ; Lai et al. 2020 ) . The impact of unnecessary hops on end-to-end latency is what we call the orchestration tax . Organizations can try to dodge the orchestration tax with optimizations like RPC chains and distributed futures ( Song et al. 2009 ; Wang et al. 2021 ) or by dynamically merging orchestrators with worker services like in ServiceWeaver ( Ghemawat et al. 2023 ) . But sometimes this is not enough: optimizations do not give the programmer complete control over data movement, and some services cannot be co-located because they are pinned to specific hardware ( Quigley et al. 2009 ) . Security policies and data sovereignty requirements can also add tight constraints on how services coordinate and preclude the use of orchestrators altogether ( Acay et al. 2024 ; Park et al. 2024 ; Oracle 2025 ; Seemakhupt et al. 2023 ) . Figure 1 . A workflow with three services, implemented in three different styles. Without orchestration, worker services need to use choreography: direct, point-to-point communication with no inherent center of control (c.f. Figure 1 b). Traditionally, choreographies split a workflow’s implementation across several different services, sacrificing advantages A1 – A5 . Choreographic programming ( Montesi 2014 ; Montesi 2023 ) helps recover some of these advantages. The key idea is to extend traditional languages with a notion of ‘roles’ (the location of a value or computation) and ‘communications’ (a way to bring values from one location to another). The resulting source code, which we will call choreographic programs , can be compiled to produce choreographies as target code. Researchers have developed choreographic programming languages based on Haskell ( Shen et al. 2023 ) , Rust ( Bates et al. 2025 ) , Elixir ( Wiersdorf and Greenman 2025 ) , Clojure ( klo 2025 ) , and more; we will focus on Choral ( Giallorenzo et al. 2024 ) , a choreographic programming language based on Java. Unfortunately, real service-oriented applications have a laundry list of requirements that are not satisfied by any choreographic programming language: R1. (Concurrency) Services should not need to finish one workflow before joining another. R2. (Agreement) At the end of a workflow, all participants succeed or all participants fail. R3. (Durability) Workflows can make progress despite crashes and dropped messages. R4. (Reactivity) Once a workflow starts, services can add new participants at runtime. Requirements R1 , R2 , and R3 are properties of saga transactions ( Garcia-Molina and Salem 1987 ) . Sagas are distributed transactions that sacrifice the consistency and isolation requirements of classical ACID transactions, improving performance in service-oriented applications. Our key challenge is to design an architecture that satisfies requirements R1 – R4 and advantages A1 – A4 , despite the lack of A5 . Researchers have aimed to satisfy requirements R1 – R4 by making choreographic programming more expressive. Graversen et al proposed frames to recover from dropped messages ( Graversen et al. 2025 ) , Plyukhin et al proposed a new semantics to increase concurrency ( Plyukhin et al. 2024 ) , Lugović and Montesi proposed an event-driven pattern to make choreographies reactive ( Lugović and Montesi 2024 ) , and Wiesdorf and Greenman proposed synchronized checkpoints to achieve all-or-nothing semantics ( Wiersdorf and Greenman 2025 ) . Each of these extensions only addresses a subset of our requirements, and some require nontrivial changes to the compiler. Some language extensions also make programs more complex. To combine them all in one place would weaken the elegant correspondence between orchestrators and choreographic programs. Our solution is Accompanist : a language runtime for resilient choreographic programs. Programmers use Accompanist by writing ordinary Choral programs and deploying the compiled code to sidecars (