Search

Proof-labeling schemes are known mechanisms providing nodes of networks with certificates that can be verified locally by distributed algorithms. Given a boolean predicate on network states, such schemes enable to check whether the predicate is satisfied by the actual state of the network, by having nodes interacting with their neighbors only. Proof-labeling schemes are typically designed for enforcing fault-tolerance, by making sure that if the current state of the network is illegal with respect to some given predicate, then at least one node will detect it. Such a node can raise an alarm, or launch a recovery procedure enabling the system to return to a legal state. In this paper, we introduce error-sensitive proof-labeling schemes. These are proof-labeling schemes which guarantee that the number of nodes detecting illegal states is linearly proportional to the Hamming distance between the current state and the set of legal states. By using error-sensitive proof-labeling schemes, states which are far from satisfying the predicate will be detected by many nodes. We provide a structural characterization of the set of boolean predicates on network states for which there exist error-sensitive proof-labeling schemes. This characterization allows us to show that classical predicates such as, e.g., cycle-freeness, and leader admit error-sensitive proof-labeling schemes, while others like regular subgraphs do not. We also focus on compact error-sensitive proof-labeling schemes. In particular, we show that the known proof-labeling schemes for spanning tree and minimum spanning tree, using certificates on O (log ⁡ n) bits, and on O (log 2 ⁡ n) bits, respectively, are error-sensitive, as long as the trees are locally represented by adjacency lists, and not just by parent pointers. • A new notion of distributed certification is defined, that ensures better fault-tolerance. • A structural characterization of the problems that admit such certification is proved. • Compact such certification are described and proved. [ABSTRACT FROM AUTHOR]

The use of multiple independent spanning trees (ISTs) for data broadcasting in networks provides a number of advantages, including the increase of fault-tolerance and secure message distribution. Thus, the designs of multiple ISTs on several classes of networks have been widely investigated. Kao et al. (2019) [18] proposed an algorithm to construct independent spanning trees in bubble-sort networks. The algorithm is executed in a recursive function and thus is hard to parallelize. In this paper, we focus on the problem of constructing ISTs in bubble-sort networks B n and present a non-recursive algorithm. Our approach can be fully parallelized, i.e., every vertex can determine its parent in each spanning tree in constant time. This solves the open problem from the paper by Kao et al. Furthermore, we show that the total time complexity O (n ⋅ n !) of our algorithm is asymptotically optimal, where n is the dimension of B n and n ! is the number of vertices of the network. • We present an algorithm for constructing multiple independent spanning trees in bubble-sort networks. • Our approach can be fully parallelized, thus solving an open problem from Kao et al. (2019). • We show that the total time complexity of our algorithm is asymptotically optimal. [ABSTRACT FROM AUTHOR]

Atomic Broadcast is an essential broadcast primitive as it ensures the consistency of distributed replicas. However, it is notoriously non-scalable. In this work, we introduce the Leaderless Hierarchical Atomic Broadcast (LHABcast) algorithm, which has two properties to improve scalability. First, it is a fully decentralized algorithm that does not rely on a sequencer/leader, which is often a significant bottleneck. Processes running LHABcast send messages with local sequence numbers and order messages received from other processes using timestamps inspired on Lamport's logical clocks. A process that receives the required set of timestamps can make a decision about the overall sequence of message delivery. Second, the algorithm is hierarchical: processes are organized on a vCube logical overlay network, which has several logarithmic properties and allows the construction of autonomous spanning trees. vCube also works as a failure detector, assuming crash faults and an asynchronous system model. In this paper, LHABcast is described, specified, and proven to be correct. Both simulation and experimental results are presented. A comparison with an all-to-all strategy shows that the number of messages sent by LHABcast is significantly lower in both fault-free and faulty scenarios. An implementation of LHABcast in Akka.io achieved up to 3.9 times higher throughput in fault-free scenarios than an implementation of the Raft-based Apache Ratis. • LHABcast is a fully decentralized leaderless algorithm broadcast algorithm. • LHABcast organizes processes on a vCube, which has several logarithmic properties. • LHABcast uses autonomic spanning trees rooted at the sender for message dissemination. • LHABcast is described with examples, and multiple properties are proved. • LHABcast was evaluated both with a Neko simulation and using the Java Akka framework. [ABSTRACT FROM AUTHOR]

