Michael De Rosa

Locally Distributed Predicates: A Technique for Distributed Programming Degree Type: Ph.D. in Computer Science
Advisor(s): Seth Goldstein, Peter Chan
Graduated: May 2010

Abstract:

New research in wireless networks, sensor networks, and modular robotics has spurred renewed interest in distributed programming techniques. Distributed programming is inherently more difficult than its single-threaded equivalent, due to the need for an executing thread of a distributed program located at one computation node to access state located at a different node. Traditionally, remote state has been aggregated or summarized using distributed snapshots or global predicate evaluation.

Traditional techniques for gathering state in distributed systems may be inappropriate for large-scale, sparsely-connected systems, as they are bandwidth intensive and scale poorly. We have identified a novel class of distributed predicates in such systems that we term locally distributed predicates (LDPs). These are predicates over the local neighborhood of a particular node, bounded to a finite number of communication hops. These locally distributed predicates allow a programmer to describe the state configuration of a bounded subgraph of a distributed system.

In this work, we formalize locally distributed predicates, and present two algorithms for detecting stable subclasses of LDPs. We then show how to perform common distributed detection tasks with LDPs, and how, with simple extensions, LDPs can serve as the foundation for a reactive programming language for distributed systems. We iteratively develop the language L, showing how the addition of various language features extends the expressiveness of the language. We present implementations of many distributed algorithms in L from multiple application domains. We then implement L twice, as a naive interpreted runtime, and as an efficient bytecode execution engine. Using our implementations, we proceed to characterize the performance and scalability for L, and its suitability for various distributed programming tasks.

Thesis Committee:
Seth Goldstein (Co-chair)
Peter Lee (Co-chair)
Garth Gibson
Maurice Herlihy (Brown University)

Jeannette Wing, Head, Computer Science Department
Randy Bryant, Dean, School of Computer Science

Keywords:
Distributed programming, modular robotics, distributed predicates, coordination languages, distributed snapshots