stadium problem: Provide algorithm to solve the problem

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 assum开发者_如何学Cing 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...

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.

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!"

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.

For every column, a leader is chosen with the rule "the person in the row closest to the field is the leader" (these seats are usually filled). The leader initiates a count of the people in that column in the following manner:
1. Shake hand with the person directly sitting behind, and ask, "you?"
2. If no one is behind the person, the response should be 1, or else do step 1 with person behind, and the answer is one more than the answer from the person behind.
3. The leader immediately writes this number on a board, and holds it up
4. Among these leaders, the youngest person should start collecting these boards, and add them. If she meets a person younger than her collecting boards, the count till then is handed over to the other person. If the same age, the taller person would take over.

• Everyone drops their dacks, and the "output" is available in the local paper the next day ala "N people arrested at world's first mass-streaker incident". (i.e. the application asks the system to do the work).
• Each person picks one other person to fight, and first asks how many people they've knocked out. Winner finds another opponent, adds the defeated opponent's count. Last man (or woman) standing has the answer.
• Everyone stands up, plucks a hair, then hands it to someone nearby with at least as many hairs before sitting down again. Standing people continue to seek others to give hairs too. The last person counts the hairs.
• You invite people to grab a bag of minties from the canteen, then hand them around until they can't find anyone who hasn't had one, then drop the bag at a central point. Multiply bags * number-of-minties-per-bag - number-of-minties-left-in-bags.