- Start Date:
June 5, 2012
- Event Start Time:
2:00 PM
- Event End Time:
3:00 PM
- Organizers:
Gene Fiorini
- Seminar Series:
REU Seminar
- Presenter(s):
Donatella Firmani - Sapienza University of Rome
- Event Location:
DIMACS Seminar room
- Abstract:
In the MapReduce framework, originally proposed by Google, and its open source implementation, Hadoop, the computation is performed over a set of (key,value) pairs and consists of a map stage, a shuffle stage and a reduce stage. During each round of the computation, these stages are executed sequentially, while data-intensive operations executed by a single stage can be parallelized over many machines. Assuming that the communication cost of the machines and their space usage must be small with respect to the input size, the design of algorithms that minimize the number of rounds becomes quite challenging. This work describes various solutions to the undirected graph connectivity problem and minimum spanning tree, discussing recent results in literature and highlighting open problems.