• Improved distributed approximation for Steiner tree. • Approximation algorithms for Steiner tree in the CONGEST model of distributed computing. • Steiner tree problem in network optimization. In this paper we present two deterministic distributed algorithms for the Steiner tree (ST) problem in the CONGEST model. The first algorithm computes a 2 (1 − 1 / ℓ) -approximate ST using O (S + n log ⁎ ⁡ n) rounds and O (m S + n 3 / 2) messages for a graph of n nodes and m edges, where S is the shortest path diameter of the graph and ℓ is the number of leaf nodes in the optimal ST. It improves the round complexity of the best distributed ST algorithm known so far, which is O ˜ (S + min { S t , n }) [34] , where t is the number of terminal nodes. The second algorithm improves the message complexity of the first one by dropping the additive term of O (n 3 / 2) at the expense of a logarithmic multiplicative factor in the round complexity. We also show that for graphs with S = O (log ⁡ n) , a 2 (1 − 1 / ℓ) -approximate ST can be deterministically computed using O ˜ (n) rounds and O ˜ (m) messages and these complexities almost coincide with the results of some of the singularly-optimal minimum spanning tree (MST) algorithms proposed in [15,22,37]. [ABSTRACT FROM AUTHOR]

The protection routing uses the multi-paths technique for integrating route discovery and route maintenance mechanisms in a network, and thus it can tolerate the failure of one component (including a node or a link). Tapolcai (2013) proposed a method showing that a network possessing two completely independent spanning trees (CISTs for short) suffices to configure a protection routing. However, it is well-known that the problem of determining whether there exist two CISTs in a graph (or network) is NP-complete. In this paper, we extend Tapolcai's method such that the protection routing is configured by a combination of multiple CISTs. The first application of such an extension is that it can be used to deal with the problem of security in transmission, which we call the secure-protection routing scheme (SPR-scheme for short). Thus, a network transmission using the SPR-scheme ensures that no node other than the destination can receive the complete message. Moreover, we show that if a message M is transmitted in a network G using the SPR-scheme configured by a combination of n CISTs, then each intermediate node of G can receive a maximum of 2 ∕ n ratio of M. From a similar idea of the extension, another application is the so-called multiple-protection routing scheme (MPR-scheme for short) which can be used to increase the capability of fault-tolerance. For assessing the performance of routing using MPR-scheme, we first propose a construction of three CISTs in the two types of Möbius cubes, which are hypercube-variant networks and are superior to hypercubes due to having a smaller diameter. For the n -dimensional Möbius cube, the diameters of CISTs we constructed are at most 14 when n = 6 and at most 2 n + 1 when n ⩾ 7. So, we configure the desired protection routing in the Möbius cubes via the three CISTs. Then, we provide simulation results to experimentally evaluate the performance of the newly proposed MPR-scheme in the n -dimensional Möbius cubes for 6 ⩽ n ⩽ 10. As an important point, our results show that the adoption of routing using MPR-scheme will result in a significant slowdown in the transmission failure rate. • We propose a construction of three CISTs in a Möbius cube M Q n . • For n ⩾ 7 , the diameters of three CISTs of M Q n we constructed are at most 2n+1. • Protection routing employing MPR-scheme can increase the capability of fault-tolerance. • Protection routing using SPR-scheme ensures that no node other than the destination can receive the complete message. [ABSTRACT FROM AUTHOR]

