Machinations


PODC Day 3
June 13, 2011, 9:56 pm
Filed under: Uncategorized | Tags: , ,

The following is a guest post by Mahnush Mohavedi.  Mahnush is a first year PhD student at UNM.  She got her Masters degree from Amirkabir University of Technology in Iran and I believe this was her first conference in the U.S.

In the third day of PODC conference, there were several interesting talks including:

  • “Stability of P2P Communication Systems” by Ji Zhu and Bruce Hajek.  This paper discussed the missing piece syndrome in which one piece becomes very rare in a network like Bittorrent, leading to instability in the system. They calculate the minimum amount of help needed from the seed nodes in an information dissemination game in order to stabilize the system, and ensure that all nodes receive a file.
  • “Tight Bounds on Information Dissemination in Sparse Mobile Networks” by Pettarin, et al. is a study of the dynamics of information dissemination between k agents performing independent random walks on an n-node grid. They assume communication is determined by a dynamic communication graph process G_t, where two agents are connected in G_t iff their distance at time t is within a specified broadcast radius.  They assume that a rumor travels completely throughout a connected component of G_t during round t.  They study the broadcast time, T_B, of the system, which is the time it takes for all agents to know the rumor.  They study the sparse case for the broadcast radius, where, whp, all components are of size log n.  Their main result is that T_B is soft-Theta(n/\sqrt(k)).  In particular, for this sparse case, the broadcast time does not depend on the broadcast radius.
There were also some interesting brief announcements:
  • “Rationality Authority for Provable Rational Behavior” by Dolev et al. considers the games in which players are not totally rational and smart. They define a game inventor agent that is able to find the best response of the game and present it to the players. The inventor is rational and may gain revenues from the game. Thus, they introduce verifiers as trustable service providers that can verify inventor’s advices using formal methods. During dinner on Tuesday, I had a chance to talk to Elad who presented the talk. He believes separation of interest, benefits, and goals is the key idea of the work.
  • “Distributed Computing with Rules of Thumb” by Jaggard et al. indicates that a large and natural class of simple algorithms fails to guarantee convergence to an equilibrium in an asynchronous setting, even if the nodes and communication channels are reliably failure-free.  In particular, they consider algorithms like “best replying” to other player’s actions and minimizing “regret”.  They show that these algorithms fail to ensure convergence, in the asynchronous setting, for problems in routing, congestion control, social networks and circuit design.  
Advertisements

Leave a Comment so far
Leave a comment



Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s



%d bloggers like this: