Effective High-level Coordination Programming for Decentralized and Distributed Ensembles

Programming and coordinating decentralized ensembles of computing devices is extremely hard and error-prone. With cloud computing maturing and the emerging trend of embedding computation into mobile devices, the demand for building reliable distributed and decentralized systems is becoming increasingly common and complex. Because of these growing technical challenges, solutions for effective programming and coordination of decentralized ensembles remain elusive. Most main-stream programming methodologies only offer a node-centric view of programming, where a programmer specifies distributed computations from the perspective of each individual computing node (e.g., MPI, transactional memory, the Actor model, Linda Tuple Space, graph processing frameworks). When programming distributed computations in this style, programmers experience minimal shifts in paradigm but such concurrency primitives offer minimal support for the coordination problem. However, as systems grow in complexity and sophistication, maintaining code in this node-centric style of ten becomes costly, as the lack of concurrency abstraction means that programmers assumes all the responsibility of avoiding concurrency pitfalls (e.g., deadlocks and race-conditions). Because of this, ensemble-centric concurrency abstractions are now growing in popularity. In this style of programming, programmers are able to specify complex distributed computations from the perspective of entire collections of computing nodes as a whole (e.g., MapReduce, Google Web Tool-kit, choreographic programming), making implementations of distributed computations more concise and even making large classes of concurrency pitfalls syntactically impossible. However, programming distributed computations in this style typically require programmers to adopt a new perspective of computation. At times, they are overly restrictive and hence not applicable to a wider range of distributed coordination problems. Our work centers on developing a concurrency abstraction to overcome the above challenges, by (1) providing a high-level ensemble-centric model of coordinating distributed computations, and (2) offering a clean and intuitive integration with traditional main-stream imperative programming languages. This framework as a whole, orthogonally combines a high-level concurrency abstraction together with established lower-level main-stream programming methodologies, maintaining a clean separation between the ensemble-centric concurrency model and the underlying sequential computation model, yet allowing them to interact with each other in a symbiotic manner. The benefit of this separation is twofold: first, a clear distinction of the elements of the coordination model from the computation model helps lower the learning curve of this new programming framework. Hence, developers familiar with the underlying main-stream computation model can incrementally build their technical understanding of the framework, by focusing solely on the coordination aspects of the framework. Second, by building the coordination model on top of an underlying main-stream computation model, we inherit all existing libraries, optimizations, as well as programming expertise available to it. We have addressed several key challenges of developing such an ensemble-centric concurrency model. In particular, we have developed a choreographic transformation scheme that transform our ensemble-centric programs into node-centric encodings, and we have also developed a compilation scheme that convert such node-centric encodings into lower-level imperative codes that can be executed by individual computing nodes. Finally, we proved the soundness of this choreographic compilation scheme by showing a two-step correspondence from ensemble-centric specifications to node-centric encodings, then to node-centric compilations. We have implemented an instance of this distributed programming framework for coordinating decentralized ensembles of Android mobile devices. This system is called CoMingle and it is built to integrate with Java and the Android SDK. The ensemble-centric nature of this programming abstraction simplifies the coordination of multiple Android devices, and in we demonstrate how the clean integration with Java and Android SDK allow local computations within each device to be implemented in a traditional manner, hence leveraging from an Android programmer's expertise, rather than forcing him/her to work with an entirely new programming environment. As proof-of-concept, we have developed a number of distributed mobile Android applications. CoMingle is open-source and available for download at https://github.com/sllam/comingle.