We investigate the hardness of establishing as many stable marriages (that is, marriages that last forever) in a population whose memory is placed in some arbitrary state with respect to the considered problem, and where traitors try to jeopardize the whole process by behaving in a harmful manner. On the negative side, we demonstrate that no solution that is completely insensitive to traitors can exist, and we propose a protocol for the problem that is optimal with respect to the traitor containment radius.
Self-stabilization @cite_16 @cite_7 @cite_15 is a versatile technique that permits forward recovery from any kind of transient faults, while Byzantine fault-tolerance @cite_2 is traditionally used to mask the effect of a limited number of malicious faults. In the context of self-stabilization, the first algorithm for computing a maximal marriage was given by Hsu and Huang @cite_17 . @cite_8 later gave a synchronous self-stabilizing variant of Hsu and Huang's algorithm. Finally, @cite_0 gave an algorithm for computing a maximal marriage under the distributed daemon. When it comes to improving the @math -approximation induced by the maximal mariage property, @cite_14 and Blair and Manne @cite_3 presented a framework that can be used for computing a maximum mariage in a tree, while @cite_6 gave a self-stabilizing algorithm for computing a @math -approximation in anonymous rings of length not divisible by three. later generalized this result to any arbitrary topology @cite_5 . Note that contrary to our proposal, none of the aforementioned marriage construction algorithms can tolerate Byzantine behaviour.
@cite_14 @cite_7 @cite_8 @cite_3 @cite_6 @cite_0 @cite_2 @cite_5 @cite_15 @cite_16 @cite_17
1817294132 2953267792 1541510840 1546022395
Self-stabilization is a versatile approach to fault-tolerance since it permits a distributed system to recover from any transient fault that arbitrarily corrupts the contents of all memories in the system. Byzantine tolerance is an attractive feature of distributed systems that permits to cope with arbitrary malicious behaviors. We consider the well known problem of constructing a maximum metric tree in this context. Combining these two properties proves difficult: we demonstrate that it is impossible to contain the impact of Byzantine nodes in a self-stabilizing context for maximum metric tree construction (strict stabilization). We propose a weaker containment scheme called topology-aware strict stabilization, and present a protocol for computing maximum metric trees that is optimal for this scheme with respect to impossibility result. Self-stabilization is a versatile approach to fault-tolerance since it permits a distributed system to recover from any transient fault that arbitrarily corrupts the contents of all memories in the system. Byzantine tolerance is an attractive feature of distributed systems that permits to cope with arbitrary malicious behaviors. We consider the well known problem of constructing a breadth-first spanning tree in this context. Combining these two properties proves difficult: we demonstrate that it is impossible to contain the impact of Byzantine nodes in a strictly or strongly stabilizing manner. We then adopt the weaker scheme of topology-aware strict stabilization and we present a similar weakening of strong stabilization. We prove that the classical @math protocol has optimal Byzantine containment properties with respect to these criteria. Self-stabilizing protocols can tolerate any type and any number of transient faults. However, in general, self-stabilizing protocols provide no guarantee about their behavior against permanent faults. This paper considers self-stabilizing link-coloring resilient to (permanent) Byzantine faults in arbitrary anonymous networks. First, we show that stabilizing link-coloring is impossible in anonymous cycles when there is no constraint on the spatial scheduling of processes. Then, given the assumption that no correct neighbors execute their actions simultaneously, we present a self-stabilizing link-coloring protocol that is also resilient to Byzantine faults in arbitrary anonymous networks. The protocol uses 2d-1 colors where d is the maximum degree in the network. This protocol guarantees that any link (u, v) between non faulty processes u and v is assigned a color within 2d+2 rounds and its color remains unchanged thereafter. Our protocol is Byzantine insensitive in the sense that the subsystem of correct processes remains operating properly in spite of unbounded Byzantine faults. Awareness of the need for robustness in distributed systems increases as distributed systems become integral parts of day-to-day systems. Self-stabilizing while tolerating ongoing Byzantine faults are wishful properties of a distributed system. Many distributed tasks (e.g. clock synchronization) possess efficient non-stabilizing solutions tolerating Byzantine faults or conversely non-Byzantine but self-stabilizing solutions. In contrast, designing algorithms that self-stabilize while at the same time tolerating an eventual fraction of permanent Byzantine failures present a special challenge due to the “ambition” of malicious nodes to hamper stabilization if the systems tries to recover from a corrupted state. This difficulty might be indicated by the remarkably few algorithms that are resilient to both fault models. We present the first scheme that takes a Byzantine distributed algorithm and produces its self-stabilizing Byzantine counterpart, while having a relatively low overhead of O(f′) communication rounds, where f′ is the number of actual faults. Our protocol is based on a tight Byzantine self-stabilizing pulse synchronization procedure. The synchronized pulses are used as events for initializing Byzantine agreement on every node’s local state. The set of local states is used for global predicate detection. Should the global state represent an illegal system state then the target algorithm is reset.