73 research outputs found
Stabilizing Byzantine-Fault Tolerant Storage
No full textDistributed storage service is one of the main abstractions provided to developers of distributed applications due to its ability to hide the complexity generated by the various messages exchanged between processes. Many protocols have been proposed to build Byzantine-fault-tolerant (BFT) storage services on top of a message-passing system but none of them considers the possibility that well-behaving processes (i.e. correct processes) may experience transient failures due to, say, isolated errors during computation or bit alteration during message transfer. This paper proposes a stabilizing Byzantine-tolerant algorithm for emulating a multi-writer multi-reader regular register abstraction on top of a message passing system with n > 5f servers, which we prove to be the minimal possible number of servers for stabilizing and tolerating f Byzantine servers. That is, each read operation returns the value written by the most recent write and write operations are totally ordered with respect to the happened before relation. Our algorithm is particularly appealing for cloud computing architectures where both processors and memory contents (including stale messages in transit) are prone to errors, faults and malicious behaviors. The proposed implementation extends previous BFT implementations in two ways. First, the algorithm works even when the local memory of processors and the content of the communication channels are initially corrupted in an arbitrary manner. Second, unlike previous solutions, our algorithm uses bounded logical timestamps, a feature difficult to achieve in the presence of transient errors
Improved Distributed Algorithms for Coloring Interval Graphs with Application to Multicoloring Trees
No full textWe give a distributed (1+)-approximation algorithm for the minimum vertex coloring problem on interval graphs, which runs in the LOCAL model and operates in O(1 log∗ n) rounds. If nodes are aware of their interval representations, then the algorithm can be adapted to the CONGEST model using the same number of rounds. Prior to this work, only constant factor approximations using O(log∗ n) rounds were known [12]. Linial’s ring coloring lower bound implies that the dependency on log∗ n cannot be improved. We further prove that the dependency on 1 is also optimal. To obtain our CONGEST model algorithm, we develop a color rotation technique that may be of independent interest. We demonstrate that color rotations can also be applied to obtain a (1 + )-approximate multicoloring of directed trees in O(1 log∗ n) rounds.<br/
Practical Byzantine Reliable Broadcast on Partially Connected Networks (Extended version)
No full textIn this paper, we consider the Byzantine reliable broadcast problem on
authenticated and partially connected networks. The state-of-the-art method to
solve this problem consists in combining two algorithms from the literature.
Handling asynchrony and faulty senders is typically done thanks to Gabriel
Bracha's authenticated double-echo broadcast protocol, which assumes an
asynchronous fully connected network. Danny Dolev's algorithm can then be used
to provide reliable communications between processes in the global fault model,
where up to f processes among N can be faulty in a communication network that
is at least 2f+1-connected. Following recent works that showed that Dolev's
protocol can be made more practical thanks to several optimizations, we show
that the state-of-the-art methods to solve our problem can be optimized thanks
to layer-specific and cross-layer optimizations. Our simulations with the
Omnet++ network simulator show that these optimizations can be efficiently
combined to decrease the total amount of information transmitted or the
protocol's latency (e.g., respectively, -25% and -50% with a 16B payload, N=31
and f=4) compared to the state-of-the-art combination of Bracha's and Dolev's
protocols.Comment: This is an extended version of a paper that appeared at the IEEE
ICDCS 2021 conferenc
Connaissance vs. Synchronie pour l'Accord Tolérant aux Pannes dans les Réseaux Inconnus
No full textNational audienceDans les réseaux auto-organisés, tels que les réseaux mobiles ad hoc et les réseaux pair-à-pair, le consensus est une brique fondamentale pour résoudre les problèmes d'accord. Il permet de coordoner les actions de noeuds répartis de manière ad hoc de telle sorte que des décisions cohérentes peuvent être prises. Il est notoire que dans les environnements classiques, où les entités se comportent de manière asynchrone et où les identités de chacun sont connues, le consensus ne peut être résolu dès qu'une panne crash est susceptible de se produire. Les systèmes auto-organisés renforcent ce résultat d'impossibilité car les identifiants des participants ne sont pas connus. Nous définissons des conditions nécessaires et suffisantes pour que le consensus puisse être résolu dans de tels environnements. Ces conditions sont liées aux hypothèses de synchronie sur l'environnement, ainsi qu'à la connectivité du graphe des connaissances induit par les noeuds qui souhaitent communiquer avec leurs pairs
Connaissance vs. Synchronie pour l'Accord Tolérant aux Pannes dans les Réseaux Inconnus
No full textNational audienceDans les réseaux auto-organisés, tels que les réseaux mobiles ad hoc et les réseaux pair-à-pair, le consensus est une brique fondamentale pour résoudre les problèmes d'accord. Il permet de coordoner les actions de noeuds répartis de manière ad hoc de telle sorte que des décisions cohérentes peuvent être prises. Il est notoire que dans les environnements classiques, où les entités se comportent de manière asynchrone et où les identités de chacun sont connues, le consensus ne peut être résolu dès qu'une panne crash est susceptible de se produire. Les systèmes auto-organisés renforcent ce résultat d'impossibilité car les identifiants des participants ne sont pas connus. Nous définissons des conditions nécessaires et suffisantes pour que le consensus puisse être résolu dans de tels environnements. Ces conditions sont liées aux hypothèses de synchronie sur l'environnement, ainsi qu'à la connectivité du graphe des connaissances induit par les noeuds qui souhaitent communiquer avec leurs pairs
On the self-stabilization of mobile oblivious robots in uniform rings
No full textWe investigate self-stabilizing algorithms for anonymous and oblivious robots in uniform ring networks, that is, we focus on algorithms that can start from any initial configuration (including those with multiplicity points). First, we show that no probabilistic self-stabilizing gathering algorithm exists in the asynchronous (ASYNC) model or if only global-weak and local-strong multiplicity detection is available. This impossibility result implies that a common assumption about initial configurations (no two robots share a node initially) is a very strong one.On the positive side, we give a probabilistic self-stabilizing algorithm for the gathering and orientation problems in the semi-synchronous (SSYNC) model with global-strong multiplicity detection. With respect to impossibility results, those are the weakest system hypotheses. In addition, as an application of the previous algorithm, we provide a self-stabilizing algorithm for the set formation problem. Our results imply that any static set formation can be realized in a self-stabilizing manner in this model
Impact of Information on the Complexity of Asynchronous Radio Broadcasting
No full textLecture Notes in Computer Scienc
Conflict Managers for Self-stabilization without Fairness Assumption
No full textInternational audienceIn this paper, we specify the conflict manager abstraction. Informally, a conflict manager guarantees that any two nodes that are in conflict cannot enter their critical section simultaneously (safety), and that at least one node is able to execute its critical section (progress). The conflict manager problem is strictly weaker than the classical local mutual exclusion problem, where any node that requests to enter its critical section eventually does so (fairness). We argue that conflict managers are a useful mechanism to transform a large class of self-stabilizing algorithms that operate in an essentially sequential model, into self-stabilizing algorithm that operate in a completely asynchronous distributed model. We provide two implementations (one deterministic and one probabilistic) of our abstraction, and provide a composition mechanism to obtain a generic transformer. Our transformers have low overhead: the deterministic transformer requires one memory bit, and guarantees time overhead in order of the network degree, the probabilistic transformer does not require extra memory. While the probabilistic algorithm performs in anonymous networks, it only provides probabilistic stabilization guarantees. In contrast, the deterministic transformer requires initial symmetry breaking but preserves the original algorithm guarantees
Knowledge Connectivity vs. Synchrony Requirements for Fault-Tolerant Agreement in Unknown Networks
No full textIn self-organizing systems, such as mobile ad-hoc and peer-to-peer networks, consensus is a fundamental building block to solve agreement problems. It contributes to coordinate actions of nodes distributed in an ad-hoc manner in order to take consistent decisions. It is well known that in classical environments, in which entities behave asynchronously and where identities are known, consensus cannot be solved in the presence of even one process crash. It appears that self-organizing systems are even less favorable because the set and identity of participants are not known. We define necessary and sufficient conditions under which fault-tolerant consensus become solvable in these environments. Those conditions are related to the synchrony requirements of the environment, as well as the connectivity of the knowledge graph constructed by the nodes in order to communicate with their peers
- …
