Peter D. Stout

WAX: A Wide-area Distributed Computation System Degree Type: Ph.D. in Computer Science
Advisor(s): Brian Bershad, Eric Cooper
Graduated: December 1994

Abstract:

This dissertation explores the use of machines connected to wide-area networks to provide the parallelism needed to work on large coarse-grain parallel applications. Large applications, such as circuit simulations, integer factoring, graphics applications, and NP- complete approximations, have potential coarse-grain parallelism that exceeds the parallel processing facilities at any single site. At the same time, the machines connected to wide- area networks represent a large and growing source of under-utilized computing power. However, in order to transform the idle machines on a wide-area network into a large scale, wide-area distributed computing system, a number of problems need to be addressed: latency, failure, security, process management, scale, and system administration. This dissertation describes a prototype wide-area distributed computation system, called Wax, that has been built and used to explore solutions to these problems.

Wax implements a programming model that takes into consideration the problems that exist in distributed computing environments, particularly wide-area ones. The key differences from traditional parallel programming models are a reduced global consistency guarantee, the explicit incorporation of failure into the model, and reduced access to the local execution machine. The first two differences allow Wax to expose the effects of some these wide-area problems (failure, latency, scale) to the application programmer. The most appropriate solutions to these problems often require application-specific knowledge. The third difference allows Wax to incorporate mechanisms to protect the resources used to process applications from abuse by those applications.

Instead of providing a global consistency guarantee, which not all applications require, Wax handles some of the other wide-area problems (processor failure, process management) that existing distributed computation systems leave to their users. By de-emphasizing consistency, Wax is also able to provide applications with greater potential parallelism.

Since the Wax programming model differs from those supported by existing distributed computation systems, the dissertation also identifies a class of applications that can be solved using the model. In addition, the dissertation reports the performance of Wax implementations of several applications from the general class.

Thesis Committee:
Brian Bershad (Co-Chair)
Eric Cooper (Co-Chair)
Doug Tygar
Adam Beguelin
Mark Manasse (DEC SRC)

James Morris, Head, Computer Science Department
Raj Reddy Dean, School of Computer Science

Keywords:
Distributed Systems, Parallel Processing, Networks