Mobile agents rendezvous in spite of a malicious agent
Επιτομή
We examine the problem of rendezvous, i.e., having multiple mobile agents gather in a single node of the network. Unlike previous studies, we need to achieve rendezvous in presence of a very powerful adversary, a malicious agent that moves through the network and tries to block the honest agents and prevents them from gathering. The malicious agent can be thought of as a mobile fault in the network. The malicious agent is assumed to be arbitrarily fast, has full knowledge of the network and it cannot be exterminated by the honest agents. On the other hand, the honest agents are assumed to be quite weak: They are asynchronous and anonymous, they have only finite memory, they have no prior knowledge of the network and they can communicate with the other agents only when they meet at a node. Can the honest agents achieve rendezvous starting from an arbitrary configuration in spite of the malicious agent? We present some necessary conditions for solving rendezvous in spite of the malicious agent in arbitrary networks. We then focus on the ring and mesh topologies and provide algorithms to solve rendezvous. For ring networks, our algorithms solve rendezvous in all feasible instances of the problem, while we show that rendezvous is impossible for an even number of agents in unoriented rings. For the oriented mesh networks, we prove that the problem can be solved when the honest agents initially form a connected configuration without holes if and only if they can see which are the occupied nodes within a two-hops distance. To the best of our knowledge, this is the first attempt to study such a powerful and mobile fault model, in the context of mobile agents. Our model lies between the more powerful but static fault model of black holes (which can even destroy the agents), and the less powerful but mobile fault model of Byzantine agents (which can only imitate the honest agents but can neither harm nor stop them). © Springer International Publishing Switzerland 2015.
Collections
Related items
Showing items related by title, author, creator and subject.
-
Skeletal muscle relaxants in anaesthesiology
Benakis, A.; Plessas, C. T.; Plessas, S. T. (1999)During the 16th century, European explorers found that the Indians along the Amazon and Orinoco Rivers were using an arrow poison, named curare, that produced death by skeletal paralysis. Curare is one of several different ... -
Chios mastic gum: A plant-produced resin exhibiting numerous diverse pharmaceutical and biomedical prοperties
Dimas, K. S.; Pantazis, P.; Ramanujam, R. (2012)Chios mastic gum (CMG) is a resin produced by the plant Pistacia lentiscus var. chia. CMG is used to extract the mastic gum essential oil (MGO). CMG and MGO consist of nearly 70 constituents and have demonstrated numerous ... -
Drug-induced endocrinopathies and diabetes: A combo-endocrinology overview
Diamanti-Kandarakis E., Duntas L., Kanakis G.A., Kandaraki E., Karavitaki N., Kassi E., Livadas S., Mastorakos G., Migdalis I., Miras A.D., Nader S., Papalou O., Poladian R., Popovic V., Rachoń D., Tigas S., Tsigos C., Tsilchorozidou T., Tzotzas T., Bargiota A., Pfeifer M., on behalf of COMBO ENDO TEAM: 2018 (2019)In the currently overwhelming era of polypharmacy, the balance of the dynamic and delicate endocrine system can easily be disturbed by interfering pharmaceutical agents like medications. Drugs can cause endocrine abnormalities ...