2021 — M2 Internship: Placement algorithm for distributed applications
Background
Modern applications are composed of numerous decoupled components that
communicate with one another. These applications can be represented as a
Directed Acyclic Graph (DAG) where the nodes are represented by the
components and the edges by the unidirectional communication channel
used between components. The resulting DAG must then be applied to a
network topology composed of compute nodes that may be located on a
Data-Center (DC), or on multiple DCs in a geo-distributed context. This
mapping of the application’s DAG onto physical compute nodes can be done
using an algorithm that is dependent on the optimization goal.
To address this, we propose to identify and design different placement
algorithms [4] to optimize for overall latency, data-freshness, and/or
some other predefined metric. This will first be done in an
offline/static manner and, if time permits, dynamically at runtime. For
example Stream Processing and Query Processing applications [5] will
benefit from placement optimizations to greatly improve overall latency,
throughput and data-freshness. These types of systems are prone to be
modeled as DAGs as each component is independent and communicates using
a stream of events. Furthermore, these optimizations may also be
included in a framework and be applied to any applications built using
this framework (e.g. Orleans [1]).
Research objectives and methods
The aim of this project is to study, design and develop different
positioning algorithms in order to evaluate them. Besides from being an
interesting study for modern applications (and more generally in graph
theory), the resulting algorithms will be applied to a Reactive Actor
Model [2, 3] framework in C++.
We break down the project into the following steps:
- Brief study of the state of the art
- Identify and use/implement an evaluation strategy
- Developing a simple and functional positioning algorithm that will be used as a baseline for future evaluation. The goal is to learn about DAG encoding, positioning algorithm design and implementation
- Incrementally improve on the first algorithm or start on a new algorithm
- Evaluate and compare the identified algorithm(s)
- Adapting the identified algorithm within an existing framework
How to apply
The intern must:
- Be enrolled in a Masters degree in Computer Science / Informatics or a related field
- Have an excellent academic record
- Be strongly interested in, and have good knowledge of, distributed systems and/or graph theory
- Be motivated by experimental research
The internship is funded, and will take place in the Delys group, at
Laboratoire d’Informatique de Paris-6 (LIP6), in Paris.
The advisors are
Benoît Martin <benoit.martin@lip6.fr>,
Dimitrios Vasilas and Sreeja Nair <sreeja.nair@lip6.fr>, under
supervision of Dr. Marc
Shapiro.
A successful intern will be invited to apply for a PhD.
To apply, contact the advisors, with the following information:
- A resume or Curriculum Vitæ
- A list of courses and grades of the last two years of study (an informal transcript is OK)
- Names and contact details of two references (people who can recommend you), whom we will contact directly
References
[1] Phil Bernstein et al. “Orleans: Distributed Virtual
Actors for Programmability and Scalability”.
[2] Jonas Bonér et al. The reactive
manifesto. 2014.
[3] Carl Hewitt, Peter Bishop, and Richard Steiger. “A
Universal Modular Actor Formalism for Artificial Intelligence”. In:
Proceedings of the 3rd International Joint Conference on Artificial
Intelligence. IJCAI’73. Stanford, USA. San Francisco, CA,
USA: Morgan Kaufmann Publishers Inc., 1973, pp. 235–245.
[4] Geetika T. Lakshmanan, Ying Li, and Rob
Strom. Placement Strategies for Internet-Scale Data Stream
Systems. Publisher: IEEE Computer Society. Nov. 1, 2008. doi: 10.1109/
MIC.2008.129.
[5] Dimitrios Vasilas, Marc Shapiro, and Bradley
King. “A modular design for geo-distributed querying: work in progress
report”. In: Proceedings of the 5th Workshop on the Principles and
Practice of Consistency for Distributed Data. PaPoC ’18. Porto,
Portugal: Association for Computing Machinery, Apr. 23, 2018,
pp. 1–4. isbn: 978-1-4503-5655-8. doi: 10.1145/3194261.3194265.
