Deterministic gathering with crash faults. Issue 2 (16th February 2018)

• Record Type: Journal Article
• Authors: Pelc, Andrzej
• Is Part Of: Networks. Volume 72:Issue 2(2018)
• Page Start: 182
• Page End: 199
• Publication Date: 2018-02-16
• Subjects: crash fault -- deterministic algorithm -- gathering -- mobile agent -- network; Network analysis (Planning) -- Periodicals; 658.4032
• DOI: 10.1002/net.21810
• Languages: English
• ISSNs: 0028-3045

Abstract

Abstract : A team consisting of an unknown number of mobile agents, starting from different nodes of an unknown network, have to meet at the same node and terminate. This problem is known as gathering . We study deterministic gathering algorithms under the assumption that agents are subject to crash faults which can occur at any time. Two fault scenarios are considered. A motion fault immobilizes the agent at a node or inside an edge but leaves intact its memory at the time when the fault occurred. A more severe total fault immobilizes the agent as well, but also erases its entire memory. Of course, we cannot require faulty agents to gather. Thus the gathering problem for fault prone agents calls for all fault‐free agents to gather at a single node, and terminate.