T. White, Hadoop: The Definitive Guide. O'Reilly Media, 2012.

S. Kavulya, J. Tan, R. Gandhi, and P. Narasimhan, An Analysis of Traces from a Production MapReduce Cluster, 2010 10th IEEE/ACM International Conference on Cluster, Cloud and Grid Computing, pp.94-103, 2010.
DOI : 10.1109/CCGRID.2010.112

Z. Guo, G. C. Fox, and M. Zhou, Investigation of Data Locality in MapReduce, 2012 12th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing (ccgrid 2012), pp.419-426, 2012.
DOI : 10.1109/CCGrid.2012.42

D. Borthakur, HDFS Architecture Guide, p.39, 2008.

M. Zaharia, D. Borthakur, J. S. Sarma, K. Elmeleegy, S. Shenker et al., Delay scheduling, Proceedings of the 5th European conference on Computer systems, EuroSys '10, pp.265-278, 2010.
DOI : 10.1145/1755913.1755940

S. Ibrahim, H. Jin, L. Lu, B. He, G. Antoniu et al., Maestro: Replica-Aware Map Scheduling for MapReduce, 2012 12th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing (ccgrid 2012), pp.435-442, 2012.
DOI : 10.1109/CCGrid.2012.122
URL : https://hal.archives-ouvertes.fr/hal-00670813

M. Chowdhury and I. Stoica, Coflow, Proceedings of the 11th ACM Workshop on Hot Topics in Networks, HotNets-XI, pp.31-36
DOI : 10.1145/2390231.2390237

Z. Qiu, C. Stein, and Y. Zhong, Minimizing the Total Weighted Completion Time of Coflows in Datacenter Networks, Proceedings of the 27th ACM on Symposium on Parallelism in Algorithms and Architectures, SPAA '15, pp.294-303, 2015.
DOI : 10.1016/j.omega.2005.09.007

M. Hammoud and M. F. Sakr, Locality-Aware Reduce Task Scheduling for MapReduce, 2011 IEEE Third International Conference on Cloud Computing Technology and Science, pp.570-576, 2011.
DOI : 10.1109/CloudCom.2011.87

J. Tan, S. Meng, X. Meng, and L. Zhang, Improving ReduceTask data locality for sequential MapReduce jobs, 2013 Proceedings IEEE INFOCOM
DOI : 10.1109/INFCOM.2013.6566959

Q. Xie and Y. Lu, Degree-guided map-reduce task assignment with data locality constraint, 2012 IEEE International Symposium on Information Theory Proceedings, pp.985-989, 2012.
DOI : 10.1109/ISIT.2012.6284711

W. Wang, K. Zhu, L. Ying, J. Tan, and L. Zhang, Map task scheduling in MapReduce with data locality: Throughput and heavy-traffic optimality, 2013 Proceedings IEEE INFOCOM, pp.1609-1617, 2013.
DOI : 10.1109/INFCOM.2013.6566957

M. Isard, V. Prabhakaran, J. Currey, U. Wieder, K. Talwar et al., Quincy, Proceedings of the ACM SIGOPS 22nd symposium on Operating systems principles, SOSP '09, pp.261-276, 2009.
DOI : 10.1145/1629575.1629601

I. Gog, M. Schwarzkopf, A. Gleave, R. N. Watson, and S. Hand, Firmament: Fast, Centralized Cluster Scheduling at Scale, Symposium on Operating Systems Design and Implementation (OSDI). USENIX, pp.99-115, 2016.

P. Erdã?s and A. Rã?nyi, On Random Matrices, Studia Scientiarum Mathematicarum Hungarica, vol.8, pp.455-461, 1964.

D. W. Walkup, Matchings in random regular bipartite digraphs, Discrete Mathematics, vol.31, issue.1, pp.59-64, 1980.
DOI : 10.1016/0012-365X(80)90172-7
URL : https://doi.org/10.1016/0012-365x(80)90172-7

J. E. Hopcroft and R. M. Karp, An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs, SIAM Journal on Computing, vol.2, issue.4, pp.225-231, 1973.
DOI : 10.1137/0202019

A. Goel, M. Kapralov, and S. Khanna, Perfect Matchings in $O(n\log n)$ Time in Regular Bipartite Graphs, SIAM Journal on Computing, vol.42, issue.3, pp.1392-1404, 2013.
DOI : 10.1137/100812513
URL : http://arxiv.org/abs/0909.3346

