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)


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)


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.


Back to Top

Do Young Eun's home page