P2P communication

Paul stated some interesting graph theory questions here that he suspected were open.

Talked to Virginia about this — she suspects that these are not actually open.

Acks: thought about this with N.

Basic setup:

• Randomly choose of size .
• Connect each person to random people.

Easy mode: two functions

• LISTEN(ID) — pop the last message sent from person ID from the queue.
• SEND(ID, msg) — send a message to someone

Hard mode 1:

• You can only use these functions within the network topology

Hard mode 2:

• Some people are evil :O
• maybe need to be a bit careful to define this…

Hard mode 3:

• hard mode 1 + 2

Problems:

1. Choose two people randomly. must send a message to .
2. Choose pairs of people , all the ‘s must send message to ‘s.

---

Some thoughts:

Easy mode

Problem 1— it seems like the following thing just works:

• just broadcast-anate the message throughout the entire graph :)

Problem 2 — Paul described a protocol basically.

• todo write it down and analyze it

Hard mode 1

Problem 1, broadcasting message to whole graph still works

Problem 2

Let . Here’s a strategy for getting .

We basically

• chose a set of special guys.

• assign everyone canonically to a special guy

• we give each of the special guys a chance to talk to the whole graph (i.e. BFS broadcast) — after this, everyone learns a shortest path to their designated special node.

• Now, if you have a message for person , you send it to ‘s rep.

• Next, we repeat the following thing times:

  • each person sends a request for a message to their special node with probability, where by request I mean they send the path they want the message to return along.
  • special node acquiesces.

• To actually send the messages we just send them our designated special guy, who sends it to recipient’s designated special guy, who sends it to recipient.

todo flesh out details.

Q: Can you “recurse” this strategy?

---

Here’s an obstacle to “Recursing”:

Locally this kind of random graph is a tree. For instance, if you take the vertices closest to some vertex, then the induced subgraph on this set of vertices is a tree!

---

remark Nathan had a fun somewhat similar question — You have some cars on the hypercube , they all want to drive somewhere (distinct), Give a locally-computable strategy that achieves congestion and takes time for the drivers. The solution is quite nice:

• If destinations were random, then just flipping 1 bit at a time in order suffices.
• If destinations are adversarial, then first route people to random locations!

---

remark

• You can’t exchange messages efficiently on a tree :)
• This indicates that thinking about the problem “locally” isn’t a great idea.