Coordinator Pattern

Last updated on 16th July 2024

The curse of FullyConnected Groups

When connecting two Groups together, FullyConnected is generally the canonical choice as it gives the flexibility of having each agent from the source Group know each agent in the target Group.

This is fine for local models where the number of agents is generally small (less than 1 million agents) but when it comes time to scale your model up, you may encounter some critical slow downs.

This is due to the fact that the number of links increases fast compared to the number of agents.

If the size of your source Group and target Group are respectively n and m, the number of link to create is exactly n * m:

Sneaking one Group between the Source and the Target

One way to shrink down the number of links is to introduce an extra group between the source Group and the target Group of a smaller size. Its agents will be dedicated to transfer the messages from the source to the target, possibly aggregating them together. Those agents are called Coordinators.

If p is the size of the Coordinators ' Group; then the number of link is equal to p * m + n.

To give you an brief idea of the number of links for each situations, here are some results for a small number of agents.

n	m	# of links w/o Coordinators	# of links with Coordinators with p = log(n * m)	proportion of links avoided
10	100	1000	310	69.0 %
200	100	20000	630	96.8 %
1000	200	200000	2060	98.9 %
200	1000	200000	5501	97.2 %
10000	1000	10000000	17000	99.8 %

Let's now see how this transcribes the model.

Changing your model logic to use Coordinators

Let's say that you start with a model like this:

Naive implementation (Java)

public class CoordinatorPatternExample extends AgentBasedModel<GlobalState> {

    // Number of agents for each group
    public int n = 1000;
    public int m = 10000;

    @Override
    public void setup() {
        Group<SourceAgent> sourceGroup = generateGroup(SourceAgent.class, n);
        Group<TargetAgent> targetGroup = generateGroup(TargetAgent.class, m);

        sourceGroup.fullyConnected(targetGroup, Links.CoordinatorLink.class);
        super.setup();
    }
}

With those agents and this message minimally defined like so :

public class SourceAgent extends Agent<GlobalState> {}

public class TargetAgent extends Agent<GlobalState> {
  public void doSomething(int totalAmount, List<Long> sourceAgentIDs){}
}

We definitively in the first case described by the first figure.

Let's say the behaviour of the model is defined as a sequence with SourceAgents sending a message to the TargetAgents:

@Override
public void step() {
  run(
    Action.create(SourceAgent.class, sAgent -> {
      sAgent.getLinks(Links.CoordinatorLink.class).send(Messages.CoordinatorMessage.class, 1);
    }),

    Action.create(TargetAgent.class, tAgent -> {
      List<CoordinatorMessage> transfers = tAgent.getMessagesOfType(Messages.CoordinatorMessage.class);

      List<Long> sourceAgentIDs = new ArrayList<>();
      int totalAmount = 0;

      for (CoordinatorMessage message : transfers) {
        sourceAgentIDs.add(message.getSender());
        totalAmount += message.getBody();
      }

      tAgent.doSomething(totalAmount, sourceAgentIDs)
    })
  );
}
class CoordinatorMessage extends Message.Integer{}

At each tick, each SourceAgent sends a transfer message to all the theTargetAgents. Those latter agents can then doSomething with it then.

Here you can convert your model to use Coordinators between the SourceAgents and the TargetAgents as shown on the second figure.

You will also need another type of message, AggregatedTransferMessage.

class SourceAgent extends Agent<GlobalState> {}
class TargetAgent extends Agent<GlobalState> {
  public void doSomething(int totalAmount, List<Long> sourceAgentIDs) {
    // do something
  }
}
class Coordinator extends Agent<GlobalState> {}

class AggregatedTransferMessage extends Message {
  int amount;
  List<java.lang.Long> sourceAgents;
}

Essentially, the Coordinators will gather the Transfers sent by their SourceAgents and will remap them to all the TargetAgents.

