In this paper, we propose a methodology to design and analyze the correctness and fairness of committee-based blockchains. We specify the problem that these blockchains implement, specifically, the Byzantine repeated consensus problem. Moreover, we define the problem of fair reward distribution among committee members and study the impact of synchronous assumptions on fairness . It is common knowledge that in permisionless blockchain systems, the main threat is the tragedy of commons that may yield the system to collapse if the rewarding mechanism is not adequate. At minimum, the reward mechanism must be fair , i.e., distribute the rewards in proportion to the merit of the participants. We prove, for the first time in blockchain systems, that in repeated-consensus based blockchains there exists an (eventual) fair rewarding mechanism if and only if the system is (eventual) synchronous. As a case study, we study Tendermint both from Byzantine Repeated Consensus perspective and its fairness with respect to the rewarding of committee members. We prove that in eventual synchronous systems, a modified version of Tendermint solves: (i) one-shot consensus for the validation of one single block with message complexity O ( n 3 ) where is the size of the validators set and (ii) a variant of the repeated consensus problem for multiple blocks. Our second contribution is related to the fairness of the Tendermint rewarding mechanism. We show that the rewarding in Tendermint is not fair, but a small modification of Tendermint is eventually fair.

Hierarchical federated learning (HFL) has attracted academic attention to improve the efficiency of federated learning (FL) in real-world applications, however, little research has been done to explore the structural advantages of HFL against Byzantine attacks and to investigate how to make HFL immune to top-level server Single Point of Failure (SPOF). To explore this field and improve the robustness of HFL, we propose a novel generalized paradigm ABD-HFL for asynchronous Byzantine-resistant decentralized hierarchical federated learning, a multi-tier structure without a central server for FL tasks with a large number of devices. Based on the layered structure, an innovative universal Byzantine resistance mechanism is designed in ABD-HFL, which enables it to apply a combination of multiple Byzantine robust techniques, making ABD-HFL more powerful than any single application of such techniques. Besides, ABD-HFL is a fully decentralized HFL, there is no central server, but rather multiple nodes at the top level agree on the global model where malicious model updates are excluded. A new concept of pipeline learning workflow is also introduced to study communication efficiency in ABD-HFL, which is based on asynchronous communication between various levels to train and propagate the global model. Our numerical evaluation validates the advantage of ABD-HFL in terms of robustness and communication efficiency.

In this paper we propose and evaluate an innovative algorithm that enables the creation of Peer-to-Peer network overlays characterized by emergent multi-hubs. This approach generates overlays that balance between the randomness of a graph and the structure of a star network, resulting in networks that not only feature prominent hubs but also exhibit strong resilience to failures. By leveraging principles of preferential attachment and random attachment, our method allows hubs to form spontaneously, offering a decentralized and fault-tolerant solution ideal for applications requiring both low network diameter and high robustness. The protocol is entirely decentralized, operates asynchronously, and depends exclusively on local information. Nodes organically evolve into hubs and remain indistinguishable from other nodes (except in terms of the number of incoming links). The quantity of hubs that emerge can be predetermined by the application as a network parameter.

Blockchains are appealing technologies with various applications ranging from banking to networking. IOTA blockchain is one of the most prominent blockchain specifically designed for IoT environments. In this paper we investigate the convergence of two Consensus proposed by IOTA: Fast Probabilistic Consensus and Cellular Consensus, when run on top of various topologies. Furthermore, we investigate their resilience to various types of adversaries. Our extensive simulations show that both Cellular Consensus and Fast Probabilistic Consensus have poor convergence rates even under low power adversaries and have poor scaling performances except for the case of Watts Strogatz topologies. Our study points out that the design of IOTs dedicated blockchains is still an open research problem and gives hints design. Our results confirmed the motivation of the foundation IOTA who is working on a complete version of consensus, Coordicide, for the new IOTA, while regarding these two as components of.

Payment-channel networks (PCN) enhance the impact of cryptocurrencies by providing a fast and consensus-free solution to the scalability problems of traditional blockchain protocols. However, PCNs often rely on powerful nodes with high availability, large storage capacity, and strong computational power, which hinders their adoption in mobile environments. In this paper, we consider a PCN architecture that extends the functionalities of traditional PCNs to wireless resource-constrained devices. We address the token theft problem, a vulnerability that is critical on wireless PCNs, and propose a countermeasure based on minimum time windows that lock tokens whenever a user disconnects. We evaluate our proposal with real data from Bitcoin’s Lightning Network and 3G/4G mobile broadband networks. The results show that the countermeasure is most effective when devices present high availability and that there is a security-efficiency trade-off when connectivity is low.

