Back to search

University of Thessaly (UTH)

Solving Fundamental Problems in Hostile Networks

Abstract

dc:description

In 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

Rights

Language dc:language
eng

Identifiers

dc:identifier.*
Identifier
10.12681/eadd/49764

Chain of custody

source
Harvested from
Greek National Archive of PhD Theses
Base URL
phdtheses.ekt.gr/eadd_oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Giachoudis, Nikolaos; Γιαχούδης, Νικόλαος. Solving Fundamental Problems in Hostile Networks. University of Thessaly (UTH), 2021. http://hdl.handle.net/10442/hedi/49764