Due to the application in reliable communication, reliable broadcasting, secure message distribution, etc., node/edge-independent spanning trees (ISTs) have attracted much attention in the past twenty years. However, node/edge conjecture is still open for networks with node/edge-connectivity ≥ 5. So far, results have been obtained on a lot of special networks, but only a few results are reported on the line graphs of them. Hypercubes play important roles in parallel computing systems, and the line graphs of which have been recently adopted for the architectures of data center networks. Since the line graph of n -dimensional hypercube Q n , L (Q n) , is (2 n − 2) -regular, whether there exist 2 n − 2 node-ISTs rooted at any node on L (Q n) is an open question. In this paper, we focus on the problem of constructing node-ISTs on L (Q n). Firstly, we point out that L (Q n) can be partitioned into 2 n − 1 complete graphs. Then, based on the complete graphs and n − 1 node-ISTs rooted at 0 on Q n − 1 0 , we obtain an "independent forest" containing 2 n − 2 trees on L (Q n). Furthermore, we present an O (N) time algorithm to construct 2 n − 2 node-ISTs rooted at node [0, 2 n − 1 ] isomorphic to each other on L (Q n) based on the independent forest, where N = n × 2 n − 1 is the number of nodes on L (Q n). In addition, we point out that the 2 n − 2 node-ISTs on L (Q n) is a new method to prove the node/edge-connectivity and the upper bound of (2 n − 2) -node/edge-wide-diameter of L (Q n). • We propose the definition of independent forest and use it to solve the node-independent spanning trees (ISTs) problem on L (Q n). • We design an O (N) time algorithm to construct 2 n − 2 node-ISTs rooted at node [0, 2 n − 1 ] in L (Q n) , where N = n × 2 n − 1 is the number of nodes in L (Q n). • The height of the node-ISTs is n + 2 and the trees are isomorphic to each other. • The 2 n − 2 node-ISTs in L (Q n) is a new method to prove the node/edge connectivity and the upper bound of (2 n − 2) -node/edge-wide-diameter of L (Q n). [ABSTRACT FROM AUTHOR]

Routing protocols are at the core of distributed systems performances, especially in the presence of faults. A classical approach to this problem is to build a spanning tree of the distributed system. Numerous spanning tree construction algorithms depending on the optimized metric exist (total weight, height, distance with respect to a particular process, …) both in fault-free and faulty environments. In this paper, we aim at optimizing the diameter of the spanning tree by constructing a minimum diameter spanning tree. We target environments subject to transient faults ( i.e. faults of finite duration). Hence, we present a self-stabilizing algorithm for the minimum diameter spanning tree construction problem in the state model. Our protocol has the following attractive features. It is the first algorithm for this problem that operates under the unfair and distributed adversary (or daemon ). In other words, no restriction is made on the asynchronous behavior of the system. Second, our algorithm needs only O ( log n ) bits of memory per process (where n is the number of processes), that improves the previous result by a factor n . These features are not achieved to the detriment of the convergence time, which stays polynomial. [ABSTRACT FROM AUTHOR]

Most of the existing work on topology control is to minimize the interference or delay separately. However, minimizing the interference and reducing the delay are two conflicting goals; therefore, considering a trade-off between them is necessary. In this paper, our goal is to minimize the interference while guaranteeing the end-to-end delay under a constraint. We take into account three optimization objectives, including the maximum interference, average interference and average path interference. We propose a centralized algorithm with a greedy strategy that can minimize the maximum interference while satisfying the delay constraint. A distributed algorithm (LDMST) is proposed to minimize the average interference. In LDMST, each node builds a delay-constrained minimum spanning tree (DMST). To minimize the path interference, a localized delay-constrained Bellman–Ford (LDBF) algorithm is proposed. LDBF employs an improved Bellman–Ford algorithm to find the optimal path, which has the minimum interference and satisfies the delay constraint. The final topology is composed of these optimal paths. The simulation results illustrate that the proposed topology control algorithms exhibit good performance in terms of the interference objectives and can also guarantee the end-to-end delay under the constraint. [ABSTRACT FROM AUTHOR]

Message broadcasting in networks can be efficiently carried over spanning trees. A set of spanning trees in the same network is node independent if two conditions are satisfied. First, all trees are rooted at the same node r . Second, for every node u in the network, all trees’ paths from r to u are node-disjoint, excluding the end nodes r and u . Independent spanning trees have applications in fault-tolerant communications and secure message distributions. Gaussian networks and two-dimensional toroidal networks share similar topological characteristics. They are regular of degree four, symmetric, and node-transitive. Gaussian networks, however, have relatively lesser network diameter that could result in a better performance. This promotes Gaussian networks to be a potential alternative for two-dimensional toroidal networks. In this paper, we present constructions for node independent spanning trees in dense Gaussian networks. Based on these constructions, we design routing algorithms that can be used in fault-tolerant routing and secure message distribution. We also design fault-tolerant algorithms to construct these trees in parallel. [ABSTRACT FROM AUTHOR]

