07518nam 22007695 450 991034926130332120230222181231.03-319-74875-010.1007/978-3-319-74875-7(CKB)4100000001794910(DE-He213)978-3-319-74875-7(MiAaPQ)EBC6281463(MiAaPQ)EBC5591807(Au-PeEL)EBL5591807(OCoLC)1020793426(PPN)223955477(EXLCZ)99410000000179491020180127d2018 u| 0engurnn#008mamaatxtrdacontentcrdamediacrrdacarrierAlgorithmic Aspects of Cloud Computing Third International Workshop, ALGOCLOUD 2017, Vienna, Austria, September 5, 2017, Revised Selected Papers /edited by Dan Alistarh, Alex Delis, George Pallis1st ed. 2018.Cham :Springer International Publishing :Imprint: Springer,2018.1 online resource (X, 171 p. 60 illus.)Theoretical Computer Science and General Issues,2512-2029 ;107393-319-74874-2 Intro -- Preface -- Organization -- Contents -- Invited Paper -- Warehouse-Scale Computing in the Post-Moore Era -- 1 Heterogeneity in Platforms -- 2 Massive Data Analytics -- References -- Optimization for Cloud Services -- A Walk in the Clouds: Routing Through VNFs on Bidirected Networks -- 1 Introduction -- 1.1 Model -- 1.2 Contributions -- 1.3 Related Work -- 1.4 Paper Organization -- 2 The Unordered BWRP -- 2.1 An Introduction to (Unordered) Waypoint Routing -- 2.2 Hardness and Improved Approximation -- 3 Ordered BWRP -- 3.1 A Constant Number of Waypoints Is Feasible -- 3.2 Optimally Solving OBWRP Is NP-Hard -- 3.3 Optimality on the Cactus with Constant Capacity -- 4 Conclusion -- References -- Service Chain Placement in SDNs -- 1 Introduction -- 1.1 Related Work -- 1.2 Our Results -- 2 Preliminaries -- 3 Hardness Results -- 4 Algorithms for Physical Directed Acyclic Graphs -- 4.1 Placing a Sub-chain in a Physical Node -- 4.2 Placing a Service Chain -- 4.3 Placing a Service Chain with a Latency Bound -- 4.4 FPTAS for General Costs -- 5 General Networks -- References -- Tight Approximability of the Server Allocation Problem for Real-Time Applications -- 1 Introduction -- 2 Approximation Algorithms -- 2.1 Case 1: Metric in SU -- 2.2 Case 2: Metric in S -- 3 Hardness of Approximation -- 4 Experiments -- 4.1 Acceleration of the Proposed Algorithms -- 4.2 Experiment 1: Following Kawabata et al. KCO16 -- 4.3 Experiment 2: With More Servers -- References -- Computing with Risk and Uncertainty -- Risk Aware Stochastic Placement of Cloud Services: The Case of Two Data Centers -- 1 Introduction -- 2 The Normal Two Bin Case -- 2.1 The Sorting Algorithm -- 2.2 The Correctness Proof -- 3 Other Cost Functions -- 4 Non-normal Distributions -- 4.1 The Berry-Esseen Theorem -- 4.2 Approximating General Independent Distributions with the Normal Distribution.5 Simulation Results -- 5.1 Results for Synthetic Normally Distributed Data -- 5.2 Results for Real Data -- 6 Conclusions -- A Proving SP-MED Falls into Our Framework -- B Proving SP-MWOP Falls into Our Framework -- C Proving SP-MOP Falls into Our Framework -- D Error Induced by the Reduction to the Normal Distribution -- E Error Induced by Outputting an Integral Solution -- E.1 SP-MED -- E.2 SP-MWOP -- F Unbalancing Bin Capacities Is Always Better -- References -- Towards an Algebraic Cost Model for Graph Operators -- 1 Introduction -- 2 Related Work -- 3 Algebraic Framework -- 3.1 Data Model -- 3.2 Base Operators -- 3.3 Cost Model -- 4 Graph Operator Decomposition -- 4.1 Finding Cycles -- 4.2 Random Walk, Path, and Star-Path -- 4.3 Grid Query -- 5 Experiments -- 5.1 Experimental Setup -- 5.2 Results and Discussion -- 5.3 Including Label Information in the Cost Model -- 6 Conclusions -- A Appendix -- A.1 Random 4-Walk Benchmarks -- References -- Computing Probabilistic Queries in the Presence of Uncertainty via Probabilistic Automata -- 1 Introduction and Motivation -- 2 Related Work -- 3 Definitions and Notation -- 4 Using Probabilistic Automata to Answer Queries -- 4.1 Constructing Automata from Queries -- 4.2 The General Method -- 5 Conclusion and Future Work -- References -- Scaling and Cost Models in the Cloud -- Improving Rule-Based Elasticity Control by Adapting the Sensitivity of the Auto-Scaling Decision Timeframe -- 1 Introduction -- 2 Motivation -- 3 The AdaFrame Library -- 3.1 Adaptive Monitoring Estimation Model -- 3.2 Runtime Change Detection -- 4 Evaluation -- 4.1 Testbed 1: Scaling a NoSQL Document Store -- 4.2 Testbed 2: Scaling the Business Logic of a Web Service -- 5 Related Work -- 6 Conclusion -- References -- Risk Aware Stochastic Placement of Cloud Services: The Multiple Data Center Case -- 1 Introduction.2 Problem Formulation -- 3 Summary of Our Results for Two Data Centers -- 4 Three Cost Functions -- 5 The Double Sorting Framework for More Than Two Data Centers -- 6 A Dynamic Programming Algorithm -- 7 The Moving Sticks (MVS) Algorithm for SP-MWOP -- 8 The Generalized Moving Sticks (GMVS) Algorithm -- 9 Conclusions -- A Simulation Results -- A.1 Results for Synthetic Normally Distributed Data -- References -- Automatic Scaling of Resources in a Storm Topology -- 1 Introduction -- 2 Preliminaries -- 3 Architecture -- 4 Experimental Evaluation -- 5 Related Work -- 6 Conclusions -- References -- Author Index.This book constitutes the thoroughly refereed post-conference proceedings of the Second International Workshop on Algorithmic Aspects of Cloud Computing, ALGOCLOUD 2017, held in Vienna, Austria, in September 2017. The 9 revised full papers were carefully reviewed and selected from 27 submissions.  The aim of the workshop is to present research activities and results on topics related to algorithmic, design, and development aspects of modern cloud-based systems.Theoretical Computer Science and General Issues,2512-2029 ;10739AlgorithmsComputer science—MathematicsDiscrete mathematicsApplication softwareArtificial intelligence—Data processingComputer networksAlgorithmsDiscrete Mathematics in Computer ScienceComputer and Information Systems ApplicationsData ScienceComputer Communication NetworksAlgorithms.Computer science—Mathematics.Discrete mathematics.Application software.Artificial intelligence—Data processing.Computer networks.Algorithms.Discrete Mathematics in Computer Science.Computer and Information Systems Applications.Data Science.Computer Communication Networks.004Alistarh Danedthttp://id.loc.gov/vocabulary/relators/edtDelis Alexedthttp://id.loc.gov/vocabulary/relators/edtPallis Georgeedthttp://id.loc.gov/vocabulary/relators/edtMiAaPQMiAaPQMiAaPQBOOK9910349261303321Algorithmic Aspects of Cloud Computing3660151UNINA