Does a multi-agent system have to have a synchronous component in order for the agents to cooperate?

Question

During my programming assignments in multi-agent systems, I noticed that it feels impossible to get distributed agents to cooperate without a synchronous component. Let me explain what I mean by these terms:

Cooperation: I would loosely define this as any process which a single agent cannot solve without receiving non-static information from one or more other agents.

Example: Consider a system where two identical agents are needed to change a lightbulb. One agent needs to change the lightbulb itself, and one needs to hold the ladder.

Naturally, the problem is how to decide which agent is going to be the lightbulb changer and which the ladder holder. I have somehow arrived at the conclusion that this is impossible without the presence of a synchronous component in the system.

Without such a component, the agents could always get into an inconsistent state - for example, both would consider themself the holder, no matter how you decided how to assign those roles - if you were to choose, for example, a message sending system, where an agent would send to another "I will change the bulb, you hold the ladder", they could still send such a message at the same time. Similarly, if there was to be a "Leader" of those agents who would assign those roles, how would you decide which one was to be the leader? You just move the problem up a level.

Therefore, such problems are normally solved by methods such as assigning an unique integer identifier to each agent, and deciding based on this value (agents with higher value will become the leader, etc). Similarly, I have seen people use things like the time of the agent's entry into the system, the position of the agent in the environment, and so on.

However! All of those things are what I consider to be a synchronous component. Some entity has had to synchronously decide them - there is only a single time, a single person who assigns the identifiers, a single universe by which the agents' locations are defined, and so on.

I am pretty sure this statement holds. My question is: does there exist a theorem which states this or something similar (one that has been formally proven)?

Answer 1

You're asking about a problem known as leader election. There are various computational models one can consider, based on what we assume about how the network works and what agents are allowed to do.

The Wikipedia article claims there are no deterministic algorithms for leader election in a setting where all agents start from the same state (have no identity) and are situation in a ring (so connectivity is symmetrical); see https://en.wikipedia.org/wiki/Leader_election#Anonymous_rings.

At the same time, there are randomized algorithms for leader election that work if we make some assumptions about network delay (e.g., that messages won't be delayed forever), and if you're willing to accept algorithms with a finite expected running time. For instance, a very simple starting point is for each node to pick a random number and broadcast it, and then select the agent with the lowest number as the leader. In case of ties, repeat the entire procedure. There are additional details one must work out, depending on the model of computation and the assumptions about communication.

There's lots of research on this topic in the distributed systems literature. You might want to spend some time reviewing the papers that have been published in that field, to see what you can find.