Abstract Thedistributed trigger counting (DTC)problem is a fundamental block for many distributed applications. Particularly, such a problem is to raise an alert while the number of triggers received by the whole system reaches a pre‐defined amount. There have been a few algorithms proposed to solve the DTC problem in the literature. However, these existing algorithms are all under the assumption that each process knows what kind of network topology the whole system forms as well as playing distinct kind of role in the system. The foregoing assumption is not practical for wireless sensor networks because the network topology of a wireless sensor network cannot be obtained in advance, and the roles of all processes are basically identical during the computation. In this paper, we propose a novel distributed algorithm to solve the DTC problem, free of any aforementioned global assumption. Moreover, in order to reduce the message complexity of our algorithm, we further propose a more message‐efficient version, only with one extra requirement that all processes have learned ahead the number of processes in the system. Copyright © 2016 John Wiley & Sons, Ltd.

The distributed trigger counting (DTC) problem is to raise an alert while the number of triggers received by the system reaches a pre-specified amount. Particularly, there have been several algorithms proposed to solve the DTC problem in the literature. However, these existing algorithms are all under the assumption that each node knows what kind of topology the whole system is as well as what kind of role it plays in the system. Obviously, such an assumption is not practical in wireless sensor networks since the topology of a wireless sensor network cannot be known in advance. In this paper, we propose a novel distributed algorithm to solve the DTC problem without any global assumption. Moreover, we further reduce the message complexity of the foregoing algorithm, and then propose a more message-efficient version, which is still not based on any global assumption.

Most existing global-snapshot algorithms in distributed systems use control messages to coordinate the construction of a global snapshot among all processes. Since these algorithms typically assume the underlying logical overlay topology is fully connected, the number of control messages exchanged among the whole processes is proportional to the square of number of processes, resulting in higher possibility of network congestion. Hence, such algorithms are neither efficient nor scalable for a large-scale distributed system composed of a huge number of processes. Recently, some efforts have been presented to significantly reduce the number of control messages, but doing so incurs higher response time instead. In this paper, we propose an efficient global-snapshot algorithm able to let every process finish its local snapshot in a given number of rounds. Particularly, such an algorithm allows a tradeoff between the response time and the message complexity. Moreover, our global-snapshot algorithm is symmetrical in the sense that identical steps are executed by every process. This means that our algorithm is able to achieve better workload balance and less network congestion. Most importantly, based on our framework, we demonstrate that the minimum number of control messages required by a symmetrical global-snapshot algorithm is Ω(N log N), where N is the number of processes. Finally, we also assume non-FIFO channels.

The agreement problem is usually exploited to improve the fault-tolerant capability of software systems. For self-organized networks like cloud computing architectures that possess highly decentralized and self-organized natures, consensus, which is essential to solving the agreement problem, in such networks cannot be achieved in the ways for traditional fixed networks. To address this problem of Consensus with Unknown Participants (CUP), a variant of the traditional consensus problem was proposed in the literature. Correspondingly, the CUP problem considering process crashes was also introduced, called the Fault-Tolerant Consensus with Unknown Participants (FT-CUP) problem. In this paper, we propose a new knowledge connectivity condition sufficient for solving the FT-CUP problem. Our new condition is weaker and more viable than an existing one, which is hard to implement in practice.

For self-organized networks that possess highly decentralized and self-organized natures, neither the identity nor the number of processes is known to all participants at the beginning of the computation because no central authority exists to initialize each participant with some context information. Hence, consensus, which is essential to solving the agreement problem, in such networks cannot be achieved in the ways for traditional fixed networks. To address this problem of Consensus with Unknown Participants (CUP), a variant of the traditional consensus problem was proposed in the literature, by relaxing the requirement for the original knowledge owned by every process about all participants in the computation. Correspondingly, the CUP problem considering process crashes was also introduced, called the Fault-Tolerant Consensus with Unknown Participants (FT-CUP) problem. In this paper, we propose a knowledge connectivity condition sufficient for solving the FT-CUP problem, which is improved from the one proposed in our previous work.

In this paper, we propose two new efficient indexing techniques for communication-induced checkpointing (CIC) protocols that can dynamically adjust their methods of managing sequence numbers during the execution, according to the heterogeneity extent of the underlying system.

This paper presents an efficient fault-tolerant approach for the super-peers of peer-to-peer (P2P) file sharing systems. In the super-peer based P2P file sharing system, peers are organized into multiple groups. In each group, it has a special peer called super peer to serve the regular peers within the group. In this hierarchical architecture, if the super peer departs (fails), any file queries to its serving regular peers cannot be delivered. In the proposed approach, we propose a multiple publication technique to make each regular peer logically connect with two or more super peers in other groups. If a regular peer finds that its serving super peer cannot work, one of its other connected super peers will be selected as its new serving super peer to continuously process the file queries. To examine the effectiveness of the proposed approach, comprehensive simulations are performed to quantify the performance and overhead of the proposed approach.

Communication-induced checkpointing (CIC) protocols can be used to prevent the domino effect. Among such protocols, those belonging to the index-based category associate checkpoints with sequence numbers in a way that checkpoints with an equal sequence number are ensured to be consistent. Specifically, index-based protocols must cooperate with their underlying indexing methods to achieve their goal. The adopted indexing scheme makes a great impact on the number of forced checkpoint the protocol will take. Moreover, an indexing method exhibit different performance for different degrees of heterogeneity imposed on a distributed system. All existing index-based protocols only employ a fixed indexing scheme, however, and thus cannot suit themselves well for all kinds of computing environments. In this paper, we propose two new indexing techniques that can adjust themselves according to the extent of present system heterogeneity. Those new methods are also justified by a simulation study in the text.

In this paper, we present an efficient route recovery approach for ad hoc networks, which modifies an existing ad hoc routing protocol (AODV) to enhance the recovery capability and reduce the recovery overhead. Under the proposed approach, each node on an active route (each active node) maintains a backup node. Once an active node moves (fails) to result in link breakages in its route, the broken active route can be locally repaired by moving the backup node of the moving (faulty) active only. Unlike previous approaches, the proposed approach does not incur the route discovery overhead. To achieve high recovery capability, the proposed approach also considers the backup node mobility. The backup node mobility is usually ignored on the previous approaches. Finally, we performed extensive simulations to demonstrate the effectiveness of the proposed approach over previous approaches in the recovery capability, overhead, and route length.

Communication-induced checkpointing (CIC) protocols can be used to prevent the domino effect. The fully-informed (FI) protocol proposed in the literature is known as the best CIC protocol so far. In this paper, we investigate some properties of such a protocol. First, we discover that an enhancement adopted by the FI protocol rarely takes effect in practice. In particular, we prove that such an enhancement is invalid over a tree communication network. Moreover, the size of the control information that the FI protocol piggybacks on application messages can be further reduced on such a type of network. Next, we show how to apply the FI protocol to another improved indexing strategy introduced in the literature. The management of a Boolean array in its control information carried on a message must be modified. Finally, we present a simulation study to analyze the properties of the FI protocol.

Communication-induced checkpointing (CIC) protocols can be used to prevent the domino effect. Such protocols that belong to the index-based category were shown to have a better performance. In this paper, we propose an efficient index-based CIC protocol. The fully informed (FI) protocol proposed in the literature has been known to be the best index-based CIC protocol that one can achieve since the optimal protocol needs to acquire the future information. We discover that the enhancement adopted by such a protocol rarely takes effect in practice. By discarding this enhancement, we obtain a new protocol, called NMMP. Simulation results show that our protocol is almost as efficient as FI in some typical computational environments. Especially, we demonstrate that the two protocols have the same behavior over a tree communication network. Surprisingly, NMMP only has to piggyback on each message control information of constant size, regardless of the number of processes.

