Approximate agreement is a building block for fault-tolerant distributed systems. It is a formalisation for the basic operation of choosing a single real value (representing say speed) for use in later computation, reflecting the different approximations to this value reported from a number of possibly-faulty processors or sensors. We study the approximate agreement problem in distributed systems where processor failures are characterised depending on their severity. We develope a new algorithm that can tolerate up to b byzantine faults, a symmetric ones, and o send-omission faults. We analyse the convergence attained by this algorithm, and also give a universal bound on the convergence available to any algorithm no matter how complicated.
展开▼
