Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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

1 Answer 1

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

 
discard

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.