We present probabilistic dynamic I/O automata, a framework to model dynamic probabilistic systems. Our work extends dynamic I/O Automata formalism of Attie & Lynch to probabilistic setting. The original dynamic I/O Automata formalism included operators for parallel composition, action hiding, action renaming, automaton creation, and behavioural sub-typing by means of trace inclusion. They can model mobility by using signature modification. They are also hierarchical: a dynamically changing system of interacting automata is itself modeled as a single automaton. Our work extends to probabilistic settings all these features. Furthermore, we prove necessary and sufficient conditions to obtain the implementation monotonicity with respect to automata creation and destruction. Our construction uses a novel proof technique based on homomorphism that can be of independent interest. Our work lays down the foundations for extending composable secure-emulation of Canetti et al. to dynamic settings, an important tool towards the formal verification of protocols combining probabilistic distributed systems and cryptography in dynamic settings (e.g. blockchains, secure distributed computation, cybersecure distributed protocols etc).

This work extends the composable secure-emulation of Canetti et al. to dynamic settings. Our work builds on top of dynamic probabilistic I/O automata, a recent framework introduced to model dynamic probabilistic systems. Our extension is an important tool towards the formal verification of protocols combining probabilistic distributed systems and cryptography in dynamic settings (e.g. blockchains, cybersecure distributed protocols etc).

We present probabilistic dynamic I/O automata, a framework to model dynamic probabilistic systems. Our work extends dynamic I/O Automata formalism of Attie & Lynch [Paul C. Attie and Nancy A. Lynch, 2016] to the probabilistic setting. The original dynamic I/O Automata formalism included operators for parallel composition, action hiding, action renaming, automaton creation, and behavioral sub-typing by means of trace inclusion. They can model mobility by using signature modification. They are also hierarchical: a dynamically changing system of interacting automata is itself modeled as a single automaton. Our work extends all these features to the probabilistic setting. Furthermore, we prove necessary and sufficient conditions to obtain the monotonicity of automata creation/destruction with implementation preorder. Our construction uses a novel proof technique based on homomorphism that can be of independent interest. Our work lays down the foundations for extending composable secure-emulation of Canetti et al. [Ran Canetti et al., 2007] to dynamic settings, an important tool towards the formal verification of protocols combining probabilistic distributed systems and cryptography in dynamic settings (e.g. blockchains, secure distributed computation, cybersecure distributed protocols, etc).

In this paper we propose a game theoretical framework in order to formally characterize the robustness of blockchains systems in terms of resilience to rational deviations and immunity to Byzantine behaviors. Our framework includes necessary and sufficient conditions for checking the immunity and resilience of games and an original technique for composing games that preserves the robustness of individual games. We prove the practical interest of our formal framework by characterizing the robustness of various blockchain protocols: Bitcoin (the most popular permissionless blockchain), Tendermint (the first permissioned blockchain used by the practitioners), Lightning Network, a side-chain protocol and a cross-chain swap protocol. For each one of the studied protocols we identify upper and lower bounds with respect to their resilience and immunity (expressed as no worse payoff than the initial state) face to rational and Byzantine behaviors.

In this paper we address the distributed cross-chain swap problem in the blockchain context where multiple agents exchange assets across multiple blockchain systems (e.g. trading Bitcoins for Litecoins or Ethers). We present a mathematical framework allowing to characterize blockchain swap protocols as the combination of a publishing and a commitment phase, where contracts are respectively published and then committed. We characterize the equilibria of existing cross-chain swap protocols (i.e., blockchain swap protocols exchanging assets among different blockchains). More precisely, we prove that following a swap protocol characterized by concurrent publishing of exchange contracts and snap (immediate) assets transfers is a Nash equilibrium. Furthermore, we prove that for protocols with a sequential publishing and commitment of the assets transfers, following the prescribed protocol is a sub-game perfect equilibrium.

International audience

This paper is the first to specify blockchains as a composition of abstract data types all together with a hierarchy of consistency criteria that formally characterizes the histories admissible for distributed programs that use them. The paper presents as well some results on implementability of the presented abstractions and a mapping of representative existing blockchains from both academia and industry in our framework.

The presented work continues the line of recent distributed computing community efforts dedicated to the theoretical aspects of blockchains. This paper is the first to specify blockchains as a composition of abstract data types all together with a hierarchy of consistency criteria that formally characterizes the histories admissible for distributed programs that use them. Our work is based on an original oracle-based construction that, along with new consistency definitions, captures the eventual convergence process in blockchain systems. The paper presents as well some results on implementability of the presented abstractions and a mapping of representative existing blockchains from both academia and industry in our framework.

