Title: Random Walks on Distributed Networks
Speaker: Masafumi Yamashita

Abstract: Random walks on finite graphs are a popular research area both in
mathematics and computer science.  For example, designing good random walks
is a key issue in sampling (i.e., Markov chain Monte Carlo method).  In
distributed computing, random walks, of course, have been recognized as a
central mechanism to design good distributed algorithms, since they give a
natural tool to search distributed networks for requested information.  When
applying random walks in sequential and distributed algorithms, there are
however two main differences in environments.  First sequential algorithms
typically consider random walks in static graphs, but distributed networks are
typically dynamic.  Second only very local information is available in
distributed algorithms, but sequential algorithms may be able to use some
global information.  In this talk, we discuss random walks on finite graphs,
focusing on the features of distributed networks.