- Current Title: Randomize Algorithms for Dynamic Sensor Networks
- Random Walk with Choice in General Metric Space
- Power of 2 Choice in (Randomize) Networks Algorithms

- 16/10 Discussion: Concentrate on the
:*Power of Choice*- The hitting time on the line for RWC is O(n
^{1.5}), for the lollipop O(n^{1.5}log(n)). Theoretical proofs. - Simulation results for planar subgraphs of RGG: RNG, GG, random delaunay triangulation.
- Prove that the complete graph gives the least possible improvement.
- The affect of choice on mixing time and particular gossip algorithms for sensor networks.
- Theoretical results for the most visited node in RWC in some graphs.

- The hitting time on the line for RWC is O(n
- Previous Topics:
- Improve random walk techniques for sensor networks. This includes the power of choice and reducing the resistance between nodes of interest.
- random walks on subgraph of random geometric graphs, like the delaunay triangulation and other planar subgraphs.

- trade-off between random walks and gossip in terms of energy and time. Combine both techniques and/or classify when to use each.
- Dynamic network (over time): many topics to cover. representation, mobility, links error, failure. What is a simple model that we can start with. There is a lot of space for theoretical work as well as simulation and I think the modeling itself is not a simple issue. Tzika has done some work in the area and there seems to be more work than I was aware of. Never the less I think there is much to do here. What are the question we want to ask on these models (after we'll have them)? connectivity, clustering, random walks, routing...
- determine the regions of dynamics for which it is better to use optimize deterministic algorithms and for which it is better to use randomize algorithms.

- Improve random walk techniques for sensor networks. This includes the power of choice and reducing the resistance between nodes of interest.

- What should be the main outcome? theoretical results, or we will also want to have practical side (which will require equipment and simulation.
- What is the focus of the work? We need to be very clear on want we want to achieve in the proposal.
- For a startup request (2 years, $60K) what is the expected outcome, 3-4 papers of the investigators? we need to contact the group here at BGU that deals with the proposals to find that out.

- Bhaskar and Tzika, sign up at the BSF site so I can add you to see the proposal on-line.
- Divide the workload
- set a time line for the work (taking into account the paper work that is required at each university, signatures , etc)

Retrieved from http://www.bgu.ac.il/~avin/pmwiki/pmwiki.php?n=Main.BSF2006

Page last modified on October 16, 2006, at 12:57 AM