The Clubs algorithm

  The Clubs algorithm organises gunk into clubs each with a single leader. This can then be used as a basis for higher level partitioning of the gunk processors. The size of the club is the communication radius of the leader, so the leader can talk to all members of its club. A club should contain only one leader, but otherwise clubs may overlap. This gives us an abstraction of a graph with nodes and edges, where edges are processors in two clubs and nodes are processors in three or more clubs. Another nice feature is that based on the geometry of the surface and the communication geometry we can give upper bounds on the number of clubs as well as the maximum degree of the graph.

  
Figure: Club algorithm main loop

The algorithm (figure ) works as follows

1. The algorithm runs for a fixed amount of time, global-timeout.
2. Each processor chooses a random duration, leader-timeout, which is less than the global timeout. Each processor waits until either the leader timeout time has passed or a message has arrived.
3. If the leader timeout duration passes without a message arriving (line 4), the processor declares itself as a club leader to all its neighbors.
4. If a processor hears a message (line 10) before becoming a leader it becomes a club member and spends the rest of its time listening for other leaders.
5. When all the global timeouts have occured, every processor is either member of a club or a leader.

Caveats -- by choosing a large range the probability of conflicts can be reduced to minimum. Otherwise, there needs to be conflict detection and resolution, which is not difficult but then the end time is also probabilistic.