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 |