A w -container C w ( u , v ) of a graph G between two distinct vertices u and v is a set of w disjoint paths between u and v . A w -container C w ( u , v ) is a w ∗ -container if every vertex of G is on some path in C w ( u , v ) . A graph G is said to be w ∗ -connected if there exists a w ∗ -container between any two distinct vertices u and v . The connectivity of the arrangement graph A n , k is k ( n − k ) . In this paper, we prove that A n , k is k ( n − k ) ∗ -connected for n − k ≥ 2 . [ABSTRACT FROM AUTHOR]

In this paper, we revisit two fundamental results of the self-stabilizing literature about silent BFS spanning tree constructions: the Dolev et al. algorithm and the Huang and Chen’s algorithm. More precisely, we propose in the composite atomicity model three straightforward adaptations inspired from those algorithms. We then present a deep study of these three algorithms. Our results are related to both correctness (convergence and closure, assuming a distributed unfair daemon) and complexity (analysis of the stabilization time in terms of rounds and steps). [ABSTRACT FROM AUTHOR]

Abstract: Independent spanning trees (ISTs) have increasing applications in fault-tolerance, bandwidth, and security. In this paper, we study the problem of parallel construction of ISTs on crossed cubes. We first propose the definitions of dimension-adjacent walk and dimension-adjacent tree along with a dimension property of crossed cubes. Then, we consider the parallel construction of ISTs on crossed cubes. We show that there exist general dimension-adjacent trees which are independent of the addresses of vertices in the -dimensional crossed cube . Based on dimension-adjacent trees and an arbitrary root vertex, a parallel algorithm with the time complexity is proposed to construct ISTs on , where . [Copyright &y& Elsevier]

Abstract: Reliable data broadcasting on parallel computers can be achieved by applying more than one independent spanning tree (IST). Using -IST-based broadcasting from root on an interconnection network provides -degree fault tolerance in broadcasting, while construction of optimal height -ISTs needs more time than that of one IST. In the past, most research focused on constructing ISTs on the hypercube , an efficient communication network. One sequential approach utilized the recursive feature of to construct ISTs working on a specific root in time. Another parallel approach was introduced for generating ISTs with optimal height on , based on HDLS (Hamming Distance Latin Square), single pointer jumping, which is applied for a source in time for successful broadcasting in . For broadcasting from , those existing approaches require a special routine to reassign new nodes’ IDs for logical . This paper proposes a flexible and efficient parallel construction of ISTs with optimal height on , a generalized approach, for an arbitrary root (, or ) in time. Our focus is to introduce the more efficient time of preprocessing, based on double pointer jumping over of the HDLS approach. We also prove that our generalized parallel -IST construction (arbitrary ) with optimal height on is correctly set in efficient time. Finally, experiments were performed by simulation to investigate the fault-tolerance effect in reliable broadcasting. Experimental results showed that our efficient ISTs yielded 10%–20% fault tolerance for successful broadcasting (on  PEs). [Copyright &y& Elsevier]

Abstract: Multiple independent spanning trees have applications to fault tolerance and data broadcasting in distributed networks. There are two versions of the independent spanning trees conjecture. The vertex (edge) conjecture is that any -connected (-edge-connected) graph has vertex-independent spanning trees (edge-independent spanning trees) rooted at an arbitrary vertex. Note that the vertex conjecture implies the edge conjecture. The vertex and edge conjectures have been confirmed only for -connected graphs with , and they are still open for arbitrary -connected graph when . In this paper, we confirm the vertex conjecture (and hence also the edge conjecture) for the -dimensional twisted cube by providing an algorithm to construct vertex-independent spanning trees rooted at any vertex, where denotes the number of vertices in . Moreover, all independent spanning trees rooted at an arbitrary vertex constructed by our construction method are isomorphic and the height of each tree is for any integer . [Copyright &y& Elsevier]