Rollback-dependency trackability (RDT) is a property stating that all rollback dependencies between local checkpoints are online trackable by using a transitive dependency vector. Since the RDT property was introduced, many communication-induced checkpointing protocols satisfying such a property have been proposed in the literature. Most protocols can be classified as three families, PCM family, EPSCM family and PMM family, according to their underlying RDT characterizations. Up to now, several theoretical analyses on comparing the performance of RDT protocols were addressed, but simulation studies on this topic are rare and not comprehensive. We present a simulation study for comparing RDT protocols systematically. The simulation is carried out in different computational environments. We will not only verify the results from existing theoretical analyses, but also explore the impact of optimizations on protocols. Our results can provide guidelines for understanding the efficiency of RDT protocols.

Rollback-dependency trackability (RDT) is a property stating that all rollback dependencies between local checkpoints are online trackable by using a transitive dependency vector. The most crucial RDT characterizations introduced in the literature can be represented as certain types of RDT-PXCM-paths. Here, let the U-path and V-path be any two types of RDT-PXCM-paths. We investigate several properties of communication-induced checkpointing protocols that ensure the RDT property. First, we prove that if an online RDT protocol encounters a U-path at a point of a checkpoint and communication pattern associated with a distributed computation, it also encounters a V-path there. Moreover, if this encountered U-path is invisibly doubled, the corresponding encountered V-path is invisibly doubled as well. Therefore, we can conclude that breaking all invisibly doubled U-paths is equivalent to breaking all invisibly doubled V-paths for an online RDT protocol. Next, we continue to demonstrate that a visibly doubled U-path must contain a doubled U-cycle in the causal past. These results can further deduce that some different checkpointing protocols actually have the same behavior for all possible patterns. Finally, we present a commendatory systematic technique for comparing the performance of online RDT protocols.

The paper investigates the reliability of Mobile IP in a cellular system. To support the node mobility, a lot of mobility agents are deployed in the packet network of a cellular system to retain the continuous network connectivity while mobile nodes move their locations. If a mobility agent fails, the mobile nodes under its coverage area will be affected. The network connectivity of these mobile nodes will be disrupted. The main goal of this paper is to present an efficient approach to tolerating the failures of mobile agents. Once failures occur in a mobility agent, its in-progress and new-arrival workload can be redirected to other mobility agents. The mobile nodes under the mobility agent's coverage area do not lose their data executive ability. The overhead of the proposed fault-tolerant approach is also measured in terms of the performance degradation on other mobility agents by using an M/G/m/m queueing mode. The analytic results show that the performance degradation is very low if the workloads of the faulty mobility agent are not too heavy.

Domino-Effect Freedom (DEF) is a property stating that unbounded, cascading rollback propagation will not occur during the process of finding a consistent global checkpoint. DEF checkpointing protocols can be classified into two different categories: index-based and model-based. An index-based protocol timestamps local checkpoints with sequence numbers for achieving consistency, while a model-based one prohibits the formation of particular checkpoint and communication patterns in the execution. We explore several characteristics of communication-induced checkpointing protocols with the DEF property. First, we demonstrate that there is no optimal online scalar DEF protocol, in terms of the number of forced checkpoints. Then some techniques for comparing protocols are proposed. We construct some patterns or give formal proofs to compare the performance of both index-based and model-based protocols.

Rollback-Dependency Trackability (RDT) is a property that states that all rollback dependencies between local checkpoints are on-line trackable by using a transitive dependency vector. In this paper, we address three fundamental issues in the design of communication-induced checkpointing protocols that ensure RDT. First, we prove that the following intuition commonly assumed in the literature is in fact false: If a protocol forces a checkpoint only at a stronger condition, then it must take, at most, as many forced checkpoints as a protocol based on a weaker condition. This result implies that the common approach of sharpening the checkpoint-inducing condition by piggybacking more control information on each message may not always yield a more efficient protocol. Next, we prove that there is no optimal on-line RDT protocol that takes fewer forced checkpoints than any other RDT protocol for all possible communication patterns. Finally, since comparing checkpoint-inducing conditions is not sufficient for comparing protocol performance, we present some formal techniques for comparing the performance of several existing RDT protocols.