stadium problem: Provide algorithm to solve the problem

Question

In a small stadium there are several thousand people in the stands. Devise a distributed algorithm enabling the audience to count itself. Do not assume any particular geometry of the stadium except, if you want, that it is bowl shaped. Explicitly state your assumptions, then present your algorithm and analysis

I was assuming the members to be a linked-list and appending the counter and free(ptr)..I may be wrong...Kindly provide some useful insights

Thanks in adv...

Answer 1

Assuming everyone can talk to his/her neighbor (possibly over many empty seats) and that fans of team A are willing to speak to fans of team B, the following could work:

Everyone grabs his/her nearest neighbor, who is not already grabbed by someone else, to form groups of at most two people. Now everyone remembers the size of the group they are in (can be 1 or 2). Now a leader of each group is chosen in a way that he is able to communicate to a member of another group. The leaders of each group try to join their group with one other and each member of the two (now joined) groups remembers the sum of the members of each group (this can be done by broadcasting the new value to be added to the group). This process continues until there is only one group left. Upon termination of this process everyone knows the number of people in the stadium.

Hope this helps.

Answer 2

In a small stadium there are several thousand people in the stands. Devise a distributed algorithm enabling the audience to count itself.

Feynman answer (see round manhole question): Have everyone shout "Several thousand!"

Answer 3

Here is another algorithm:

1. Let everyone count the others and himself.
2. Then, at the sound of a horn, each counter shout his count.
3. Keep the most shouted.

With this algorithm you can cope with errors.