Abstract
dc:descriptionIn this thesis we study three fundamental problems in hostile network environments. Our work lies in the area of Theoretical Computer Science and in particular in the area of Distributed Computing. We design distributed algorithms and we prove their correctness and computational complexity for the following problems. We study how identical mobile agents that move autonomously in a network and have only local information about the environment, can gather at a node of a network despite the presence of a hostile mobile agent which may prevent agents from visiting a node of the network. We also study how a number of agents that move autonomously and have only local information about the environment, might collectively decontaminate a network in which there is a virus capable of infecting an area of the network. Finally, we study how mobile agents that move autonomously in a network can learn a message initially carried by only one of the agents despite the fact that the agents cannot communicate from a distance, cannot leave messages at nodes of the network and many links of the network might unpredictably fail at any time. The above problems are often needed to be solved as an early step in order to solve other problems in distributed environments. Some of those problems have been previously studied either in safe environments or when static hostile entities are present. Here we investigate more general models in which either hostile mobile agents exist in the network, or a hostile behaviour can spread at the nodes of the network, or many unpredictable faults can occur in the network. We prove lower bounds on the number of mobile agents which are necessary in order to solve the problems and design optimal algorithms that meet those lower bounds. We show how those three important problems can be solved fast in severe hostile environments by autonomous mobile agents having very limited resources (e.g., very limited memory and no initial knowledge about the environment) and capabilities (e.g., no communication from a distance and no sensory abilities). Since in most cases our models are very weak, we hope that our techniques can be extended to handle different problems and systematically increase our knowledge in extremely malicious environments where the hostile behaviour can affect large and sometimes distant areas of the environment.
Degree
thesis:*- Grantor dc:publisher
- University of Thessaly (UTH)
- Year dc:date
- 2021
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Giachoudis, Nikolaos
- Γιαχούδης, Νικόλαος
Subjects
dc:subject × 17- Κατανεμημένοι υπολογισμοί
- Κατανεμημένοι αλγόριθμοι
- Κινητοί πράκτορες
- Θεωρητική πληροφορική
- Distributed computing
- Distributed algorithms
- Mobile agents
- Theoretical computer science
- Mobile agent gathering
- Broadcasting
- Black-virus decontamination
- Επιστήμη Ηλεκτρονικών Υπολογιστών και Πληροφορική
- Φυσικές Επιστήμες
- Επιστήμη ηλεκτρονικών υπολογιστών, θεωρία και μέθοδοι
- Computer and Information Sciences
- Natural Sciences
- Computer science, theory and methods
Rights
- Language dc:language
- eng
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/49764