In this paper we describe the architecture and the implementation of a broker based publish/subscribe system where the broker role is played by a private blockchain, Hyperledger Fabric. We show the effectiveness of our architecture by implementing and deploying a photo trading platform. Interestingly, our architecture is generic enough to be adapted to any digital asset trading.

Blockchains interoperability is one of the hardest problems to be solved in the nowadays blockchain ecosystem that contains thousands of different blockchains. This paper focuses on swapping assets from a blockchain to another without a trusted third party. One recent scheme for atomically swapping assets, Atomic Cross Chain Swap (ACCS), has been formally analyzed in [2]. This paper proposes an implementation of an ACCS between the two most valued crypto-currencies today: Bitcoin and Ether.

Committee-based blockchains are among the most popular alternatives of proof-of-work based blockchains, such as Bitcoin. They provide strong consistency (no fork) under classical assumptions, and avoid using energy-consuming mechanisms to add new blocks in the blockchain. For each block, these blockchains use a committee that executes Byzantine-fault tolerant distributed consensus to decide the next block they will add in the blockchain. Unlike Bitcoin, where there is only one creator per block, in committee-based blockchain any block is cooperatively created. In order to incentivize committee members to participate in the creation of new blocks, rewarding schemes have to be designed. In this paper, we study the fairness of rewarding in committee-based blockchains and we provide necessary and sufficient conditions on the system communication under which it is possible to have a fair reward mechanism.

We study verification problems for autonomous swarms of mobile robots that self-organize and cooperate to solve global objectives. In particular, we focus in this paper on the model proposed by Suzuki and Yamashita of anonymous robots evolving in a discrete space with a finite number of locations (here, a ring). A large number of algorithms have been proposed working for rings whose size is not a priori fixed and can be hence considered as a parameter. Handmade correctness proofs of these algorithms have been shown to be error-prone, and recent attention had been given to the application of formal methods to automatically prove those. Our work is the first to study the verification problem of such algorithms in the parameterized case. We show that safety and reachability problems are undecidable for robots evolving asynchronously. On the positive side, we show that safety properties are decidable in the synchronous case, as well as in the asynchronous case for a particular class of algorithms. Several properties on the protocol can be decided as well. Decision procedures rely on an encoding in Presburger arithmetics formulae that can be verified by an SMT-solver. Feasibility of our approach is demonstrated by the encoding of several case studies.

In this paper, we propose BAN-GZKP that optimizes the best to date secure lightweight and energy efficient authentication scheme, BANZKP, designed for WBAN networks. BANZKP is vulnerable to several security attacks such as the replay attack, DDoS attacks at sink and redundancy information crack. Also BANZKP needs an end-to-end authentication which is not compliant with the human body postural mobility. Our scheme, BAN-GZKP, improves both the security and postural mobility resilience of BANZKP. In order to fix the security vulnerabilities of BANZKP, BAN-GZKP uses a novel random key allocation. Moreover, BAN-GZKP uses a hop-by-hop authentication scheme which makes it tolerant to postural mobility. We further prove the reliability of our scheme to various attacks including those to which BANZKP is vulnerable. Furthermore, via extensive simulations we prove that our scheme, BAN-GZKP, outperforms BANZKP in terms of reliability to human body postural mobility for various network parameters (end-to-end delay, number of packets exchanged in the network, number of transmissions). We compared both schemes using representative convergecast strategies with various transmission rates and human postural mobility. When our BAN-GZKP scheme is used the percentage of packets received increases by 34.06%, the end-to-end-delay reduces by 36.02% and the number of transmissions reduces by 8.75% with respect to the case when BANZKP is used. Moreover, BAN-GZKP uses only a three-phase authentication which is optimal in the class of ZKP protocols. Finally, it is important to mention that BAN-GZKP has no additional cost in terms memory, computational complexity or energy consumption compared to BANZKP.

