Driven by the widespread adoption of both cloud computing and mobile devices,
distributed computing is increasingly commonplace. As a result, a growing
proportion of developers must tackle the complexity of distributed
programming---that is, they must ensure correct application behavior in the
face of asynchrony, concurrency, and partial failure.
To help address these difficulties, developers have traditionally relied upon
system infrastructure that provides strong consistency guarantees
(e.g., consensus protocols and distributed transactions). These mechanisms
hide much of the complexity of distributed computing---for example, by
allowing programmers to assume that all nodes observe the same set of events
in the same order. Unfortunately, providing such strong guarantees becomes
increasingly expensive as the scale of the system grows, resulting in
availability and latency costs that are unacceptable for many modern
applications.
Hence, many developers have explored building applications that only require
loose consistency guarantees---for example, storage systems that only
guarantee that all replicas eventually converge to the same state, meaning
that a replica might exhibit an arbitrary state at any particular
time. Adopting loose consistency involves making a well-known tradeoff:
developers can avoid paying the latency and availability costs incurred by
mechanisms for achieving strong consistency, but in exchange they must deal
with the full complexity of distributed computing. As a result, achieving
correct application behavior in this environment is very difficult.
This thesis explores how to aid developers of loosely consistent applications
by providing programming language support for the difficulties they
face. The language level is a natural place to tackle this problem: because
developers that use loose consistency have fewer system facilities that they
can depend on, consistency concerns are naturally pushed into application
logic. In part, our goal has been to recognize, formalize, and automate
application-level consistency patterns.
We describe three language variants that each tackle a different challenge in
distributed programming. Each variant is a modification of Bloom, a
declarative language for distributed programming we have developed at UC
Berkeley. The first variant of Bloom, BloomL, enables
deterministic distributed programming without the need for distributed
coordination. Second, Edelweiss allows distributed storage reclamation
protocols to be generated in a safe and automatic fashion. Finally,
BloomPO adds sophisticated ordering constraints that
we use to develop a declarative, high-level implementation of concurrent
editing, a particularly difficult class of loosely consistent programs.
