Gossip-based protocols are one of the popular approaches to estimate aggregates in large scale distributed systems. In this paper, we propose a gossip-based asynchronous and robust protocol to compute aggregates. In our protocol, each node employs the proposed pessimistic approach to exchange its local estimate with one of its neighbors and also uses the proposed recovery scheme which conserves the system mass in the presence of asynchrony and churn. The simulation results presented in this paper show that our protocol yields accurate aggregates in comparatively lesser time.

With the success of the peer-to-peer systems, there is an emerging trend to develop an aggregation service that can provide global information about these distributed and decentralized overlays. Existing aggregation protocols have focused on providing an efficient and cost effective solution to compute aggregates. In this paper, we are interested to search the node based on an aggregate query over rapidly changing data e.g., to seek a node with minimum/maximum workload in the network. Solution to such queries can benefit number of applications such as, node-ranking, reputation building, resource scheduling, etc. Here we propose a novel protocol to solve such queries. Our proposed protocol is reactive and pull-based in nature. It intrinsically builds and manages a routing table which routes aggregate query to the desired node in the system. We evaluated our protocol for accuracy, efficiency and communication cost through detailed simulations. We also discuss effects of an explicit routing table management scheme and show that this explicit scheme causes our protocol to work better in presence of churn and node failures.

The large scale and dynamic nature of a distributed system makes it difficult to collect the attributes of the individual nodes in the network. In these systems, often an aggregate (e.g. AVG, COUNT, MIN, MAX, SUM etc) of these attributes is adequate. Epidemic-style protocols are one of the popular approaches to estimate aggregates in such systems. In existing epidemic-style aggregation protocols the accuracy of the estimated aggregate at local nodes heavily depends upon synchronization of aggregation rounds. To enforce synchronization in these protocols, length of aggregation round should be long enough so that all the nodes in the system complete their aggregation information exchange. In this paper, we study the impacts of asynchrony in epidemic-style aggregation protocols. We present a simple asynchronous technique to estimate system aggregates in a distributed system. Based upon this technique, we analyze two popular existing epidemic-style aggregation protocols, Push-Pull and Push-Sum. Through detailed simulations, we evaluate accuracy and cost of asynchronous version of these protocols. We found that to obtain an estimate of the true system aggregate, aggregation protocols do not need to be synchronized and hence an efficient estimate can be obtained in lesser time.

Gossip-based protocols are a popular approach to estimate aggregates in P2P systems. For gossip-based aggregation protocols, the accuracy of the estimated aggregate heavily depends upon conservation of the system mass. In this paper, we present a gossip-based asynchronous aggregation protocol. Our protocol conserves the system mass under asynchronous settings and churn. Simulation results show that our proposed protocol converges to the correct system aggregate even in the presence of very dynamic and adverse network delays and under churn.

International Symposium on High Performance Distributed Computing (HPDC)

Due to mobility, energy limitations, and unreliable wireless channels, applications running on mobile devices suffer from faults such as temporary disconnection and data loss. We, therefore, need a fault tolerance mechanism to guarantee their smooth working and performance. In this paper, we present a novel proxy-based uncoordinated checkpointing scheme with pessimistic message logging for efficient fault recovery in mobile Grid system. Simulation results show that this scheme is reliable, efficient and, at the sametime, consumes less network traffic.