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

d * = D [K], không biết đến chúng tôi, và điều duy nhất chúng ta biết về d * Xếp hạng thứ hạng của nó [d, d] = K. Một cách hiệu quả để xử lý các vấn đề phát hiện ra d * là để giảm thiểu càng nhiều không gian tìm kiếm có thể, loại bỏ từ xem xét nhiều mặt hàng càng tốt, cho đến khi chúng ta tìm thấy | 348 SYNCHRONOUS COMPUTATIONS Our goal is now to design protocols that can communicate any positive integer I transmitting k 1 packets and using as little time as possible. Observe that with k 1 packets the communication sequence is bo q1 b1 q2 b2 . qk bk . We will first of all make a distinction between protocols that do not care about the content of the transmitted protocols like C2 and C3 and those like R2 and R3 that use those packets to convey information about I. The first class of protocols are able to tolerate the type of transmission failures called corruptions. In fact they use packets only to delimit quanta as it does not matter what the content of the packet is but only that it is being transmitted these protocols will work correctly even if the value of the bits in the packets is changed during transmission. We will call them as corruption-tolerant communicators. The second class exploits the content of the packets to convey information about I hence if the value of just one of the bits is changed during transmission the entire communication will become corrupted. In other words these communicators need reliable transmission for their correctness. Clearly the bounds and the optimal solution protocols are different for the two classes. We will consider the first class in details the second types of communicators will be briefly sketched at the end. As before we will consider for simplicity the case when a packet is composed of a single bit that is c 1 the results can be easily generalized to the case c 1. Corruption-Tolerant Communication If transmissions are subject to corruptions the value of the received packets cannot be relied upon and so they are used only to delimit quanta. Hence the only meaningful part of the communication sequence is the k-tuple of quanta q1 q2 . qk . Thus the infinite set Qk of all possible k-tuples qb q2 . qk where the qi are nonnegative integers describes all the possible communication sequences. What we are going to do is .