Oct 24
CS Tea Talk: Large Scale Distributed Graph Algorithms
As graphs become enormous (e.g., the Facebook 'friends' graph has a trillion edges!), it is becoming impossible to solve large-scale algorithmic graph problems on a single machine. This talk focuses on distributed graph algorithms, where the input graph is split into pieces and distributed across many machines. In this setting communication is the costliest resource and so machines need to communicate just enough with other machines to ensure correctness, but no more. I will present algorithmic techniques for the design of low-communication distributed graph algorithms. I will also present techniques from communication complexity and information theory for showing when such low-communication algorithms are impossible. We will begin with tea and cookies in CMC 328 and then move to CMC 301 for our talk.
← Return to site Calendar
Go to Campus Calendar →