Advancement: Shen, G. (CSE) - Toward Asynchronous and Fault-Tolerant Choreographic Programming

Choreographic programming is a programming paradigm for building distributed systems. In this approach, programmers describe the desired protocol as a single program where communications between participants are expressed globally, like a choreography. This program is then compiled into a collection of local programs for each node, resulting in a deadlock-free implementation of the protocol.

Previously, we have built HasChor, an embedded domain-specific language (EDSL) for choreographic programming in Haskell. In HasChor, choreographies are expressed as computations in a monad, and the compilation process is defined as interpreting the operations in the monad from the view of a particular node. To our knowledge, HasChor is the first choreographic language that does not require a customized compiler; as a result, it integrates seamlessly with the existing Haskell ecosystem, a step forward for the applicability of choreographic programming.

However, existing choreographic languages remain impractical because they typically assume synchronous and lossless communications. These assumptions prevent us from applying choreographic programming to implement realistic distributed protocols, as the real network is asynchronous and lossy. Additionally, HasChor has a limitation: its embedding technique relies on freer monads, whose dynamic structures prevent us from doing useful static analysis, such as optimizing away unnecessary communications.

In this paper, we propose an extension to choreographic programming that provides asynchronous and fault-tolerant communications. The core of our extension is the future, a construct representing a computation that will be completed in the undetermined future or even fail. Continuing our line of work on implementing choreographic programming as EDSL, we also propose using applicative functors—a structure that exposes more static information than monads—to refactor HasChor and embed our extension.

Event Host: Gan Shen, Ph.D. Student, Computer Science & Engineering

Advisor: Lindsey Kuper