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)?