Robust Aggregation Protocols for Large-Scale Overlay Networks∗Alberto MontresorDept. of Computer ScienceUniversity of Bologna, [email protected]´ark Jelasity†Dept. of Computer ScienceUniversity of Bologna, [email protected] BabaogluDept. of Computer ScienceUniversity of Bologna, [email protected] refers to a set of functions that provideglobal information about a distributed system. These func-tions operate on numeric values distributed over the systemand can be used to count network size, determine extremalvalues and compute averages, products or sums. Aggrega-tion allows important basic functionality to be achieved infully distributed and peer-to-peer networks. For example, ina monitoring application, some aggregate reaching a spe-cific value may trigger the execution of certain operations;distributed storage systems may need to know the total freespace available; load-balancing protocols may benefit fromknowing the target average load so as to minimize the trans-fered load. Building on the simple but efficient idea of anti-entropy aggregation (a scheme based on the anti-entropyepidemic communication model), in this paper we intro-duce practically applicable robust and adaptive protocolsfor proactive aggregation, including the calculation of aver-age, product and extremal values. We show how the averag-ing protocol can be applied to compute further aggregateslike sum, variance and the network size. We present theoret-ical and empirical evidence supporting the robustness of theaveraging protocol under different scenarios.1. IntroductionThe latest generation of peer-to-peer (P2P) networks aretypically self-organizing, large-scale distributed systems.Unlike many traditional distributed systems, however, nei-ther a central authority nor a fixed communication topologyare employed to control the various components. Instead,a dynamically changing overlay network is maintained andcontrol is completely decentralized with “cooperation” linksamong nodes being created and deleted based on the re-quirements of the particular application. Such systems areattractive for several reasons, including the lack of singlepoints of failure, the potential to scale to millions of nodes,∗ This work was partially supported by the FET unit of the EuropeanCommission through Project BISON (IST-2001-38923).† also with MTA RGAI, SZTE, Szeged, Hungaryand the fact that they allow the creation of relatively inex-pensive distributed computin g platform s.The decentralized nature of such systems, how-ever, presents certain drawbacks. P2P systems tend to behighly dynamic, with a continuous flow of nodes join-ing and leav ing the network. Control and monitoring insuch systems are difficult tasks: performing global compu-tations requires orchestrating a huge number of nodes.A useful building block for monito ring and control inP2P system s is aggregation, which is the collective namegiven to a set of functions that provide statistical informa-tion about the system [10]. These functions include find-ing extremal values of some property, computing averagesand sums, etc. Aggregation can provide participants in a P2Pnetwork with important global information such as the sizeof the network or the average load in a network. Further-more, aggregation can be used as a building block for ob-taining more complex protocols. For example, the knowl-edge of the average load in a network can be exploited toimplement near-optimal load-balancing schemes [6].Aggregation protocols can be divided into two cate-gories: reactive and proactive. Reactive protocols respondto specific queries issued by nodes in the network. The an-swers are returned directly to the issuer of the query [3].Proactive protocols, on the other hand, continuously pro-vide the value of some aggregate to all nodes in the sys-tem in an adaptive fashion. By adaptive we mean that if theaggregate changes due to network dynamism or because ofvariations in the values being aggregated, the output of theaggregation protocol should follow this change reasonablyquickly. Proactive protocols are often useful when aggrega-tion is used as a building block for completely decentralizedprotocols. For example, in the load-balancing scheme citedabove, the knowledge of the average load is used by eachnode to decide when it can stop transferring load [6].In this paper we introduce a robust and adaptive proto-col for calculating aggregates in a proactive manner. Thecore of the protocol is a simple scheme [5] in which ag-gregation is performed in the style of an an ti-entropy epi-demic protocol, typically used for propagating updates indistributed databases [2]. Periodically, each node selects arandom peer and communicates with it to bring the twostates up-to-date. In our case, instead of resolving differ-ences between datab ases, the elementary step consists ofProceedings of the 2004 International Conference on Dependable Systems and Networks (DSN’04) 0-7695-2052-9/04 $ 20.00 © 2004 IEEEsome aggregation-specific computation based on the valuesmaintained by the two commun icating peers.Our contribu tion is threefold. First, we present a full-fledged practical solution for proactive aggregation in dy-namic environments, complete with mechanisms for adap-tivity, robustness and topology management. Second, weshow how our approach can be extended to compute addi-tional aggregates such as variances and products. Third, wepresent both theoretical and experimental evidence on therobustness of our protocol.2. System ModelWe consider a P2P network consisting of a large collec-tion of nodes that are assigned unique identifiers and thatcommunicate through message exchanges. The network ishighly dynamic; new nodes may join at any time, and exist-ing nodes may leave, either voluntarily or by crashing.Ourprotocol does not need any mechanism specific to leaves socrashes and voluntary leaves can be treated uniformly. Thus,in the following, we limit our discussion to node crashes.Byzantine failures, with nodes behaving arbitrarily, are ex-cluded from the present discussion (but see [7]).We assume that nodes are connected through an exist-ing routed network, such as the Internet, where every nodecan potentially communicate with every other node. To actu-ally communicate, a node has to know the identifiers of a setof other nodes, called its neighbors. This neighborhood re-lation over the nodes defines the topology of the overlay
View Full Document
Unlocking...