Skip to Main content Skip to Navigation
Conference papers

Group Mutual Exclusion to Scale Distributed Stream Processing Pipelines

Mehdi Belkhiria 1 Marin Bertier 1 Cédric Tedeschi 1
1 MYRIADS - Design and Implementation of Autonomous Distributed Systems
Inria Rennes – Bretagne Atlantique , IRISA-D1 - SYSTÈMES LARGE ÉCHELLE
Abstract : Stream Processing has become the de facto standard way of supporting real-time data analytics. Stream Processing applications are typically shaped as pipelines of operators, each record of the stream traversing all the operators of the graph. The placement of these operators on nodes of the platform can evolve through time according to different parameters such as the velocity of the input stream and the capacity of nodes. Such an adaptation calls for mechanisms such as dynamic operator scaling and migration. With the advent of Fog Computing, gathering multiple computationally-limited geographically-distributed resources, these mechanisms need to be decentralized, as a central coordinator orchestrating these actions is not a scalable solution any more. In a fully decentralized vision, each node hosts part of the pipeline. Each node is responsible for the scaling of the operators it runs. More precisely speaking, nodes trigger new instances of the operators they runs or shut some of them down. The number of replicas of each operator evolving independently, there is a need to maintain the connections between nodes hosting neighbouring operators in the pipeline. One issue is that, if all these operators can scale in or out dynamically, maintaining a consistent view of their neighbours becomes difficult, calling for synchronization mechanisms to ensure it, to avoid routing inconsistencies and data loss. In this paper, we show that this synchronization problem translate into a particular Group Mutual Exclusion (GME) problem where a group comprises all instances of a given operator of the pipeline and where conflicting groups are those hosting neighbouring operators in the pipeline. The specificity of our problem is that groups are fixed and that each group is in conflict with only one other groups at a time. Based on these constraints, we formulate a new GME algorithm whose message complexity is reduced when compared to algorithms of the literature, while being able to ensure a high level of concurrent occupancy (the number of processes of the same group in the critical section (the scaling mechanism) at the same time.
Complete list of metadata
Contributor : Mehdi Belkhiria Connect in order to contact the contributor
Submitted on : Friday, February 12, 2021 - 12:12:08 PM
Last modification on : Wednesday, November 3, 2021 - 8:17:46 AM
Long-term archiving on: : Thursday, May 13, 2021 - 6:01:28 PM


  • HAL Id : hal-02993099, version 1


Mehdi Belkhiria, Marin Bertier, Cédric Tedeschi. Group Mutual Exclusion to Scale Distributed Stream Processing Pipelines. UCC 2020 - 13th IEEE/ACM International Conference on Utility and Cloud Computing,, Dec 2020, Leicester / Virtual, United Kingdom. ⟨hal-02993099⟩



Les métriques sont temporairement indisponibles