Abstract In this paper, we propose a novel, safe, and fault-tolerant on-demand concurrent authentication algorithm that concurrently verifies authentication requests of multiple processes by checking the legitimacy (or safety) of the server processes and those in the communication path between the requesters and their servers to implement propagation safety in the presence of transient faults and upon starting in an arbitrary system configuration. A server is the central trusted computing entity providing some services to the other processes in a communication network. A transient fault refers to a fault that perturbs the state of system processes but not their programs. Since the algorithm is safe, it ensures that authentication for a process is always achieved iff all the processes between the process and its corresponding server process are safe. Due to being able to start in an arbitrary system configuration, the proposed algorithm is scalable and does not require a reset or an initial setup. The on-demand property of the algorithm ensures that the authentication is activated only if some authentication requests are present. The authentication starts upon a request without a delay and takes $O(n)$ rounds, where $n$ is the height of the broadcast tree.

Propagation safety and propagation reliability, are important building blocks for secure network protocols, defense and safety mechanisms, and command and control systems. Propagation safety refers to the broadcasting of only those messages that have actually originated from a legitimate source. Propagation reliability, on the other hand, refers to the propagation of a message to every node in the system exactly once. In this paper, we first prove that it is impossible to devise a safe self- or snap-stabilizing broadcast algorithm. We then propose the first self- and snap-stabilizing broadcast algorithm with the propagation 1-safety and the propagation reliability properties. Starting in an arbitrary initial configuration or after a fault, our proposed algorithm implements propagation 1-safety ensuring that a spurious message, a message that did not originate from the legitimate root process, can be sent by a process to its neighbors, however, it cannot be forwarded further. In addition, the propagation reliability property of the proposed algorithm ensures that a legitimate message reaches all system processes exactly once.

Abstract In this paper, we propose the first efficient, reliable and safe snap-stabilizing $m$-$wave$ (multi-initiator wave) algorithm implementing concurrent waves started by multiple initiator processes in tree networks. Unlike its self-stabilizing counterpart and broadcast algorithms, the proposed algorithm is a reliable and safe $m$-wave algorithm, i.e. it implements an $m$-wave such that after it is started in an arbitrary initial configuration or after faults, the first $m$-wave started is guaranteed to reach all system processes as per its specification. In addition, the proposed $m$-wave algorithm increases the efficiency of the broadcast compared to a $1$-wave algorithm by allowing the broadcast to be initiated by multiple processes. Our proposed algorithm is safe in the sense that after initiating an $m$-wave, it completes as per the specifications. Additionally, it is reliable as the algorithm guarantees that each process receives at least one broadcast from an initiator process. Furthermore, the proposed algorithm significantly reduces the broadcast completion time compared to that of its single counterparts. Solutions to global-snapshots, distributed broadcast and various synchronization problems can be solved efficiently using waves with multiple concurrent initiators. In addition, the proposed algorithm has applications in mobile wireless sensor networks, VANETs and military communication networks.

Summary Star graphs possess many desirable properties such as scalable node degrees and diameters, which are essential to facilitate reduced routing table sizes and low maximum path length for routing in large P2P networks. In addition, because a large number of disjoint paths are available and each data/replica in ann‐star can be placed in an (n− 1)‐star, load balancing and alleviation of network bottlenecks can be implemented in star P2P overlay networks. Therefore, star networks have been proposed as viable alternatives to existing overlay topologies for large P2P networks. In this paper, we propose an optimal stabilizing and inherently stabilizing algorithm for routing messages over all disjoint paths between two peers in a star P2P overlay network. The algorithm is optimal in terms of its time complexity in rounds and the length of the longest path traversed by the messages, and fault tolerant due to being stabilizing and inherently stabilizing, allowing the system to withstand transient faults. The algorithm can be used to increase network reliability and survivability in P2P networks. In addition, the usage of all disjoint paths to route messages between two peers leads to increased network bandwidth while distributing the communication overhead across the network and eliminating network bottlenecks in P2P networks. Copyright © 2016 John Wiley & Sons, Ltd.

Many fundamental problems in the area of distributed systems such as security, reliable routing, network survivability and broadening available bandwidth can be addressed through the use of disjoint paths between communication endpoints. Therefore, distributed solutions to the disjoint paths problem are of crucial importance to these fundamental problems. Disjoint paths naturally exist in traditional networks; however, these networks provide no guarantees regarding the presence and the number of available disjoint paths. On the other hand, network topologies structured based on Caley graphs such as hypercube, star networks and their variations possess many desirable properties related to disjoint paths. Therefore, it is anticipated that backbones of future networks will be structured following some Caley graph topologies. In this paper, we present a simple novel stabilizing and inherently stabilizing algorithm to route messages over all node-disjoint paths of optimal length from one non-faulty process to another in at most n+1 rounds in an n-dimensional hypercube network in the presence of crash failures. The proposed algorithm can tolerate up to 2n−⌈log (n+1)⌉ process/link failures in the network and a maximum of ⌊(L−2)/3⌋ process/link failures on each disjoint path, where L is the number of processes on a disjoint path and the distance between any two failed processes/links is at least three. The proposed algorithm tolerates a large number of process and link failures, while delivering all n messages over optimal-length disjoint paths in the presence of maximum permissible process/link failures on each path. This is achieved by a simple uniform distributed algorithm using only local knowledge of failure locations.

