Assume two nodes in a peer-to-peer network initiating a communication.
In this communication, one node has to serve as a “sender”, another as a “receiver” (role names are arbitrary here).
I’d like the nodes to assert either role with approximately equal probability. That is, in N communications with various other nodes a given node would assume the “sender” role roughly N/2 times. Since there’s no third-party arbiter available, nodes should agree on their roles by exchanging messages.
The catch is that we can encounter a rogue node which would try to become the “receiver” in most or all cases, and coax the other side to always serve as a “sender”.
I’m looking for an algorithm to assign roles to sides of communication so that no side could get a predetermined role with high probability. It’s OK for the side which is trying to cheat to fail to communicate.
It so happens that’s a variation on a problem for which someone asked a question in the game programming site: “Can adversarial agents flip coins?”
The solution to that problem would also solve this problem nicely.