d * hoặc các không gian tìm kiếm là đủ nhỏ (ví dụ: , O (n)) cho chúng tôi áp dụng các kỹ thuật được thảo luận trong phần trước. Giả sử rằng chúng tôi (bằng cách nào đó) biết Xếp hạng xếp hạng [d, D của một d mục dữ liệu trong D. Nếu Rank [d, D] = K sau đó d là yếu tố chúng tôi đang tìm kiếm. | CHAPTER 7 Computing in Presence of Faults INTRODUCTION In all previous chapters with few exceptions we have assumed total reliability that is the system is failure free. Unfortunately total reliability is practically nonexistent in real systems. In this chapter we will examine how to compute if possible when failures can and do occur. Faults and Failures We speak of a failure or fault whenever something happens in the systems that deviates from the expected correct behavior. In distributed environments failures and their causes can be very different in nature. In fact a malfunction could be caused by a design error a manufacturing error a programming error physical damage deterioration in the course of time harsh environmental conditions unexpected inputs operator error cosmic radiations and so forth. Not all faults lead immediately to computational errors . to incorrect results of the protocol but some do. So the goal is to achievefault-tolerant computations that is our aim is to design protocols that will proceed correctly in spite of the failures. The unpredictability of the occurrence and nature of a fault and the possibility of multiple faults render the design of fault-tolerant distributed algorithms very difficult and complex if at all possible. In particular the more components . entities links are present in the system the greater is the chance of one or more of them being becoming faulty. Depending on their cause faults can be grouped into three general classes execution failures that is faults occurring during the execution of the protocol by an entity examples of protocol failures are computational errors occurring when performing an action as well as execution of the incorrect rule. transmission failures due to the incorrect functioning of the transmission subsystem examples of transmission faults are the loss or corruption of a transmitted message as well as the delivery of a message to the wrong neighbor. Design and Analysis of .
