CIEL: a universal execution engine for distributed data-flow computing
Published 30 March 2011
Derek G. Murray, Malte Schwarzkopf, Christopher Smowton, Steven M. Smith, Anil Madhavapeddy, Steven Hand
Citations230
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
The execution engine provides transparent fault tolerance and distribution to Skywriting scripts and high-performance code written in other programming languages, and achieves scalable performance for both iterative and non-iterative algorithms.
Abstract
This paper introduces CIEL, a universal execution engine for distributed data-flow programs. Like previous execution engines, CIEL masks the complexity of distributed programming. Unlike those systems, a CIEL job can make data-dependent control-flow decisions, which enables it to compute iterative and recursive algorithms. We have also developed Skywriting, a Turingcomplete scripting language that runs directly on CIEL. The execution engine provides transparent fault tolerance and distribution to Skywriting scripts and highperformance code written in other programming languages. We have deployed CIEL on a cloud computing platform, and demonstrate that it achieves scalable performance for both iterative and non-iterative algorithms. 1
Keywords
Computer ScienceDecision Sciences
Communications of the ACMMapReduce
18,538 Citations2008Jay B. Dean, Sanjay Ghemawat
This presentation explains how the underlying runtime system automatically parallelizes the computation across large-scale clusters of machines, handles machine failures, and schedules inter-machine communication to make efficient use of the network and disks.
Journal of Molecular BiologyIdentification of common molecular subsequences
10,081 Citations1981Temple F. Smith, Michael S. Waterman
This letter extends the heuristic homology algorithm of Needleman & Wunsch (1970) to find a pair of segments, one from each of two long sequences, such that there is no other Pair of segments with greater similarity (homology).
Journal of Financial EconomicsOption pricing: A simplified approach
6,191 Citations1979John C. Cox, Stephen A. Ross +1 more
ACM SIGOPS Operating Systems ReviewThe Google file system
5,003 Citations2003Sanjay Ghemawat, Howard Gobioff +1 more
Spark: cluster computing with working sets
4,236 Citations2010Matei Zaharia, Mosharaf Chowdhury +3 more
Spark can outperform Hadoop by 10x in iterative machine learning jobs, and can be used to interactively query a 39 GB dataset with sub-second response time.
Resilient distributed datasets: a fault-tolerant abstraction for in-memory cluster computing
3,577 Citations2012Matei Zaharia, Mosharaf Chowdhury +7 more
Resilient Distributed Datasets is presented, a distributed memory abstraction that lets programmers perform in-memory computations on large clusters in a fault-tolerant manner and is implemented in a system called Spark, which is evaluated through a variety of user applications and benchmarks.
Pregel
3,534 Citations2010Grzegorz Malewicz, Matthew H. Austern +5 more
A model for processing large graphs that has been designed for efficient, scalable and fault-tolerant implementation on clusters of thousands of commodity computers, and its implied synchronicity makes reasoning about programs easier.
Hadoop: The Definitive Guide
2,714 Citations2009Tom White
This comprehensive resource demonstrates how to use Hadoop to build reliable, scalable, distributed systems: programmers will find details for analyzing large datasets, and administrators will learn how to set up and run Hadoops clusters.
MPI: A Message-Passing Interface Standard
2,709 Citations1994Message P Forum
This document contains all the technical features proposed for the interface and the goal of the Message Passing Interface, simply stated, is to develop a widely used standard for writing message-passing programs.
Communications of the ACMCan programming be liberated from the von Neumann style?
2,582 Citations1978John Backus
A new class of computing systems uses the functional programming style both in its programming language and in its state transition rules; these systems have semantics loosely coupled to states—only one state transition occurs per major computation.
Dryad
2,460 Citations2007Michael Isard, Mihai Budiu +3 more
The Dryad execution engine handles all the difficult problems of creating a large distributed, concurrent application: scheduling the use of computers and their CPUs, recovering from communication or computer failures, and transporting data between vertices.
Pig latin
1,744 Citations2008Christopher Olston, Benjamin Reed +3 more
A new language called Pig Latin is described, designed to fit in a sweet spot between the declarative style of SQL, and the low-level, procedural style of map-reduce, which is an open-source, Apache-incubator project, and available for general use.
UC BerkeleyMesos: a platform for fine-grained resource sharing in the data center
1,593 Citations2011Benjamin Hindman, Andy Konwinski +6 more
The results show that Mesos can achieve near-optimal data locality when sharing the cluster among diverse frameworks, can scale to 50,000 (emulated) nodes, and is resilient to failures.
Proceedings of the VLDB EndowmentHive
1,539 Citations2009Ashish Thusoo, Joydeep Sen Sarma +7 more
Hadoop is a popular open-source map-reduce implementation which is being used as an alternative to store and process extremely large data sets on commodity hardware.
Delay scheduling
1,380 Citations2010Matei Zaharia, Dhruba Borthakur +4 more
This work proposes a simple algorithm called delay scheduling, which achieves nearly optimal data locality in a variety of workloads and can increase throughput by up to 2x while preserving fairness.
Journal of the ACMScheduling multithreaded computations by work stealing
1,326 Citations1999Robert D. Blumofe, Charles E. Leiserson
Communications of the ACMParallel database systems
1,281 Citations1992David J. DeWitt, Jim Gray
Over the last decade 'Eradata, Tandem, and a host of startup companies have successfully developed and marketed highly parallel machines that refutes a 1983 paper predicting the demise of database machines.
X10
1,268 Citations2005Philippe Charles, Christian Grothoff +6 more
A modern object-oriented programming language, X10, is designed for high performance, high productivity programming of NUCC systems and an overview of the X10 programming model and language, experience with the reference implementation, and results from some initial productivity comparisons between the X 10 and Java™ languages are presented.
ACM Transactions on Programming Languages and SystemsMULTILISP: a language for concurrent symbolic computation
1,072 Citations1985Robert H. Halstead
A recommended Multilisp programming style is presented which, if followed, should lead to highly parallel, easily understandable programs.
Hive - a petabyte scale data warehouse using Hadoop
925 Citations2010Ashish Thusoo, Joydeep Sen Sarma +7 more
Hive is presented, an open-source data warehousing solution built on top of Hadoop that supports queries expressed in a SQL-like declarative language - HiveQL, which are compiled into map-reduce jobs that are executed using Hadoops.
Quincy
852 Citations2009Michael Isard, Vijayan Prabhakaran +4 more
It is argued that data-intensive computation benefits from a fine-grain resource sharing model that differs from the coarser semi-static resource allocations implemented by most existing cluster computing architectures.
Proceedings of the VLDB EndowmentSCOPE
731 Citations2008Ronnie Chaiken, B. Keith Jenkins +5 more
A new declarative and extensible scripting language, SCOPE (Structured Computations Optimized for Parallel Execution), targeted for this type of massive data analysis, designed for ease of use with no explicit parallelism, while being amenable to efficient parallel execution on large clusters.
Operating Systems Design and ImplementationDryadLINQ: a system for general-purpose distributed data-parallel computing using a high-level language
699 Citations2008Yuan Yu, Michael Isard +5 more
IEEE Transactions on Knowledge and Data EngineeringWhat you always wanted to know about Datalog (and never dared to ask)
691 Citations1989Stefano Ceri, Georg Gottlob +1 more
The syntax and semantics of Datalog and its use for querying a relational database are presented, and the most relevant methods for achieving efficient evaluations of Daloog queries are presented.
Proceedings of the VLDB EndowmentHaLoop
688 Citations2010Yingyi Bu, Bill Howe +2 more
HaLoop is presented, a modified version of the Hadoop MapReduce framework that is designed to serve iterative applications and dramatically improves their efficiency by making the task scheduler loop-aware and by adding various caching mechanisms.
MapReduce online
682 Citations2010Tyson Condie, Neil Conway +4 more
A modified version of the Hadoop MapReduce framework that supports online aggregation, which allows users to see "early returns" from a job as it is being computed and also supports continuous queries, which enable MapReduce programs to be written for applications such as event monitoring and stream processing.
Universality of data retrieval languages
633 Citations1979Alfred V. Aho, Jeffrey D. Ullman
Although relational algebra and relational calculus satisfy these principles, there are certain queries involving least fixed points that cannot be expressed by these languages, yet that also satisfy the principles.
Communications of the ACMProgramming parallel algorithms
449 Citations1996Guy E. Blelloch
This research on parallel algorithms has not only improved the general understanding of par-allelism but in several cases has led to improvements in sequential algorithms.
CERN Document Server (European Organization for Nuclear Research)PNG: The Definitive Guide
391 Citations1999G. R. Roelofs, Richard Koman
IEEE Transactions on Parallel and Distributed SystemsThe Design of OpenMP Tasks
379 Citations2009Eduard Ayguadé, Nawal Copty +7 more
The paper summarizes the efforts of the sub-committee in designing, evaluating and seamlessly integrating the tasking model into the OpenMP specification, and compares a prototype implementation of thetasking model with existing models, and evaluates it on a wide range of applications.
MapReduce for Data Intensive Scientific Analyses
378 Citations2008Jaliya Ekanayake, Shrideep Pallickara +1 more
This paper presents CGL-MapReduce, a streaming-based MapReduce implementation and compares its performance with Hadoop, and presents the experience in applying the MapReduced technique for two scientific data analyses: high energy physics data analyses; and K-means clustering.
Piccolo: building fast, distributed programs with partitioned tables
268 Citations2010Russell Power, Jinyang Li
ACM SIGMOD RecordSQL
143 Citations1999Andrew Eisenberg, Jim Melton
The proposed SQL:1999 is much more than merely SQL-92 plus object technology, and involves additional features that the authors consider to fall into SQL's relational heritage, as well as a total restructuring of the standards documents themselves with an eye towards more effective standards progression in the future.
Boom analytics
135 Citations2010Peter Alvaro, Tyson Condie +4 more
This paper used the Overlog language to implement a "Big Data" analytics stack that is API-compatible with Hadoop and HDFS and provides comparable performance and presents both quantitative and anecdotal results, providing some concrete evidence that both data-centric design and declarative languages can substantially simplify distributed systems programming.
Adaptive and reliable parallel computing on networks of workstations
115 Citations1997Robert D. Blumofe, Philip A. Lisiecki
This paper presents the design of Cilk-NOW, a runtime system that adaptively and reliably executes functional Cilk programs in parallel on a network of UNIX workstations and shows how these decisions allow the design to exploit high-level algorithmic properties of the Cilk programming model in order to simplify and streamline the implementation.
Lecture notes in computer scienceThe Design and Implementation of Glasgow Distributed Haskell
35 Citations2001Robert F. Pointon, Phil Trinder +1 more
The design and implementation of Glasgow distributed Haskell is presented, a non-strict distributed functional language intended for constructing scalable, reliable distributed applications, and is Haskell'98 compliant, being a superset of both Concurrent Haskell and Glasgow parallel Haskell.
Scripting the cloud with skywriting
27 Citations2010Derek G. Murray, Steven Hand
Skywriting is introduced: a Turing-powerful, purely-functional script language for describing distributed computations, and its main features are introduced, and a novel cooperative task farming execution engine is outlined.