In this paper we prove lower and matching upper bounds for the number of servers required to implement a regular shared register that tolerates unsynchronized Mobile Byzantine failures. We consider the strongest model of Mobile Byzantine failures to date: agents are moved arbitrarily by an omniscient adversary from a server to another in order to deviate their computation in an unforeseen manner. When a server is infected by an Byzantine agent, it behaves arbitrarily until the adversary decides to move the agent to another server. Previous approaches considered asynchronous servers with synchronous mobile Byzantine agents (yielding impossibility results), and synchronous servers with synchronous mobile Byzantine agents (yielding optimal solutions for regular register implementation, even in the case where servers and agents periods are decoupled). We consider the remaining open case of synchronous servers with unsynchronized agents, that can move at their own pace, and change their pace during the execution of the protocol. Most of our findings relate to lower bounds, and characterizing the model parameters that make the problem solvable. It turns out that unsynchronized mobile Byzantine agent movements requires completely new proof arguments, that can be of independent interest when studying other problems in this model. Additionally, we propose a generic server-based algorithm that emulates a regular register in this model, that is tight with respect to the number of mobile Byzantine agents that can be tolerated. Our emulation spans two awareness models: servers with and without self-diagnose mechanisms. In the first case servers are aware that the mobile Byzantine agent has left and hence they can stop running the protocol until they recover a correct state while in the second case, servers are not aware of their faulty state and continue to run the protocol using an incorrect local state.

This paper considers the Approximate Agreement problem in presence of mobile Byzantine agents. We prove lower bounds on the number of correct processes to solve such problem. To do that we prove that the existing solutions tolerant to Byzantine agents still holds in such case and under which conditions.

Advances in wearable and implementable of wireless sensors have enable the development of tiny and intelligent sensors called body sensors. Monitoring the vital body parameters in real-time using wireless body area network (WBAN) has shown great potential in improving healthcare quality not only for patients but also for medical staff. However, security and privacy are still an important issue in WBANs especially in multi-hop architectures. Considering the constraints of the body sensors (namely energy, memory, computational power, etc.). In this paper, we propose and present the design and the evaluation of a secure lightweight and energy efficient authentication scheme BANZKP based on an efficient cryptographic protocol, Zero Knowledge Proof (ZKP) and a commitment scheme. ZKP is used to confirm the identify of the sensor nodes, with small computational requirement, which is favorable for body sensors given their limited resources, while the commitment scheme is used to deal with replay attacks and hence the injection attacks by committing a message and revealing the key later. BANZKP reduces the memory requirement by 56,13% compared to TinyZKP [10], the comparable alternative so far for Body Area Networks. Also, the simulation results demonstrate that our proposed scheme is 17 and 5 times more efficient in term of execution time, and uses 94.11% and 80% less energy compared to TinyZKP and W-ECDSA [16], respectively.

We present an optimal emulation of a server based regular read/write storage in a synchronous round-free message-passing system that is subject to mobile Byzantine failures and prove that the problem is impossible to solve in asynchronous settings. In a system with n servers implementing a regular register, our construction tolerates faults (or attacks) that can be abstracted by agents that are moved (in an arbitrary and unforeseen manner) by a computationally unbounded adversary from a server to another in order to deviate the server's computation. When a server is infected by an adversarial agent, it behaves arbitrarily until the adversary decides to "move" the agent to another server. We investigate the case where the movements of the mobile Byzantine agents are decided by the adversary and are completely decoupled from the message communication delay. Our emulation spans two awareness models: servers with and without self-diagnosis mechanism. In the first case servers are aware that the mobile Byzantine agent has left and hence they can stop running the protocol until they recover a correct state while in the second case, servers are not aware of their faulty state and continue to run the protocol using an incorrect local state. Our results, proven optimal with respect to the threshold of the tolerated mobile Byzantine faults in the first model, are significantly different from the round-based synchronous models. Another interesting side result of our study is that, contrary to the round-based synchronous consensus implementation for systems prone to mobile Byzantine faults, our storage emulation does not rely on the necessity of a core of correct processes all along the computation. That is, every server in the system can be compromised by the mobile Byzantine agents at some point in the computation. This leads to another interesting conclusion: storage is easier than consensus in synchronous settings, when the system is hit by mobile Byzantine failures.

The minimum spanning tree (MST) construction is a classical problem in Distributed Computing for creating a globally minimized structure distributedly. Self-stabilization is versatile technique for forward recovery that permits to handle any kind of transient faults in a unified manner. The loop-free property provides interesting safety assurance in dynamic networks where edge-cost changes during operation of the protocol. We present a new self-stabilizing MST protocol that improves on previous known approaches in several ways. First, it makes fewer system hypotheses as the size of the network (or an upper bound on the size) need not be known to the participants. Secondly, it is loop-free in the sense that it guarantees that a spanning tree structure is always preserved while edge costs change dynamically and the protocol adjusts to a new MST. Finally, time complexity matches the best known results, while space complexity results show that this protocol is the most efficient to date.

Distributed 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.

