Tuesday, May 24, 2016
1:00 PM
Gahyun Park
Randomization in Distributed Computing


I will first present two famous existing papers that use randomization as a powerful method to achieve load balance in distributed settings. The first paper is "Balanced Allocations", so called multiple choice, which shows that the maximum bin load is exponentially reduced compared to that of the single choice balls into bins problem. I will present my work related to the multiple choice strategy and discuss how the scheme can be extended to a more general and parallel version. The second paper is "Consistent Hashing and Random Trees" which presents a random tree data structure based on consistent hashing which is effective to prevent hotspot. I will also present a new data structure that further optimizes the random tree.