The node-disjoint paths problem deals with finding node-disjoint paths from a source node s to target node t, where t ¿ s. Two paths from s to t are said to be node-disjoint iff they do not have any common vertices except for their endpoints. Distributed solutions to the node-disjoint paths problem have numerous applications such as secure message transmission, reliable routing, and network survivability. In this paper, we present a simple distributed algorithm that is both stabilizing and inherently stabilizing under a realistic model that describes system interfaces and implementation issues in detail to route messages over all shortest node-disjoint paths from one process to another in an n-dimensional hypercube network.

Synchronization is an important task in distributed computing since it allows asynchronous systems to simulate synchronous ones. Synchronization among distributed processes can be implemented using waves. A wave is a distributed execution, often made up of a broadcast phase followed by a feedback phase, requiring the participation of all the system processes before a particular event called decision is taken. Waves consisting of consecutive distinct broadcasts with corresponding feedbacks are referred to as a multi-wave. Solutions to a large number of fundamental problems in distributed computing such as distributed reset [1] and multiphase stabilization [10] require the completion of multi-waves. In this article, we propose a time and state-space optimal snap-stabilizing multi-wave algorithm implementing k distinct consecutive waves (k > 2) in a rooted tree, with O(kh) rounds of delay and at most k + 4 states per process, where h is the height of the tree. A system is said to be snap-stabilizing if it always behaves according to its specification [13]. One of the main advantages of the multi-wave algorithm being snap-stabilizing is that the arbitrary initial configuration has limited or no effect on the pace of the broadcast propagation.

Consider a distributed system that delivers a set of services (such as message routing, maintenance of a global invariant, leader election, mutual exclusion, and so forth) to a distributed application. Such a system often provides its services at all times, regardless of whether or not these services are in demand at any given time. This leads to wasteful use of system resources. In this paper, we propose a novel stabilizing protocol for deactivating the system services in the absence of demand and reactivating the services upon demand. The proposed protocol is simple enough. When a process needs a service, it periodically sends messages that reach every other process in the system and causes every process to reactivate the service. For this purpose, only a single-type message carrying no information is sent in the system. When no process needs the service, the sending of messages is stopped, causing every process to deactivate the service. The proposed system has many applications in mobile and sensor networks.

In this paper, we present a self-stabilizing algorithm for finding clustering of tree networks on a distributed model of computation. Clustering is defined as the covering of the nodes of a network by subtrees such that the intersection of any two subtrees is at most a single node and the difference between the sizes of the largest and the smallest clusters are minimal. The proposed algorithm evenly partitions the network into nearly the same size clusters and places resources and services for each cluster at its clusterhead to minimize the cost of sharing resources and using the services. Due to being self-stabilizing, the algorithm can withstand transient faults and does not require initialization. The paper includes a correctness proof of the algorithm. It concludes with remarks on issues such as open and related problems and the application areas of the algorithm.

In this paper, we propose a new Generalized Distribution-Based Handover (DBHO) to deal with the inefficient utilization of spectral resources due to the non-uniform cell loads. The DBHO scheme is different from the existing adaptive schemes since it uses a new criterion to initiate handover when moving from/to a congested cell. Two risk factors are used to dynamically change handover boundaries according to the distribution of traffic loads. This controls the handover initiation process such that a user in a congested cell that is moving to a free cell is allowed to initiate a handover to a new cell earlier, as long as the signal received from the target cell is higher than a certain threshold. While delaying the handover initiation process for a user moving in the opposite direction, as long as the signal received from the serving cell is not lower than a certain threshold. Our results show a substantial reduction in the handover and call dropouts rates. Our scheme is complementary to the existing adaptive schemes proposed in the literature. The proposed scheme also gives cellular system designers a new tool to optimize the overall network performance by initiating handovers based on the traffic intensities. Frequent handovers increase the load on switching networks, which consequently degrades the Quality of Service (QoS). Existing handover schemes usually use parameters such as the received signal strength for initiating a handover with some additional measurements to reduce unnecessary handovers and call dropouts. These schemes perform well when cell loads are somewhat evenly distributed, but fail to account for nonuniform traffic, as is often the case in microcells. Hence, it is desirable to design efficient handover schemes to avoid unnecessary handovers, reduce call dropouts and yet dynamically adapt to the variation of traffic among cells. In this paper, we present a new adaptive handover scheme that dynamically changes the handover boundaries to balance cell loads and to effectively reduce the average number of handovers. Copyright © 2004 John Wiley & Sons, Ltd.

Fairness assumptions have a great impact on distributed algorithms. They play a major role in determining the time complexity and the correctness of algorithms, since progress or freedom from various types of starvation may not be guaranteed without fairness assumptions. In this paper, we present a stabilizing deterministic algorithm allowing simultaneous execution of actions for strong fairness under weak fairness assumption, in addition, we show that the proposed algorithm yields a high degree of concurrency. We conclude the paper with some remarks on issues such as time optimal implementation of strong fairness and open problems related to fairness.

Locating a center or a median in a graph is a fundamental graph-theoretic problem. Centers and medians are especially important in distributed systems because they are ideal locations for placing resources that need to be shared among different processes in a network. This paper presents simple self-stabilizing algorithms for locating centers and medians of trees. Since these algorithms are self-stabilizing, they can tolerate transient failures. In addition, they can automatically adjust to a dynamically changing tree topology. After the algorithms are presented, their correctness is proven and upper bounds on their time complexity are established. Finally, extensions of our algorithms to trees with arbitrary, positive edge costs are sketched.

No abstract available.