The rapid advances in sensors and ultra-low power wireless communication has enabled a new generation of wireless sensor networks: Wireless Body Area Networks (WBAN). To the best of our knowledge the current paper is the first to address broadcast in WBAN. We first analyze several broadcast strategies inspired from the area of Delay Tolerant Networks (DTN). The proposed strategies are evaluated via the OMNET++ simulator that we enriched with realistic human body mobility models and channel models issued from the recent research on biomedical and health informatics. Contrary to the common expectation, our results show that existing research in DTN cannot be transposed without significant modifications in WBANs area. That is, existing broadcast strategies for DTNs do not perform well with human body mobility. However, our extensive simulations give valuable insights and directions for designing efficient broadcast in WBAN. Furthermore, we propose a novel broadcast strategy that outperforms the existing ones in terms of end-to-end delay, network coverage and energy consumption.

A stabilizing Byzantine single-writer single-reader (SWSR) regular register, which stabilizes after the first invoked write operation, is first presented. Then, new/old ordering inversions are eliminated by the use of a (bounded) sequence number for writes, obtaining a practically stabilizing SWSR atomic register. A practically stabilizing Byzantine single-writer multi-reader (SWMR) atomic register is then obtained by using several copies of SWSR atomic registers. Finally, bounded time-stamps, with a time-stamp per writer, together with SWMR atomic registers, are used to construct a practically stabilizing Byzantine multi-writer multi-reader (MWMR) atomic register. In a system of n servers implementing an atomic register, and in addition to transient failures, the constructions tolerate t<n/8 Byzantine servers if communication is asynchronous, and t

We present the first self-healing architecture for recovering semantic DR-tree overlays in response to physical nodes failures (crash). Our work builds on two of our recent results: the overlay virtualization and churn tolerant design of constant expanders for distributed R-trees. That is, the proposed self-healing strategy, in order to recover the searchability and the semantic organization of the original overlay, exploits both the randomly uniform distribution of the logical nodes on top of the physical network and the additional virtual links of the expander. The convergence time of our scheme is O(log(n)) and the height of the recovered tree is increased only by Ω(log f) with respect to the original overlay (n is the size of the network and f are the number of crashed nodes). We validate our scheme via simulations including measures of the recovery time, the recovery extra cost and finally the impact of the recovery scheme on the distributed R-tree connectivity and semantics.

Abstract Sensor networks are mainly used to gather strategic information in various monitored areas. Sensors may be deployed in zones where their internal memory, or the sensors themselves, can be corrupted. Since deployed sensors cannot be easily replaced, network persistence and robustness are the two main issues that have to be addressed while efficiently deploying large scale sensor networks. The sensing radius of a sensor is the distance within which a sensor can monitor certain events. The communication radius of a sensor is the distance within which a sensor can transmit and receive data. A sensor is said to cover a particular monitored area if a circular area, with radius equal to that sensor's sensing radius, covers that area. A set of sensors is said to be strongly connected if any two sensors in the set can communicate with each other, either directly or indirectly. The goal of forming a minimum connected cover of a query region in sensor networks is to select a subset of nodes that entirely covers a particular monitored area, which is strongly connected, and which does not contain a subset with the same properties. Selecting a minimal number of connected sensors is an NP hard problem. In our work, we address minimality in terms of inclusion. In this paper, we consider the most general case, wherein every sensor has a different sensing and communication radius. We propose two novel and robust solutions to the minimum connected cover problem that can cope with both transient faults (corruptions of the internal memory of sensors) and sensor crash/join. Also, our proposal includes extended versions which use multi‐hop information. We also prove the self‐stabilization property of our solutions, both analytically and through extended simulations. A self‐stabilizing system is a system that, when started from an arbitrary state, is always guaranteed to recover following the occurrence of (transient) faults and converge to a desired behavior (legitimate state) in a finite number of steps.Viasimulations, we also conclude that our solutions provide better performance, in terms of coverage, than preexisting self‐stabilizing solutions. Moreover, we observe that multi‐hop solutions produce a better approximation to an optimal cover set. Copyright © 2009 John Wiley & Sons, Ltd.

Distributed R-tree overlays emerged as an alternative for efficiently implementing DHT-free publish/subscribe communication primitives. Overlays using R-tree index structures offer logarithmic delivery garantis, guarantee zero false negatives and considerably reduce the number of false positives. In this paper we extend the distributed R-trees (DR-trees) in order to reduce event delivery latency. Our optimizations target both the structural organization of the DR-Trees and the publication policies. The contribution of the current work steams in an extensive evaluation of the novel structure along four parameters: latency, load, scalability and the rate of false positives. The enhanced structure performs better than the traditional distributed R-tree in terms of delivery latency. Additionally, it does not alter the performances related to the scalability, nor the load balancing of the tree, and neither the rate of false positives and negatives filtered by a node.

