4

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.

4

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.