J. Langguth, F. Manne, and P. Sanders, Heuristic initialization for bipartite matching problems, Journal of Experimental Algorithmics, vol.15, issue.1, pp.1-1, 2010.
DOI : 10.1145/1671970.1712656
URL : http://www.parallab.uib.no/%7Efredrikm/fredrik/papers/JEA2010.pdf

F. Dufossã?, K. Kaya, and B. Uã?ar, Two approximation algorithms for bipartite matching on multicore architectures, Journal of Parallel and Distributed Computing, vol.85, pp.62-78, 2015.
DOI : 10.1016/j.jpdc.2015.06.009

M. Raab and A. Steger, ???Balls into Bins??? ??? A Simple and Tight Analysis, Randomization and Approximation Techniques in Computer Science (RANDOM, pp.159-170, 1998.
DOI : 10.1007/3-540-49543-6_13

P. Berenbrink, T. Friedetzky, Z. Hu, and R. Martin, On weighted balls-into-bins games, Theoretical Computer Science, vol.409, issue.3, pp.511-520, 2008.
DOI : 10.1016/j.tcs.2008.09.023
URL : https://doi.org/10.1016/j.tcs.2008.09.023

M. Mitzenmacher, The power of two choices in randomized load balancing, IEEE Transactions on Parallel and Distributed Systems, vol.12, issue.10, pp.1094-1104, 2001.
DOI : 10.1109/71.963420

A. W. Richa, M. Mitzenmacher, and R. Sitaraman, The Power of Two Random Choices: A Survey of Techniques and Results, Combinatorial Optimization, vol.9, pp.255-304, 2001.

P. Berenbrink, A. Czumaj, A. Steger, and B. Vöcking, Balanced allocations, Proceedings of the thirty-second annual ACM symposium on Theory of computing , STOC '00, pp.745-754, 2000.
DOI : 10.1145/335305.335411

Y. Peres, K. Talwar, and U. Wieder, The (1 + ??)-Choice Process and Weighted Balls-into-Bins, Symposium on Discrete Algorithms (SODA). SIAM, pp.1613-1619, 2010.
DOI : 10.1137/1.9781611973075.131
URL : http://research.microsoft.com/pubs/104938/YPeres.pdf

P. Sanders, S. Egner, and J. Korst, Fast Concurrent Access to Parallel Disks, Algorithmica, vol.35, issue.1, pp.21-55, 2003.
DOI : 10.1007/s00453-002-0987-0
URL : http://www.mpi-sb.mpg.de/~sanders/courses/randalg/rda.ps.gz

A. Czumaj, C. Riley, and C. Scheideler, Perfectly Balanced Allocation, Approximation, Randomization, and Combinatorial Optimization (APPROX), pp.240-251, 2003.
DOI : 10.1007/978-3-540-45198-3_21
URL : http://www.cis.njit.edu/~czumaj/PUBLICATIONS/MyPublications/RANDOM-2003-LNCS.pdf

P. Sanders, Algorithms for Scalable Storage Servers, International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM, pp.82-101, 2004.
DOI : 10.1007/978-3-540-24618-3_8
URL : http://www.mpi-sb.mpg.de/~sanders/papers/storage.ps.gz

J. A. Cain, P. Sanders, and N. Wormald, The random graph threshold for k-orientiability and a fast algorithm for optimal multiple-choice allocation, Symposium on Discrete Algorithms (SODA). SIAM, pp.469-476, 2007.

C. Berge, TWO THEOREMS IN GRAPH THEORY, Proceedings of the National Academy of Sciences, vol.43, issue.9, pp.842-844, 1957.
DOI : 10.1073/pnas.43.9.842
URL : http://doi.org/10.1073/pnas.43.9.842

P. Hall, On representatives of subsets, Journal of the London Mathematical Society, issue.1, pp.1-10, 1935.

N. Revol and F. Rouillier, Motivations for an Arbitrary Precision Interval Arithmetic and the MPFI Library, Reliable Computing, vol.2, issue.3, pp.275-290, 2005.
DOI : 10.1007/978-3-7091-8577-3_15
URL : https://hal.archives-ouvertes.fr/inria-00072090

R. N°-8968 and R. Centre-grenoble-?-rhône-alpes, Inovallée 655 avenue de l'Europe Montbonnot 38334 Saint Ismier Cedex Publisher Inria Domaine de Voluceau -Rocquencourt BP 105 -78153 Le Chesnay Cedex inria, pp.249-6399