Here’s a simple cute routing algorithm:
So, the problem is you are in congested clique model.
Meaning, at each round you can send bits on each edge.
And, each vertex has messages that they want to distribute, and each vertex is the recipient of at most messages.
Then the question is, how to route?
It turns out that it’s possible. I’m going to present something slightly weaker to start at least.
First, let’s suppose that everyone only has like messages that they want to distribute.
Then you could solve this as follows.
Everyone sends message to random people.
Each node that gets at most message passes it along.
ok, now we can handle a slightly higher number of messages like as follows:
Send message to random people.
Then in expectation less than people get multiple messages.
You can then inform the senders which messages failed to send. And this smaller number of people can try again.