NDLI: Assigning tasks for efficiency in Hadoop: extended abstract

Please wait, while we are loading the content...

Buffer-space efficient and deadlock-free scheduling of stream applications on multi-core architectures

Database systems in the multicore era

Collaborative scoring with dishonest participants

Brief announcement: on speculative replication of transactional systems

Data-aware scheduling of legacy kernels on heterogeneous platforms with distributed memory

Basic network creation games

Algorithms and application for grids and clouds

The Cilkview scalability analyzer

Brief announcement: flashcrowding in tiled multiprocessors under thermal constraints

Low depth cache-oblivious algorithms

A local $O(n^{2})$ gathering algorithm

Implementing and evaluating nested parallel transactions in software transactional memory

Fast distributed approximation algorithms for vertex cover and set cover in anonymous networks

Simplifying concurrent algorithms by exploiting hardware transactional memory

Corrigendum: weakest failure detector for wait-free dining under eventual weak exclusion

Scheduling jobs with varying parallelizability to reduce variance

Securing every bit: authenticated broadcast in radio networks

Brief announcement: combine -- an improved directory-based consistency protocol

Online capacity maximization in wireless networks

Tree network coding for peer-to-peer networks

Towards optimizing energy costs of algorithms for shared memory architectures

Brief announcement: on regenerator placement problems in optical networks

Managing the complexity of lookahead for LU factorization with pivoting

Delays induce an exponential memory gap for rendezvous in trees

Transactions in the jungle

A work-efficient parallel breadth-first search algorithm (or how to cope with the nondeterminism of reducers)

A universal construction for wait-free transaction friendly data structures

Scheduling to minimize power consumption using submodular functions

Multi-sided shared coins and randomized set-agreement

Brief announcement: byzantine agreement with homonyms

Balls into bins with related random choices

Optimal gossip-based aggregate computation

Computing the throughput of probabilistic and replicated streaming applications

Brief announcement: a reinforcement learning approach for dynamic load-balancing of parallel digital logic simulation

New algorithms for efficient parallel string comparison

Best-effort group service in dynamic networks

Lightweight, robust adaptivity for software transactional memory

Parallel approximation algorithms for facility-location problems

Low-contention data structures

Assigning tasks for efficiency in Hadoop: extended abstract

Brief announcement: fun in numbers -- a platform for sensor-based multiplayer pervasive games

On the bit communication complexity of randomized rumor spreading

Brief announcement: locality-aware load balancing for speculatively-parallelized irregular applications

Deadlock avoidance for streaming computations with filtering

TLRW: return of the read-write lock

Flat combining and the synchronization-parallelism tradeoff

Brief announcement: Lower bounds on communication for sparse Cholesky factorization of a model problem

Brief announcement: serial-parallel reciprocity in dynamic multithreaded languages

Assigning tasks for efficiency in Hadoop: extended abstract

Content Provider	ACM Digital Library
Author	Yin, Yitong Fischer, Michael J. Su, Xueyuan
Abstract	In recent years Google's MapReduce has emerged as a leading large-scale data processing architecture. Adopted by companies such as Amazon, Facebook, Google, IBM and Yahoo! in daily use, and more recently put in use by several universities, it allows parallel processing of huge volumes of data over cluster of machines. Hadoop is a free Java implementation of MapReduce. In Hadoop, files are split into blocks and replicated and spread over all servers in a network. Each job is also split into many small pieces called tasks. Several tasks are processed on a single server, and a job is not completed until all the assigned tasks are finished. A crucial factor that affects the completion time of a job is the particular assignment of tasks to servers. Given a placement of the input data over servers, one wishes to find the assignment that minimizes the completion time. In this paper, an idealized Hadoop model is proposed to investigate the Hadoop task assignment problem. It is shown that there is no feasible algorithm to find the optimal Hadoop task assignment unless P = NP. Assignments that are computed by the round robin algorithm inspired by the current Hadoop scheduler are shown to deviate from optimum by a multiplicative factor in the worst case. A flow-based algorithm is presented that computes assignments that are optimal to within an additive constant.
Starting Page	30
Ending Page	39
Page Count	10
File Format	PDF
ISBN	9781450300797
DOI	10.1145/1810479.1810484
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2010-06-13
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Hadoop Mapreduce Approximation algorithm Load balancing Np-completeness Task assignment
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in