Maybe I wasn’t clear. The blockquoted part is (my phrasing of) the problem statement. In the slashdot thread (and this is all from memory), several correct, bounded solutions were posted. I’ll try to find the thread. (IIRC the original phrasing had a cup instead of a coin.)
The intuition behind the existence of a solution is that the prisoners can effectively send infinite one-bit messages between each other, while the king can only block a finite number of them, so they just need to choose a leader and run some “message accumulator” protocol that will reach a certain state when all prisoners are certain to have been in the CC.
Edit: Wow, that was actually easy to find. Here’s the discussion that spawned it, and here’s the thread that introduces this problem, and here’s a comment with a solution. Apparently, the problem has a name it goes by.
Doesn’t your comment on Slashdot indicate that there is no solution?
Maybe I wasn’t clear. The blockquoted part is (my phrasing of) the problem statement. In the slashdot thread (and this is all from memory), several correct, bounded solutions were posted. I’ll try to find the thread. (IIRC the original phrasing had a cup instead of a coin.)
The intuition behind the existence of a solution is that the prisoners can effectively send infinite one-bit messages between each other, while the king can only block a finite number of them, so they just need to choose a leader and run some “message accumulator” protocol that will reach a certain state when all prisoners are certain to have been in the CC.
Edit: Wow, that was actually easy to find. Here’s the discussion that spawned it, and here’s the thread that introduces this problem, and here’s a comment with a solution. Apparently, the problem has a name it goes by.
This is the comment that provoked mine. Your link and this do seem to be solutions, though.
There are some comments I wish I could delete from slashdot … and this site, for that matter … such as the parent.