Distributed Graph Grocessing: An approach based on overlay composition

Nowadays, human being is producing an unprecedented amount of data coming from multiple and heterogeneous sources, ranging from scientic devices to business transactions. In many contexts such data is modelled as a graph, however, due to its size, it is often infeasible to process it on a single machine. A solution that is becoming more and more adopted relies on the adoption of distributed computing frameworks based on the MapReduce paradigm or the BSP model.This paper proposes a multi-layer graph overlay approach to support the orchestration of distributed, vertex-centric computations targeting Big- Data problems. Our approach takes inspiration from the overlay networks, a widely exploited approach for infor- mation dissemination, aggregation and computing orchestration in massively distributed systems. We propose Telos, an environment supporting the deni- tion of multi-layer graph overlays which provides each vertex with a layered, vertex-centric, view of the graph. Telos is dened on the top of the RDD Spark abstraction and it has been evaluated by considering two well-known graph problems. We present a set of experimental results showing the eectiveness of our approach.