A team of mobile agents, starting from different nodes of an unknown network, possibly at different times, have to meet at the same node and declare that they have all met. Agents have different labels and move in synchronous rounds along links of the network. The above task is known as gathering and was traditionally considered under the assumption that when some agents are at the same node then they can talk. In this paper we ask the question of whether this ability of talking is needed for gathering. The answer turns out to be no. Our main contribution are two deterministic algorithms that always accomplish gathering in a much weaker model. We only assume that at any time an agent knows how many agents are at the node that it currently occupies but agents do not see the labels of other co-located agents and cannot exchange any information with them. They also do not see other nodes than the current one. Our first algorithm works under the assumption that agents know a priori some upper bound N on the network size, and it works in time polynomial in N and in the length l of the smallest label. Our second algorithm does not assume any a priori knowledge about the network but its complexity is exponential in the network size and in the labels of agents. Its purpose is to show feasibility of gathering under this harsher scenario. As a by-product of our techniques we obtain, in the same weak model, the solution of the fundamental problem of leader election among agents. As an application of our result we also solve, in the same model, the well-known gossiping problem: if each agent has a message at the beginning, we show how to make all messages known to all agents, even without any a priori knowledge about the network. If agents know an upper bound N on the network size then our gossiping algorithm works in time polynomial in N, in l and in the length of the largest message.
We investigate avenues for the exchange of information (explicit communication) among deaf and dumb mobile robots scattered in the plane. We introduce the use of movement-signals (analogously to flight signals and bees waggle) as a mean to transfer messages, enabling the use of distributed algorithms among robots. We propose one-to-one deterministic movement protocols that implement explicit communication among asynchronous robots. We first show how the movements of robots can provide implicit acknowledgment in asynchronous systems. We use this result to design one-to-one communication among a pair of robots. Then, we propose two one-to-one communication protocols for any system of n *** 2 robots. The former works for robots equipped with observable IDs that agree on a common direction (sense of direction). The latter enables one-to-one communication assuming robots devoid of any observable IDs or sense of direction. All three protocols (for either two or any number of robots) assume that no robot remains inactive forever. However, they cannot avoid that the robots move either away or closer of each others, by the way requiring robots with an infinite visibility. In this paper, we also present how to overcome these two disadvantages. These protocols enable the use of distributing algorithms based on message exchanges among swarms of Stigmergic robots. They also allow robots to be equipped with the means of communication to tolerate faults in their communication devices.