Publish/subscribe systems provide useful platforms for delivering data (events) from publishers to subscribers in a decoupled fashion. Developing efficient publish/subscribe schemes in dynamic distributed systems is still an open problem for complex subscriptions (spanning multidimensional intervals). We propose a distributed R-tree (DR-tree) structure that uses R-tree-based spatial filters to construct a peer-to-peer overlay optimized for scalable and efficient selective dissemination of information. We adapt well-known variants of R-trees to organize publishers and subscribers in balanced peer-to-peer networks that support content-based filtering in publish/subscribe systems. DR-tree overlays guarantee subscription and publication times logarithmic in the size of the network while keeping space requirements low (comparable to distributed hash tables). The maintenance of the overlay is local and the structure is balanced with height logarithmic in the number of nodes. DR-tree overlays disseminate messages with no false negatives and very few false positives in the embedded publish/subscribe system. In addition, we propose self-stabilizing algorithms that guarantee consistency despite failures and changes in the peer population.

A distributed algorithm is self-stabilizing if after faults and attacks hit the system and place it in some arbitrary global state, the systems recovers from this catastrophic situation without external intervention in finite time. Uni-directional networks preclude many common techniques in self-stabilization from being used, such as preserving local predicates. In this paper, we investigate the intrinsic complexity of achieving self-stabilization in unidirectional anonymous general networks, and focus on the classical vertex coloring problem. Specifically, we prove a lower bound of n states per process (where n is the network size) and a recovery time of at least n(n-1)/2 actions in total. We also provide a deterministic algorithm with matching upper bounds that performs in arbitrary unidirectional anonymous graphs.

We propose a self-stabilizing algorithm for constructing a Minimum-Degree Spanning Tree (MDST) in undirected networks. Starting from an arbitrary state, our algorithm is guaranteed to converge to a legitimate state describing a spanning tree whose maximum node degree is at most Delta*+ 1, where Delta* is the minimum possible maximum degree of a spanning tree of the network. To the best of our knowledge our algorithm is the first self-stabilizing solution for the construction of a minimum-degree spanning tree in undirected graphs. The algorithm uses only local communications (nodes interact only with the neighbors at one hop distance). Moreover, the algorithm is designed to work in any asynchronous message passing network with reliable FIFO channels. Additionally, we use a fine grained atomicity model (i.e. the send/receive atomicity). The time complexity of our solution is O(mn2log n) where m is the number of edges and n is the number of nodes. The memory complexity is O(delta log n) in the send-receive atomicity model (delta is the maximal degree of the network).

In this paper, we propose and prove correct a distributed stabilizing implementation of an overlay, called DR-tree, optimized for efficient selective dissemination of information. DR-tree copes with nodes dynamicity (frequent joins and leaves) and memory and counter program corruptions, that is, the processes can connect/disconnect at any time, and their memories and programs can be corrupted. The maintenance of the structure is local and requires no additional memory to guarantee its stabilization. The structure is balanced and is of height 0(logm(N)), which makes it suitable for performing efficient data storage or search. We extend our overlay in order to support complex content-based filtering in publish/subscribe systems. Publish/subscribe systems provide useful platforms for delivering data (events) from publishers to subscribers in a decoupled fashion in distributed networks. Developing efficient publish/subscribe schemes in dynamic distributed systems is still an open problem for complex subscriptions (spanning multi-dimensional intervals). Embedding a publish/subscribe system in a DR-trees is a new and viable solution. The DR-tree overlay also guarantees subscription and publication times logarithmic in the size of the network while keeping its space requirement low (comparable to its DHT-based counterparts). Nonetheless, the DR- tree overlay helps in eliminating the false negatives and drastically reduces the false positives in the embedded publish/subscribe system.

In 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.

Publish/Subscribe systems provide a useful platform for delivering data (events) from publishers to subscribers in an anonymous fashion in distributed networks. In this paper, we promote a novel design principle for self-. dynamic and reliable content-based publish/subscribe systems and perform a comparative analysis of its probabilistic and deterministic implementations. More specifically, we present a generic content-based publish/subscribe system, called DPS (Dynamic Publish/Subscribe). DPS combines classical content-based filtering with self-. (self-organizing, selfconfiguring, and self-healing) subscription-driven clustering of subscribers. DPS gracefully adapts to failures and changes in the system while achieving scalable events delivery. DPS includes a variety of fault-tolerant deterministic and probabilistic content-based publication/subscription schemes. These schemes are targeted toward scalability, and aim at reducing and distributing the number of messages exchanged. Reliability and scalability of our system are shown through analytical and experimental evaluation.

