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
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.