tailieunhanh - DESIGN AND ANALYSIS OF DISTRIBUTED ALGORITHMS phần 3

Nếu đây không phải là trường hợp, vấn đề xây dựng các bảng định tuyến là khó khăn hơn để giải quyết. Một số phương pháp tuần tự truyền thống được dựa trên một cách tiếp cận lặp đi lặp lại. Ban đầu, mỗi thực thể x biết chỉ | 108 ELECTION Procedure INITIALIZE begin count 0 size 1 known false send Election id x size to right min id x end Procedure CHECK begin if count ringsize then if min id x then become LEADER else become FOLLOWER endif endif end FIGURE Procedures of protocol All the Way. for a total of n2 log id n bits. The time costs will be at most 2n Exercise . Summarizing M AlltheWay n2 T AlltheWay 2n - 1. The solution protocol we have just designed is very expensive in terms of communication costs in a network with 100 nodes it would cause 10 000 message transmissions . The protocol can be obviously modified so as to follow strategy Elect Minimum Initiator finding the smallest value only among the initiators. In this case those entities that do not initiate will not originate a message but just forward the others . In this way we would have fewer messages whenever there are fewer initiators. In the modification we must be careful. In fact in protocol All the Way we were using an entity s own message to determine n so as to be able to determine local termination. Now some entities will not have this information. This means that termination is again a problem. Fortunately this problem has a simple solution requiring only n additional messages and time Exercise . Summarizing the costs of the modified protocol All the Way Minit are as follows M AlltheWay Minit nk n T AlltheWay Minit 3n - 1 The modified protocol All the Way Minit will in general use fewer messages than the original one. In fact if only a constant number of entities initiate it will use only ELECTION IN RINGS 109 O n messages which is excellent. By contrast if every entity is an initiator this protocol uses n messages more than the original one. IMPORTANT. Notice that All the Way in its original or modified version can be used also in unidirectional rings with the same costs. In other words it does not require the Bidirectional Links restriction. We will return to this point later. .