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

Ví dụ, trong hầu hết các ứng dụng thực tế, số lượng các trang web là 10-100, trong khi số lượng dữ liệu ở mỗi trang web là ≥ 106. Những gì chúng ta cần là một chiến lược khác nhau để đối phó với trường hợp chung. Hãy để chúng tôi suy nghĩ của tập D có chứa các yếu tố N là một không gian tìm kiếm mà chúng ta cần phải tìm | 288 DISTRIBUTED SET OPERATIONS example in most practical applications the number of sites is 10-100 while the amount of data at each site is 106. What we need is a different strategy to deal with the general case. Let us think of the set D containing the N elements as a search space in which we need to find d D K unknown to us and the only thing we know about d is its rank Rank d D K .An effective way to handle the problem of discovering d is to reduce as much as possible the search space eliminating from consideration as many items as possible until we find d or the search space is small enough . O n for us to apply the techniques discussed in the previous section. Suppose that we somehow know the rank Rank d D of a data item d in D. If Rank d D K then d is the element we were looking for. If Rank d D K then d is too small to be d and so are all the items smaller than d. Similarly if Rank d D K then d is too large to be d and so are all the items larger than d. This fact can be employed to design a simple and as we will see rather efficient selection strategy Strategy RankSelect 1. Among the data items under consideration initially they all are choose one say d. 2. Determine its overall rank k Rank d D . 3. If k K then d d and we are done. Else if k K respectively k K remove from consideration d all the data items smaller respectively larger than d and restart the process. Thus according to this strategy the selection process consists of a sequence of iterations each reducing the search space performed until d is found. Notice that we could stop the process as soon as just few data items . O n are left for consideration and then apply protocol Rank. Most of the operations performed by this strategy are rather simple to implement. We can assume that a spanning tree of the network is available and will be used for all communication and an entity is elected to coordinate the overall execution becoming the root of the tree for this protocol . Any entity can act