Do Young Eun
(Dept. of ECE, North Carolina State University)
Designing efficient and distributed algorithms has been central to almost all large networked systems. Examples include crawling-based sampling of large online social networks, statistical estimation or inference from massive scale of networked data, efficient searching algorithms in unstructured peer-topeer networks, randomized routing and duty-cycling algorithm for better performance-energy tradeoff in wireless sensor networks, and distributed scheduling algorithms leading to maximal throughput and smaller delay in multihop wireless networks. Except for small-sized, static networks for which centralized design is not much of an issue, virtually all large networks necessarily demand distributed algorithms for inherent lack of global information and also randomized algorithms for autonomous load balancing and their resilience/robustness against possible points of failure/attacks, yet often with close-to-optimal performance.
The long-term goal of the proposed research is to explore all possible design spaces to systematically construct a class of randomized algorithms or Markov chains on a large graph in a completely distributed and decentralized manner, with proven long-term performance guarantee as well as better second-order behavior and higher efficiency. Our proposed work aims to break the barrier set by the current practice in the use of standard (reversible) random walk based algorithms or Metropolis- Hastings algorithms off the shelf, thereby unlocking the current performance limitations in the area of distributed algorithms in networks such as (i) efficient unbiased graph sampling, (ii) delay efficient and throughput-optimal CSMA-based wireless multihop scheduling, and (iii) randomized algorithms for power-delay efficient wireless sensor networks. Our work also bring significant contributions to the theoretical foundation on random walk based algorithms on graph and also be readily usable in a much broader range of applications, including efficient and randomized searching strategy in various networks, community detection in large graphs, network security and sybil attack/defense, among others, in all of which a version of random walk on graph or the Metropolis-Hastings algorithm has been the principal building block.
Unbiased estimation over a large graph such as online social networks has been done by crawling random walks including simple random walks (SRW) and Metropolis-Hastings random walk (MHRW) based on the classical Markov Chains Monte Carlo (MCMC) methods. In this project, we have developed efficient algorithms that outperform the SRW and MHRW that produce smaller asymptotic variance (AV) of the estimates (i.e., smaller number of samples required for a given error bound), by incorporating memory into the algorithms. We devised a systemic method to optimize a given MHRW on any arbitrary graph such that there exists no better (more efficient) Markov chain on the same graph achieving the same stationary distribution, in the sense of Peskun ordering. We have also demonstrated that the standard performance metric (AV) is defficient in fair comparison of several competing algorithms when the cost of sampling operations comes into play, and developed several cost-efficient unbiased sampling algorithms based on Markov chains on arbitrary large graphs.
Chul-Ho Lee, Xin Xu, and Do Young Eun, "Beyond Random Walk and Metropolis-Hastings Samplers: Why You Should Not Backtrack for Unbiased Graph Sampling", in ACM SIGMETRICS/Performance 2012 (31 out of 203), London, UK, June 2012 (short 12-page version, full paper in double-column ACM format)
Chul-Ho Lee, Do Young Eun, Se-Young Yun, Yung Yi, "From Glauber Dynamics To Metropolis Algorithm: Smaller Delay in Optimal CSMA", in IEEE International Symposium on Information Theory (ISIT), Cambridge, MA, July 2012 (short 5 page version)
Chul-Ho Lee, Jaewook Kwak, and Do Young Eun, “Towards Distributed Optimal Movement Strategy for Data Gathering in Wireless Sensor Networks,” IEEE Transactions on Parallel and Distributed Computing, Vol. 27, No. 2, pages 574-584, Feb. 2016
Back to Top