Efficient and decentralized computation of approximate global state. - Keshav, S.
The need for efficient computation of approximate global state lies at the heart of a wide range of problems in distributed systems. Examples include routing in the Internet, sensor fusion, search in peer-to-peer networks, coordinated intrusion detection, and Top-K queries in stream-oriented databases. Efficient algorithms that determine approximate global state could enable near-optimal local decision-making with little overhead. In this position paper, we model this problem and summarize recent work on randomized algorithms that navigate a four-way tradeo between accuracy, robustness, performance and overhead. Despite these recent successes, many open problems remain. We believe that solving these problems can radically improve the design of robust, efficient and self-managed distributed systems
Keywords: Computer systems organization; Computer communication networks; Distributed systems; Network architecture and design; Internet; Performance of systems; Computing milieux; Management of computing and information systems; System management; Algorithms; Design; Management; Measurement; Performance; Theory