Skip to main content
Do Young Eun

Distributed and Efficient Randomized Algorithms for Large Networks

Sponsored by National Science Foundation through CAREER Award CNS-1217341
Do Young Eun (Dept. of ECE, North Carolina State University) 

Motivation

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.

Efficient Unbiased Graph Sampling 

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. 

Efficient CSMA Scheduling for Multihop Wireless Networks

Optimal-CSMA algorithms, variants of Glauber dynamics on graph, have been shown to achieve throughput optimality with fully distributed implementations similar to the usual CSMA algorithms. In this project, we devised a number of ways to improve the algorithms leading to smaller delay while preserving the throughput optimality, by incorporating `better’ Markov chains (than the original Glauber dynamics) and also past state information (high-order Markov chains)

  • Jaewook Kwak, Chul-Ho Lee, and Do Young Eun, “A High-order Markov Chain Based Scheduling Algorithm for Low Delay in CSMA Networks“, in IEEE INFOCOM, Toronto, Canada, April 2014
  • Jaewook Kwak and Do Young Eun, “An Antithetic Coupling Approach to Multi-Chain based CSMA Scheduling Algorithms”, in IEEE INFOCOM, San Francisco, CA, April 2016 (9 pages) (full tech. report)
  • Jaewook Kwak, Chul-Ho Lee, Do Young Eun, “A High-order Markov Chain Based Scheduling Algorithm for Low Delay in CSMA Networks”, IEEE/ACM Transactions on Networking, Vol. 24, No. 4, pages 2278-2290, Aug. 2016 (full version)
  • Jaewook Kwak, Chul-Ho Lee, and Do Young Eun, “Exploiting the Past to Reduce Delay in CSMA Scheduling: A High-Order Markov Chain Approach,” in ACM SIGMETRICS (short paper), Pittsburgh, PA, June 2013 (full paper)
  • Jin-Ghoo Choi and Do Young Eun, “Optimal CSMA Scheduling with Look Ahead Mechanism for Multihop Wireless Networks”, IEEE Wireless Communications Letters, Vol. 5, No. 5, pages 508–511, Oct.2016 (pdf)
  • Se-Young Yun, Yung Yi, Jinwoo Shin and Do Young Eun, ” Optimal CSMA: A Survey” (invited), in IEEE ICCS, Singapore, Nov. 2012
  • 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)

Other Applications

We have also conducted research on how information spreads over online social networks, more efficient algorithms for WiFi-sensing, efficient and randomized algorithms for wireless sensor networks, and how to inter-connect multiple layers of graphs to maximize the robustness of the inter-dependent networks against cascade failure. 

  • Xin Xu, Xin Chen, and Do Young Eun, “Modeling Time-Sensitive Information Diffusion in Online Social Networks“, in IEEE NetSciCom 2015 (Best Paper Award!)
  •  Jaeseong Jung, Yung Yi, Jeong-woo Cho, Do Young Eun, Song Chong, “Wi-Fi Sensing: Should Mobiles Sleep Longer As They Age?“, in IEEE INFOCOM, Turin, Italy, April 2013
  • Jaeseong Jeong, Yung Yi, Jeong-woo Cho, Do Young Eun, Song Chong, “Energy-Efficient Wi-Fi Sensing Policy under Generalized Mobility Patterns with Aging”, IEEE/ACM Transactions on Networking, Vol. 24, No. 4, pages 2416-2428, Aug. 2016
  • Srinjoy Chattopadhyay, Huaiyu Dai, Do Young Eun, and Seyyedali Hosseinalipour, “Designing Optimal Interlink Patterns to Maximize Robustness of Interdependent Networks Against Cascading Failures”, in IEEE Transactions on Communications, Vol 65, Issue 9, pages 3847-3862, Sept. 2017
  • Chul-Ho Lee and Do Young Eun, “Exploiting Heterogeneity for Improving Forwarding Performance in Mobile Opportunistic Networks: An Analytic Approach“, IEEE Transactions on Mobile Computing, Vol. 15, No. 1, pages 150-162, Jan. 2016
  • 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