The Internet is a partitionable low bandwidth network. Two computers connected by the Internet could temporarily become unable to communicate for various reasons, from a failure at either end, to overloading of an intermediate node connecting the two, to an out-of-date routing table. The bandwidth of the Internet is relatively low: its data transfer speed is inadequate for applications that need to access very large data objects. Since its introduction the Internet kept a much faster rate of increase for the data available than for the data transfer speed. This trend is not likely to change any time soon. This thesis presents techniques to deal with availability and consistency in partitionable low bandwidth networks, and it presents a service suitable for use in such networks. The first part of the thesis presents replication techniques suitable in a partitionable network. A partitionable network puts goals of availability and consistency at odds. Making objects available in a partitionable network requires replication; yet modifications of replicated objects during a partition can introduce inconsistencies. We show various replication techniques that provide continuous availability while managing inconsistencies among replicas. The second part of the thesis describes the PEX system, an example of a service that instantiates these abstractions. PEX is an execution service that facilitates processing of remote data. It allows computations to be performed near data, so that data need not be copied over the network. It provides a session interface which facilitates the management of related computations operating on scattered data. Internally, PEX replicates various information, including sessions, using some of the techniques introduced in the first section of the thesis. This permits the system to keep computations running in the face of partitions. The third part of the thesis gives two example applications that use PEX (a distributed shell and a parallel make) and reports the performance of the PEX system.