PPoPP 2014 Tutorial

Programming Distributed Algorithms

This tutorial will give an overview of methods and languages for programming distributed algorithms.  The tutorial consists of four parts:

• 1. An introduction to distributed algorithms and an overview of methods and languages for expressing distributed algorithms.  The introduction covers important algorithms to be used as examples, including Paxos for distributed consensus that is at the core of distributed services.

  2. A method for programming distributed algorithms with (1) high-level  control flows that are easy to understand as in pseudo-code, and (2)  precise semantics for rigorous analysis and verification as in formal specification languages.

  3. A language, DistAlgo, that minimally extends conventional object-oriented programming languages, such as Python and Java, for such programming of distributed algorithms, and methods for efficient implementations.

  4. Demonstrations and experiments with an implementation of the language in Python, called DistPy, on example algorithms and implementations.

The language has been used to program a variety of important distributed algorithms for ease-of-use and efficiency evaluations, and has been used to implement distributed algorithms and services in dozens of course projects in graduate and undergraduate courses.  The projects include a wide range of distributed file systems, distributed hash tables, distributed databases, and other distributed processing systems such as MapReduce.

The tutorial content is based on materials collected during our recent and ongoing research project, Languages for Distributed Algorithms, and on our own research results:

• 1. Y.A. Liu, S.D. Stoller, B. Lin, and M. Gorbovitski.  From clarity to efficiency for distributed algorithms.  In Proceedings of the 27th ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages and Applications (OOPSLA), pages 395-410, October 2012.

  2. Y.A. Liu, S.D. Stoller, and B. Lin.  High-level executable specifications of distributed algorithms.  In Proceedings of the 14th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), volume 7596 of LNCS, pages 95-110, October 2012 (Best Student Paper Award).

Organizers

Annie Liu is a Professor of Computer Science at Stony Brook University.  She received her BS from Peking University, MEng from Tsinghua University, and PhD from Cornell University.  Her primary research is in languages and optimizations and focuses specially on systematic methods for program development, algorithm design, and problem solving.  She has published in many prestigious journals and conferences and has been awarded more than 20 research grants.  She has taught in a wide range of Computer Science areas and presented close to 100 research talks and invited talks at international conferences, universities, and research institutes.  In 2010, she received a State University of New York Chancellor's Award for Excellence in Scholarship and Creative Activities.

Scott Stoller is a Professor of Science Department at Stony Brook University.  He received his BS in Physics, summa cum laude, from Princeton University and his PhD in Computer Science from Cornell University.  His primary research interests are design, analysis, optimization, testing, and verification of software, with focuses on concurrency, computer security, and incremental computation.  He received an NSF CAREER Award, an ONR Young Investigator Award, a NASA Turning Goals Into Reality Award for Engineering Innovation, Best Paper Awards at Haifa Verification 2005 and Runtime Verification 2011, and a State University of New York Chancellor's Award for Excellence in Scholarship and Creative Activities in 2012.

Bo Lin is a PhD student at Stony Brook University.  He received his BS and MS from Peking University.  His main research focuses on implementation and optimization of distributed programming languages.  He has implemented several versions of DistPy and its earlier incarnation DistAlgo.