Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|improve this question
up vote 4 down vote accepted

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.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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