WG – Felipe de Souza: A Throughput Model for Data Stream Processing on Fog Computing


Title: A Throughput Model for Data Stream Processing on Fog Computing

Speaker: Felipe Rodrigo de Souza (LIP, AVALON team)

Location: LIP, Meeting room M7 3rd floor

Schedule: 14:00


Today’s society faces an unprecedented deluge of data that requires processing and analysis. Data Stream Processing (DSP) applications are often employed to extract valuable information in a timely manner as they can handle data as it is generated. The typical approach for deploying these applications explores the Cloud computing paradigm, which has limitations when data sources are geographically distributed, hence introducing high latency and achieving low processing throughput. To address these problems, current work attempts to take the computation closer to the edges of the Internet, exploring Fog computing. The effective adoption of this approach is achieved with proper throughput modeling that accounts for characteristics of the DSP application and Fog infrastructure, including the location of devices, processing and bandwidth requirements of the application, as well as selectivity and parallelism level of operators. In this work, we propose a throughput model for DSP applications embracing these characteristics. Results show that the model estimates the application throughput with less than 1% error.

Avalon at the TILECS Workshop

Avalon at the TILECS Workshop

Towards an Infrastructure for Large-Scale Experimental Computer Science

3 et 4 juillet, Campus Grenoble, France

More information about SILECS and the TILECS Workshop: https://www.silecs.net/tilecs-2019/

Laurent Lefevre (Avalon / Speaker) and Georges Da Costa with Christian Perez (Avalon / Chairman)

SILECS is a research infrastructure being built to gather the efforts of several testbeds.


The Avalon team are involved in this impressive project.

Farah Ait Salaht, Eddy Caron, Marcos Dias de assuncao, Laurent Lefevre (speaker), Matthieu Imbert, Christian Perez  (Session Chairman) was at this workshop.

WG – Carlos Cardonha: Online scheduling in magnetic tapes


Title: Online scheduling in magnetic tapes

Speaker: Carlos Cardonha (IBM Research Brazil)

Location: LIP, meeting room M7 3rd floor

Schedule: 14:30

Abstract: Magnetic tapes have been playing a key role as means for storage of digital data for decades, and their unsurpassed cost-effectiveness still makes them the technology of choice in several industries, such as media and entertainment. Tapes are mostly used for cold storage nowadays, and therefore the study of scheduling algorithms for read requests tailored for these devices has been largely neglected in the literature. In this article, we investigate the Linear Tape Scheduling Problem (LTSP), in which read requests associated with files stored on a single-tracked magnetic tape should be scheduled in a way that the sum of all response times are minimized. LTSP has many similarities with classical combinatorial optimization problems such as the Traveling Repairmen Problem and the Dial-a-Ride Problem restricted to the real line; nevertheless, significant differences on structural properties and strict time-limit constraints of real-world scenarios make LTSP challenging and interesting on its own. In this work, we investigate several properties and algorithms for LTSP and some of its extensions. The results allowed for the identification of 3-approximation algorithms for LTSP and efficient exact algorithms for some of its special cases. We also show that LTSPR, the version of the problem with heterogeneous release times for requests, is NP-complete. OLTSP, the online extension of LTSPR, does not admit c-competitive algorithms for any constant factor c, but we nevertheless introduce an algorithm for the problem and show through extensive computational experiments on synthetic and real-world datasets that different embodiments of the proposed strategy are computationally efficient and over-perform by orders of magnitude an algorithm being currently used by real-world tape file systems.

Mini-bio: Carlos Cardonha is a Research Staff Member at the Natural Resources Optimization group at IBM Research Brazil, with a Ph.D. in Mathematics (T.U. Berlin) and with a Bachelor’s and a Master’s degree in Computer Science (Universidade de São Paulo). His primary research interests are mathematical programming and theoretical computer science, with focus on the application of techniques in mixed integer linear programming, combinatorial optimization, and algorithms design and analysis to real-world and/or operations research problems.