High-level distributed computing

Distributed system; distributed programming; distributed database system; reactive programming; programming language and verification.

Informations

Status
Underway

Links


Description

Background

Distributed computing has become a crucial technique across many areas of computing. Programming highly-available distributed applications is no longer reserved to expert programmers. Consider for instance, mobile computing, Internet of Things (IoT), high-performance computing, Network Function Virtualisation (NFV), neural networks, or internet gaming. However, distributed programming remains difficult and error-prone, exposing users, the economy, and critical infrastructure to bugs and security violations. Indeed, concurrency and failures, essential features of a distributed system, are difficult to abstract away. Interacting concurrent processes do not compose well. Furthermore, any large-scale distributed system suffers undetectable failures and processes cannot reliably reach consensus on a single (“strongly consistent”) up-to-date view of shared state; this is a fundamental result of distributed system theory (the FLP and CAP theorems). Furthermore, applications have conflicting requirements. On the one hand, correctness (controlling what the system does), requires events to happen in a reliable, deterministic way. On the other, application performance (including availability, responsiveness and throughput), requires concurrent, asynchronous execution. There is no single right solution to this trade-off; it depends on the application requirements, the expected environment and workload, the available resources, etc. A promising direction is a hybrid approach, where updates avoid coordination by default, but specific operations that are essential to application correctness are synchronised. Getting this right is difficult: current practice in building distributed systems rests on programmer expertise, i.e., trial and error, which is costly and dangerous. Thus, currently, large numbers of non-expert programmers to play it by ear among uncomfortable and momentous trade-offs, in the presence of non-composable, non-deterministic, and weak consistency.

Proposed research

We believe that the situation is ripe for a new, high-level approach. We propose to develop methods, tools and languages to aid the programmer of general distributed programs. Highly successful and explicative abstractions already exist, such as (at opposite ends of the spectrum) consensus or data flow. Frameworks and languages are making distributed programming easily accessible in some restricted domains, for instance MapReduce, Spark or TensorFlow. These approaches work well in their restricted environment, but only by severely restricting the developer’s capabilities. The closest to a general-purpose programming environment is Orleans [4], which allows the developer to define and compose abstract, location-independent. The runtime environment is in charge of connecting them together and of deploying them, elastically as the service demands and the availability of resources change over time. Another important concept is dataflow or reactive programming, whose main abstraction is a graph whose edges carry flows of information, and whose vertices are computation entities [2]. Finally, tierless programming describes distributed computation subsuming how sub-computations are deployed and placed at the different tiers of a cloud computing environment [3]. These approaches provide orthogonal computation, composition, communication and deployment abstractions, and are designed to maximise parallelism and to enable flexibility and elasticity. However, in order to hide the complexity of distribution to application developers, they come with arbitrary restrictions; for instance, communication abstractions are often unidirectional. Deployment, consistency, security and fault-tolerance are assumed addressed by a separate system, not programmable with the same first-class abstractions. We believe that it is possible to take a similar approach for both application and system developers themselves. It should be possible to create and protect abstractions, including what is built-in or second-class in the above systems, by composing basic primitives that provide access to the full power of distribution. It should be possible, for instance, to build the equivalent of Antidote [1] or Orleans with flexible consistency levels and a pluggable, non-compromisable security architecture. Such primitives might include:
  • Shared and persistent data objects, with the capability to implement replication and versioning.
  • Asynchronous (concurrent) and synchronous (consensus-based) operation invocation, with the capability to provide transactional and causal consistency guarantees.
  • Publish-subscribe/data flow, with forward and backward paths, and combiners. Data flow carries any mixture of state, delta, or operation. Communication respects programmer-defined abstraction boundaries.
  • Transparent piggy-backing of metadata, such as timestamps, provenance, security labels, or accounting information.
  • Programmable deployment and elastic configuration of computation and data entities, transparently to their functional program text.
At the same time, our approach helps avoid many of the opportunities for error, by focusing on the essential properties of application correctness. It is often the invariants required over application data that dictates the protocol for accessing the data; this is an intuition that programmers commonly apply. Hence, we aim to apply leverage language and verification tools, to aid the programmer in choosing the best consistency level and in synthesising a program that respects its specification.

