DALD:-Distributed-Asynchronous-Local-Decontamination Algorithm in Arbitrary Graphs

محيط هاي شبكه اي گاهي اوقات ممكن است توسط عوامل مزاحم مورد حمله قرار گيرند. در شبكه ها هنگامي كه بعضي گره ها مشغول انجام محاسبات هستند بعضي عوامل مزاحم ممكن است تعدادي از گره ها را آلوده كنند. بنابراين مساله پاك سازي يك شبكه كه به وسيله عوامل مزاحم آلوده شده است، يكي از مسايل بسيار مهم به حساب مي آيد. ما در اين مقاله يك الگوريتم توزيع يافته همزمان محلي براي پاك سازي اين شبكه ها ارايه داده ايم. در بيشتر الگوريتم هاي ديگر يك عامل پاك كننده مركزي وجود دارد كه با حركت در شبكه شروع به پاك سازي آن مي كند. از آنجا كه اين روند به وسيله يك عامل پاك كننده انجام مي شود، الگوريتم پاك سازي بسيار كند عمل مي كند. در الگوريتم پيشنهادي ما، در ابتدا شبكه به تعدادي خوشه تجزيه شده است و سپس يك عامل پاك كننده مركزي در هر خوشه قرار داه شده است. بنابراين بيش از يك عامل پاك كننده در شبكه وجود دارد كه هر كدام از آنها مستقل از ديگري، از جاهاي مختلفي در خوشه هاي متفاوتي شروع به پاك سازي مي كنند. در اين حالت، شبكه سريع تر پاك سازي مي شود. همچنين در مقالات ديگر، كران بالا روي تعداد عوامل پاك كننده مورد نياز و تعداد حركت هاي اين عوامل، تنها روي شبكه هايي با ساختارهاي خاص مانند شبكه هايي با ساختار توري و حلقه بررسي شده است، در حالي كه در اين مقاله، اين كران ها را روي شبكه هايي با ساختارهاي دلخواه نيز به دست آورده‌ايم.

Network environments always can be invaded by intruder agents. In networks where nodes are performing some computations, intruder agents might contaminate some nodes. Therefore, problem of decontaminating a network infected by intruder agents is one of the major problems in these networks. In this paper, we present a distributed asynchronous local algorithm for decontaminating a network. In most of prior algorithms, there is a coordinator agent that starts from a node and decontaminates the network. Since this procedure is handled by an agent and in centralized mode decontamination algorithm is very slow. In our algorithm, the network is decomposed to some clusters and a coordinator is advocated to each cluster. Therefore, there is more than one coordinator that each of them starts from different nodes in the network and decontaminates network, independently. In this case, network is decontaminated faster. In addition, in previous works the upper bound of the number of moves and the number of cleaner agents required to decontaminate network are given only for networks with special structures such as ring or tori while our algorithm establishes these upper bounds on networks with arbitrary structure.