Towards Correct and Efficient Program Execution in Decentralized Networks: Programming Languages, Semantics, and Resource Managment

Abstract

The Internet as of 2014 connects billions of devices, and is expected to
connect tens of billions by 2020. To meet escalating requirements,
networks must be scalable, easy to manage, and be able to efficiently
execute programs and disseminate data. The prevailing use of centralized
systems and control in, e.g., pools of computing resources, clouds, is
problematic for scalability. A promising approach to management of large
networks is decentralization, where independently acting network nodes
communicate with their immediate neighbors to achieve desirable results
at the global level.

The research in this thesis addresses three distinct but interrelated
problems in the context of cloud computing, networks, and programs
running in clouds. First, we show how implementation correctness of
active objects can be achieved in decentralized networks using location
independent routing. Second, we investigate the feasibility of
decentralized adaptive resource allocation for active objects in such
networks, with promising results. Third, we automate an initial step of
a process for converting programs with thread-based concurrency using
shared memory to programs with message passing concurrency, which can
then run efficiently in clouds.

Specifically, starting from fragments of the distributed object modeling
language ABS, we give network-oblivious descriptions of runtime behavior
of programs, where the global state is a flat collection of objects and
method calls. We then provide network-aware semantics, that place
objects on network nodes connected point-to-point by asynchronous
message passing channels. By relying on location independent routing,
which maps object identifiers to next-hop neighbors at each node,
inter-object messages can be delivered, regardless of object mobility
among nodes. We establish that network-oblivious and network-aware
behavior in static networks correspond in the sense of contextual
equivalence. Using a network protocol reminiscent of a two-phase commit
for controlled node shutdown, we extend the approach to dynamic networks
without failures.

We investigate node-local procedures for object migration to meet
requirements on balanced allocations of objects to nodes, that also
attempt to minimize exchange of object-related messages between nodes.
By relying on coin-flips biased on local and neighbor load to decide on
migration, and heuristics to capture object communication patterns, we
show that balanced allocations can be achieved that make headway towards
minimizing communication and latency.

Our approach to execution of object-oriented programs in networks relies
on message-passing concurrency. Mainstream programming languages
generally use thread-based concurrency, which relies on control-centric
primitives, such as locks, for synchronization. We present an algorithm
for dynamic probabilistic inference of annotations for data-centric
synchronization in threaded programs. By making collections of variables
in classes accessed atomically explicit, these annotations can in turn
suggest objects suitable for encapsulation as a unit of message-passing
concurrency.