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, and distributed scheduling algorithms leading to maximal throughput and smaller delay in multihop wireless networks. At the heart of all such distributed and randomized algorithms lies the design of some version of a Markov chain such that (i) it possesses any desired stationary distribution, (ii) its transition probabilities depend only on locally available information on the fly with no or minimal amount of communication/computational overheads, and (iii) the chain itself converges fast (fast-mixing) or `efficient’. In particular, Markov Chain Monte Carlo (MCMC)-based approaches have proved to be extremely useful in building distributed network algorithms with near-optimal performance in various settings. 
This talk series consists of three parts.
 
Part I : 6月18日（周二）9:30-11:30
Part I is mostly of tutorial nature, where I will give necessary basics on MCMC for network applications, including random walk on graph, Metropolis-Hasting algorithm, graph coloring (Glauber dynamics), and randomized algorithms for combinatorial optimization problem (NP-hard) via Markov chains. This will set the stage and provide the backgrounds for the contents in Part II and III of this talk series. 
 
Part II : 6月18日（周二）14:00-16:00
In Part II,  I will demonstrate that there are a number of ways to improve a given Markov chain (a distributed network algorithm) so that it is more efficient with less temporal correlations overall, leading to improved network performance such as smaller delay in wireless scheduling and higher efficiency in unbiased graph sampling. This improvement hinges upon extending the design space from traditional Markov chains to a class of `better’ Markov chains, of higher-order chains for CSMA scheduling, as well as taking into account practical cost consideration in unbiased graph sampling. This part is mostly based on our past works that appeared in Sigmetrics and Infocom during 2012--2017.

Do Young Eun received his Ph.D. degree from Purdue University, West Lafayette, IN, in 2003. Since August 2003, he has been with the Department of Electrical and Computer Engineering at North Carolina State University, Raleigh, NC, where he is currently a professor. His research interests include network modeling and performance analysis, mobile ad-hoc/sensor networks, mobility modeling, graph sampling, and randomized algorithms for large (social and wireless) networks. He has been a member of Technical Program Committee of various conferences including IEEE INFOCOM, ACM MobiHoc, and ACM Sigmetrics. He served on the editorial board of IEEE/ACM Transactions on Networking and Computer Communications Journal, and was TPC co-chair of WASA'11. He received the Best Paper Awards in the IEEE ICCCN 2005, IEEE IPCCC 2006, and IEEE NetSciCom 2015, and the National Science Foundation CAREER Award 2006. He supervised and co-authored a paper that received the Best Student Paper Award in ACM MobiCom 2007.