References

  • [1] AntidoteDB, a planet-scale, available, transactional database with strong semantics. http://antidoteDB.eu/
  • [2] The Reactive Manifesto. https://www.reactivemanifesto.org, September 2014.
  • [3] Gérard Boudol, Zhengqin Luo, Tamara Rezk, and Manuel Serrano. Reasoning about Web applications: An operational semantics for HOP. ACM Transactions on Programming Languages and Systems, 34(2):10:1–10:40, June 2012. DOI: 10.1145/ 2220365.2220369.
  • [4] Sergey Bykov, Alan Geller, Gabriel Kliot, James R. Larus, Ravi Pandya, and Jorgen Thelin. Orleans: cloud computing for everyone. In Symp. on Cloud Computing, pages 16:1–16:14, Cascais, Portugal, October 2011. Assoc. for Computing Machinery. DOI: 10.1145/2038916.2038932.

Planner

Master Internship - Unifying stream processing across Edge and Cloud.

Informations

Languages
  • Python->=3.4
  • Java
Lines
~1842
Status
stopped

Description

Stream processing applications handle unbounded and continuous flows of data items which are generated from multiple geographically distributed sources. Two approaches are commonly used for processing: Cloud-based analytics and Edge analytics. The first one routes the whole data set to the Cloud, incurring significant costs and late results from the high latency networks that are traversed. The latter can give timely results but forces users to manually define which part of the computation should be executed on Edge and to interconnect it with the remaining part executed in the Cloud, leading to sub-optimal placements. In this paper, we introduce Planner, a middleware for uniform and transparent stream processing across Edge and Cloud. Planner automatically selects which parts of the execution graph will be executed at the Edge in order to minimize the network cost. Real-world micro-benchmarks show that Planner reduces the network usage by 40% and the makespan (end-to-end processing time) by 15% compared to state-of-the-art.

Knowledge in Byzantine Message-Passing System

Internship - Modelization of asynchronous message-passing system with byzantine failure thanks to epistemic logic.

Informations

Contributors
  • Roman.Kuznets
  • Ulrich.Schmid
Status
stopped

Description

We present an extension of the epistemic runs and systems framework for modeling distributed systems introduced by Fagin et.al. to also incorporate Byzantine agents. Our framework relies on a careful separation of concerns of the various actors involved in the evolution of a message- passing distributed system, and their respective constraints : the agents’ protocol, the underlying computation model, and the adversary that controls Byzantine faulty behavior. This modular- ization allows our framework to cover all existing distributed computing models we are aware of, like lock-step synchronous systems, all variants of partially synchronous systems, asynchronous systems with or without oracles like failure detectors and even timed systems. Albeit Byzantine faulty agents may behave arbitrarily (and may or may not be aware of doing so), our framework allows epistemic reasoning also about such agents (they may have arbitrary knowledge). We demonstrate the utility of our framework by applying it for identifying necessary and sufficient communication structures for certain distributed computing problems (like variants of clock synchronization) in asynchronous systems with Byzantine faulty agents. We extend pivotal concepts introduced in [Ben-Zvi and Moses, JACM’14] for the fault-free case to the Byzantine setting, and identify ε-pedes as a crucial causal structure.

Biasedwalk

Bachelor Internship - Biasedwalk in anonymous graphs.

Informations

Languages
  • Python->=3.4
  • C++-14
Lines
~4800
Status
stopped
Version
0.20.3-dev1

Description

The goal of this bachelor internship was to bias a random walk in order to do rendezvous or traversal of anonymous networks. A robot, doing classical random walk, pick the next vertex uniformly at random among the neighbors of the current vertex.The time complexity of such traversal can be reduce by skewing the selection of the next vertex, for instance the Metropolis walk use the degree of the current neighbor to weight the random choice. First, we have implement a random graph generator which can create interesting topology (in order to generate counter examples) and a walk simulator on top of the generated graphs. Secondly, we have study two local bias : remembering the last steps of the walk or using the local topology of the neighbors (e.g. the links between two neighbors are known). The time complexity in the worst case can not be improved by this techniques whereas, in practice, this two walks can reduce the traversal time in average.

Bibliography :

  1. Darell Long, Mark Lilibridge, Kave Eshghi, Deepavali Bhagwat, Extreme Binning: Scalable, Parallel Deduplication for Chunk-based File Backup, MASCOTS, 2009.
  2. Kave Eshghi, Hsiu Khuern Tang, A framework for analyzing and improving content-based chunking algorithms, , 2005.
  3. Nimrod Megiddo, Dharmendra S Modha, Outperforming LRU with an adaptive replacement cache algorithm, IEEE Computer 37(4), 2004.