DESIGN AND ANALYSIS OF DISTRIBUTED ALGORITHMS phần 2

và số lượng các hạng mục ban đầu, một thực thể ban đầu (Tập thể dục ). Lặp đi lặp lại xây dựng các bảng định tuyến giải pháp chúng tôi đã thấy được yêu cầu mỗi thực thể có sẵn tại địa phương lưu trữ, đủ để lưu trữ toàn bộ bản đồ của mạng. | 48 BASIC PROBLEMSAND PROTOCOLS PROTOCOL DF Status S INITIATOR IDLE AVAILABLE VISITED DONE Sinit iNiTIATOR IDLE Sterm DONE . Restrictions R UI. INITIATOR Spontaneously begin initiator true Unvisited N x next Unvisited send T to next send Visited to N x - next become VISITED end IDLE Receiving T begin Unvisited N x FIRST-VISIT end Receiving Visited begin Unvisited N x - sender become AVAILABLE end AVAILABLE Receiving T FIRST-VISIT Receiving Visited begin Unvisited Unvisited - sender end VISITED Receiving Visited begin Unvisited Unvisited - sender if next sender then VISIT endif end Receiving T begin Unvisited Unvisited - sender if next sender then VISIT endif end Receiving Return begin VISIT end ProtocolDF TRAVERSAL 49 Procedure FIRST-VISIT begin initiator false entry sender Unvisited Unvisited- sender if Unvisited 0 then next Unvisited send T to next send Visited to N x - entry next become VISITED else send Return to entry send Visited to N x - entry become DONE endif end Procedure VISIT begin if Unvisited 0 then next Unvisited send T to next else if not initiator then send Return to entry endif become DONE endif end FIGURE Routines used by Protocol DF IMPORTANT. The value of unlike n and m is not a system parameter. In fact it is execution-dependent. it may change at each execution value. We shall indicate this fact for f as well as for any other execution-dependent value by the use of the subscript . Traversal in Special Networks Trees In a tree network depth-first traversal is particularly efficient in terms of messages and there is no need of any optimization effort hacking . In fact in any execution of DF-Traversal in a tree no Backedge messages will be sent Exercise . Hence the total number of messages will be exactly 2 n 1 . The time complexity is the same as the optimized version of the protocol 2 n 1 . M DFTraversal Tree T DFTraversal Tree 2n 2 An interesting side effect of a depth-first traversal of a tree is that it .