The network connectivity is a basic requirement while implementing fundamental communication and storage abstractions in P2P networks, featuring scalability and fault-tolerance. The quality of services of abstractions like for example multicast, publish/subscribe, group membership or persistent storage is strongly related to the connectivity degree of the underlying overlay. Intuitively, a higher overlay connectivity ensures a reinforced reliability and consequently, the deployment of distributed applications with real-time constraints on top of these overlays becomes feasible even in environments characterized by a high dynamicity, i.e., nodes arriving and departing at a high rate. Our paper proposes a novel delta-connected DHT-free P2P overlay. Our overlay offers strong connectivity guarantees despite the system dynamicity. The construction and the maintenance of our overlay is completely decentralized and handled strictly locally, through deterministic algorithms whose correctness is rigorously proved

This paper addresses the problem of trajectory tracking that deals with gathering coherent information on the past behavior of a mobile target. When a target enters and moves within a region covered by a sensor network, information about this target is generated by any active sensor that detects the target in its monitoring area. These gathered data have to be received by some registered nodes that are in charged of identifying the trajectory of the target to perform latter complex computations at the application level (e.g., trajectory forecasting, pursuer/evader, optimization of the management of natural disasters, etc,), Our first contribution consists informally specifying the problem: the proposed formal specification is the first one to the best of our knowledge. We also propose an original architecture combining three distinct abstractions which allows describing various solutions. Some algorithmic solutions that is necessary far the self-stabilizing-implementation of the trajectory tracking specification is outlined. The overall solution blends together in the context of tracking applications, three research areas: temporal correlated data, causal correlated (content related) data, and self-stabilizing overlays

We consider the problem of fair resource sharing to optimize the performance of resource sharing in peer to peer systems. Resource sharing systems currently face rational peers which may exhibit a variety of strategies including: no participation, also referred as free-riding, and greedy behavior. The first aspect has been extensively studied in the late years, while the second one has not received much attention. The broad class of proposed solutions focuses on designing incentives to reward cooperative peers. The side effect of these incentives is twofold: the system load is not balanced and the resource potential of the system is not fully exploited. The P2P fair resource sharing aims at both balancing the load and maximizing the use of system resources. The contribution of our work is twofold. First, we specify the P2P fair resource sharing problem and propose a mechanism to solve it in large scale dynamic networks with rational users. Our mechanism is composed of a novel incentive (i.e. fair cooperation) and an algorithmic part encapsulated in a middleware layer. Second, we propose an architecture for our mechanism middleware layer including four distributed services that bring together several research area: aggregation, semantic group membership and tracking. Finally, we implement our mechanism using a peer-to-peer unstructured model and evaluate it through simulations

In this paper, we design self-* novel solutions to the minimal connected sensor cover problem. The concept of self-* is used to include fault-tolerant properties like self-configuring, self-reconfiguring/self-healing, etc. We present two self-stabilizing, fully distributed, strictly localized, and scalable solutions, and show that these solutions are both self-configuring and self-healing. The proposed solutions are space optimal in terms of the number of states used per node. Another feature of the proposed algorithms is that the faults are contained only within the neighborhood of the faulty nodes. This paper also includes a comparison of the performance of the two proposed solutions in terms of the stabilization time, cover size metrics, and ability to cope with transient and permanent faults.

Caching Internet based services is a potentially important application for MANETs, as it can improve mobile users' perceived quality of service, reduce their energy consumption, and lower their air-time costs. This paper considers the problem of locating cache proxies in MANETs using several search techniques. The paper first examines several existing and a few novel search techniques including flooding, constrained flooding, a novel dynamic variation of probabilistic flooding, and BFS. These are superimposed on a Maximal Independent Set (MIS), a Connected Dominating Set (DS), and a novel adaptation of BFS-tree based overlays, where each of these overlays is maintained in a self stabilizing manner. The paper also includes a comparison of the performance of these search techniques and overlays by extensive simulations.

