Project Goal

In this blog post I want to make it clear what the project objectives are and give the project an overarching goal.

Goal: To study distributed random walks, their properties and uses, in dynamic graphs.

Namely, we are interested in:

• hitting time of a random walk in a dynamic graph.
• cover time of a random walk in a dynamic graph.
• mixing time of a random walk in a dynamic graph.
• smoothed versions of these.
• computing hitting, cover and mixing times on various dynamic graphs by simulation.
• application of distributed random walks to solve $k$-gossip.
• other applications of distributed random walks.

Perhaps we could look into various algorithms for page rank using random walks.