Adobe PDF (674.77 kB)
Title Details:
The problem of two mobile agents meeting
Authors: Markou, Evripidis
Kranakis, Evangelos
Pagourtzis, Aristeidis
Krizanc, Danny
Reviewer: Nikolopoulos, Stavros
Description:
Abstract:
Extensive reference is made to solving the problem of two mobile agents meeting in different network topologies, such as rings and tori networks. Negative results (models in which the meeting problem is unsolvable). Deterministic algorithms in synchronous and asynchronous networks are presented and analyzed. Proofs of correctness of algorithms and complexity analysis. Agent algorithms modeled with Turing machines. Algorithms for finite automata without memory. Algorithms for agents that can leave messages on the nodes or edges of the network. Probabilistic algorithms for meeting two agents in a ring. Random walk algorithms. Trade-offs between memory and time. The Coin Half Tour Algorithm.
Type: Chapter
Creation Date: 2015
Item Details:
License: http://creativecommons.org/licenses/by-nc-nd/3.0/gr
Handle http://hdl.handle.net/11419/5773
Bibliographic Reference: Markou, E., Kranakis, E., Pagourtzis, A., & Krizanc, D. (2015). The problem of two mobile agents meeting [Chapter]. In Markou, E., Kranakis, E., Pagourtzis, A., & Krizanc, D. 2015. Algorithmic theory of distributed computing [Undergraduate textbook]. Kallipos, Open Academic Editions. https://hdl.handle.net/11419/5773
Language: Greek
Is Part of: Algorithmic theory of distributed computing
Publication Origin: Kallipos, Open Academic Editions