A self-stabilizing algorithm, regardless of the initial system state, converges in finite time to a set of states that satisfy a legitimacy predicate. The mutual exclusion problem is fundamental in distributed computing, since it allows processors competing to access a shared resource to be able to synchronize and get exclusive access to the resource (i.e. execute their critical section). It is well known that providing self-stabilization in general uniform networks (e.g. anonymous rings of arbitrary size) can only be probabilistic. However, all existing uniform probabilistic self-stabilizing mutual exclusion algorithms designed to work under an unfair distributed scheduler (that may choose processors to execute their code in an arbitrary manner) suffer from the following common drawback: once stabilized, there exists no upper bound on time between two successive executions of the critical section at a given processor. In this paper, we present the first self-stabilizing algorithm that guarantees such a bound (O(n3), where n is the network size) while working using an unfair distributed scheduler. Our algorithm works in an anonymous unidirectional ring of any size and has a polynomial expected stabilization time.

Wormhole routing is the most common in parallel architecture in which messages are sent in small fragments called flits. It is a lightweight and efficient method of routing messages between parallel processors. Self-stabilization is a technique that guarantees tolerance to transient faults (e.g. memory corruption or communication hazard) for a given protocol. Self-stabilization guarantees that the network recovers to a correct behavior infinite time, without the need for human intervention. Self-stabilization also guarantees the safety property, meaning that once the network is in a legitimate state, it will remain there until another fault occurs. This paper presents the first self-stabilizing network algorithm in the wormhole routing model, using the unidirectional ring topology. Our solution benefits from wormhole routing by providing high throughput and low latency, and front self-stabilization by ensuring automatic resilience to all possible transient failures.

Normality, consistency criteria stronger than sequentiality and equivalent to linearizability for the unary operations case, has the main advantage that it avoids the use of the "global real-time ordering". This work presents the first algorithm that implements normality without using strong communication primitives (i.e. atomic broadcast or global clock synchronization). Moreover, our implementation allows the dynamic changes of the system configuration, handles replication and refers the general case of multi-object operations. Although the use of terms as client or server our algorithm is entirely based on a peer-to-peer approach.

A self-stabilizing algorithm, regardless of the initial system state, converges in finite time to a set of states that satisfy a legitimacy predicate without the need for explicit exception handler of backward recovery. The l-mutual exclusion is a generalization of the fundamental problem of mutual exclusion: the system has to guarantee the fair sharing of a resource that can be used by l processors simultaneously. We present a space efficient solution to the l-mutual exclusion problem that performs on uniform unidirectional ring networks and that is self-stabilizing. Our solution improves the space complexity of previously known approaches by a factor of min(n/sup 2//spl times/log(n), 1/l/spl times/log/sup l-1/ (n)), while retaining none of their drawbacks in terms of system hypothesis (we support unfair scheduler and ensure strong correctness) or specification verification (we guarantee high level 2-mutual exclusion). When l is fixed, the space complexity at each node is constant in average, making our approach suitable for scalable systems.

A self-stabilizing algorithm, regardless of the initial system state, converges infinite time to a set of states that satisfy a legitimacy predicate without the need for explicit exception handler of backward recovery. Mutual exclusion is fundamental in the area of distributed computing, by serializing the accesses to a common shared resource. All existing probabilistic self-stabilizing mutual exclusion algorithms designed to work under an unfair distributed scheduler suffer from the following common drawback: Once stabilized, there exists no upper bound of time between two executions of the critical section at a given node. We present the first probabilistic self-stabilizing algorithm that guarantees such a bound (O(n/sup 3/), where n is the network size) while working using an unfair distributed scheduler. As the scheduling adversary gets weaker the bound gets better. Our algorithm works in an anonymous unidirectional ring of any size and has a O(n/sup 3/) expected stabilization time.

We study the memory requirements of self-stabilizing leader election (SSLE) protocols. We are mainly interested in two types of systems: anonymous systems and id-based systems. We consider two classes of protocols: deterministic ones and randomized ones. We prove that a non-constant lower bound on the memory space is required by a SSLE protocol on unidirectional, anonymous rings (even if the protocol is randomized). We show that, if there is a deterministic protocol solving a problem on id-based systems where the processor memory space is constant and the id-values are not bounded then there is a deterministic protocol on anonymous systems using constant memory space that solves the same problem. Thus impossibility results on anonymous rings (i.e. one may design a deterministic SSLE protocol, only on prime size rings, under a centralized daemon) can be extended to those kinds of id-based rings. Nevertheless, it is possible to design a silent and deterministic SSLE protocol requiring constant memory space on unidirectional, id-based rings where the id-values are bounded. We present such a protocol. We also present a randomized SSLE protocol and a token circulation protocol under an unfair, distributed daemon on anonymous and unidirectional rings of any size. We give a lower bound on memory space requirement proving that these protocols are space optimal. The memory space required is constant on average.