@Override
public void step() {
  run(
      Action.create(SourceAgent.class, sAgent ->
      sAgent.getLinks(Links.CoordinatorLink.class)
      .send(Messages.CoordinatorMessage.class, 1);
      Action.create(Coordinator.class, coordinator -> {
        List<AggregatedTransferMessage> transfers =
          coordinator.getMessagesOfType(AggregatedTransferMessage.class);

        List<Long> sourceAgentIDs = new ArrayList<>();
        int totalAmount = 0;

        for (AggregatedTransferMessage message : transfers) {
          sourceAgentIDs.add(message.getSender());
          totalAmount += message.getBody().amount;
        }
        int finalTotalAmount = totalAmount;
        coordinator.getLinks(Links.CoordinatorLink.class)
        .send(AggregatedTransferMessage.class,
        message -> {
          message.amount = finalTotalAmount;
          message.sourceAgents = sourceAgentIDs;
        }
      });

      Action.create(
        TargetAgent.class, tAgent -> {
          List<AggregatedTransferMessage> aggregatedTransfers =
            tAgent.getMessagesOfType(AggregatedTransferMessage.class);
          List<Long> sourceAgentIDs = new ArrayList<>();
          int totalAmount = 0;
          for (AggregatedTransferMessage message : aggregatedTransfers) {
            sourceAgentIDs.addAll(message.sourceAgents);
            totalAmount = +message.amount;
          }
          tAgent.doSomething(totalAmount, sourceAgentIDs);
      })
    );
}

Modification of actions of initial agents

Here you will see that you need to change the actions of the `TargetAgents` slightly to use this pattern.

You can easily change the topologies of your model introducing two new lines and modify the `Connectors` to include the `Coordinators` :

Creating a coordinator group(Java)

public int p = (int) Math.log(n * m);

public Group<Coordinator> coordinators = system.generateGroup(Coordinator.class, p);

sourceGroup.partitionConnected(coordinators, Links.CoordinatorLink.class);
coordinators.fullyConnected(targetGroup, Links.CoordinatorLink.class);

We introduce p to represent the number of Coordinators to create.

About the definition of p

We set `p` to be a logarithmic expression of the number of agents, this is a good tradeoff between not having a high number of links and not having a bottle neck at the `Coordinators` level. You can change it at will.

At the end you end up having this file here:

Coordinator pattern (Java)

import simudyne.core.abm.*;
import simudyne.core.graph.Message;

import java.util.ArrayList;
import java.util.List;

public class CoordinatorPatternExample extends AgentBasedModel<GlobalState> {
  // Number of agents for each group
  public int n = 1000;
  public int m = 10000;
  public int p = (int) Math.log(n * m);

  @Override
  public void setup() {
    // Creating the groups
    Group<SourceAgent> sourceGroup = generateGroup(SourceAgent.class, n);
    Group<TargetAgent> targetGroup = generateGroup(TargetAgent.class, m);
    Group<Coordinator> coordinatorGroup = generateGroup(Coordinator.class, p);

    sourceGroup.partitionConnected(coordinatorGroup, Links.CoordinatorLink.class);
    coordinatorGroup.fullyConnected(targetGroup, Links.CoordinatorLink.class);
    super.setup();
  }

  @Override
  public void step() {
    run(
        Action.create(
            SourceAgent.class,
            sAgent ->
                sAgent
                    .getLinks(Links.CoordinatorLink.class)
                    .send(Messages.CoordinatorMessage.class, 1),
        Action.create(
            Coordinator.class,
            coordinator -> {
              List<AggregatedTransferMessage> transfers =
                  coordinator.getMessagesOfType(AggregatedTransferMessage.class);

              List<Long> sourceAgentIDs = new ArrayList<>();
              int totalAmount = 0;

              for (AggregatedTransferMessage message : transfers) {
                sourceAgentIDs.add(message.getSender());
                totalAmount += message.amount;
              }
              int finalTotalAmount = totalAmount;
              coordinator.getLinks(Links.CoordinatorLink.class)
                          .send(
                  AggregatedTransferMessage.class,
                  message -> {
                    message.amount = finalTotalAmount;
                    message.sourceAgents = sourceAgentIDs;
                  })
            }),
        Action.create(
            TargetAgent.class,
            tAgent -> {
              List<AggregatedTransferMessage> aggregatedTransfers =
                  tAgent.getMessagesOfType(AggregatedTransferMessage.class);

              List<Long> sourceAgentIDs = new ArrayList<>();
              int totalAmount = 0;

              for (AggregatedTransferMessage message : aggregatedTransfers) {
                sourceAgentIDs.addAll(message.sourceAgents);
                totalAmount = +message.amount;
              }

              tAgent.doSomething(totalAmount, sourceAgentIDs);
            }));
  }
}

class SourceAgent extends Agent<GlobalState> {}
class TargetAgent extends Agent<GlobalState> {
  public void doSomething(int totalAmount, List<Long> sourceAgentIDs) {
    // do something
  }
}
class Coordinator extends Agent<GlobalState> {}

class AggregatedTransferMessage extends Message {
  int amount;
  List<java.lang.Long> sourceAgents;
}
class CoordinatorMessage extends Message.Integer{}

Using PartitionConnected#weave()

If you have a look more closely at PartitionConnected, you'll see that this ConnectionStrategy exposes two sub-strategies:

weave() for weaved connections
shard() for shard connections.

In the case of the Coordinator Pattern, using one or the other can have different meanings.

Here is an example of coordinating agents on a grid. Here, the Coordinator Pattern allows agents to have informations about others agents that are not directly next to them.

This is the snippet used to create this topology:

Partition connected weave pattern (Java)

public Group<MyAgent> agents = generateGroup(MyAgent.class,16);
public Group<Coordinator> coordinators = generateGroup(Coordinators.class, 3);

agents.gridConnected(OnGrid.class, Links.CoordinatorLink.class);
agents.partitionConnected(coordinators, Links.CoordinatorLink.class);

This example is very simple but gives the intuition about what weaving the links between the agents and the coordinators allows.

Iterative Model Building Release Notes