Say you have 2N named peers (agents) able to address each other by their name and communicate freely among them.
What distributed algorithm could they use in order to randomly pair up? The final situation would be that the agents were able to organize themselves in N random couples. On different runs the random couples should be different.
Important: the algorithm should be “private” in the following sense: at the end of the round, each agent should only know the name of agent it was paired with.