Search

Your search keyword '"Colette Johnen"' showing total 128 results
Start Over Author "Colette Johnen"
128 results on '"Colette Johnen"'

1. Self-Stabilizing Disconnected Components Detection and Rooted Shortest-Path Tree Maintenance in Polynomial Steps

Author

Stéphane Devismes, David Ilcinkas, and Colette Johnen

Subjects
disconnected network, routing algorithm, shortest path, distributed algorithm, self-stabilization, shortest-path tree, [info.info-ni] computer science [cs]/networking and internet architecture [cs.ni], Mathematics, QA1-939
Abstract

We deal with the problem of maintaining a shortest-path tree rooted at some process r in a network that may be disconnected after topological changes. The goal is then to maintain a shortest-path tree rooted at r in its connected component, V_r, and make all processes of other components detecting that r is not part of their connected component. We propose, in the composite atomicity model, a silent self-stabilizing algorithm for this problem working in semi-anonymous networks, where edges have strictly positive weights. This algorithm does not require any a priori knowledge about global parameters of the network. We prove its correctness assuming the distributed unfair daemon, the most general daemon. Its stabilization time in rounds is at most 3nmax+D, where nmax is the maximum number of non-root processes in a connected component and D is the hop-diameter of V_r. Furthermore, if we additionally assume that edge weights are positive integers, then it stabilizes in a polynomial number of steps: namely, we exhibit a bound in O(maxi nmax^3 n), where maxi is the maximum weight of an edge and n is the number of processes.

Published
2017
Full Text
View/download PDF

17. Efficient Wait-Free Queue Algorithms with Multiple Enqueuers and Multiple Dequeuers

Author

Colette Johnen and Adnane Khattabi and Alessia Milani, Johnen, Colette, Khattabi, Adnane, Milani, Alessia, Colette Johnen and Adnane Khattabi and Alessia Milani, Johnen, Colette, Khattabi, Adnane, and Milani, Alessia

Abstract

Despite the widespread usage of FIFO queues in distributed applications, designing efficient wait-free implementations of queues remains a challenge. The majority of wait-free queue implementations restrict either the number of dequeuers or the number of enqueuers that can operate on the queue, even when they use strong synchronization primitives, like the Compare&Swap. If we do not limit the number of processes that can perform enqueue and dequeue operations, the best-known upper bound on the worst case step complexity for a wait-free queue is given by [Khanchandani and Wattenhofer, 2018]. In particular, they present an implementation of a multiple dequeuer multiple enqueuer wait-free queue whose worst case step complexity is in O(√n), where n is the number of processes. In this work, we investigate whether it is possible to improve this bound. In particular, we present a wait-free FIFO queue implementation that supports n enqueuers and k dequeuers where the worst case step complexity of an Enqueue operation is in O(log n) and of a Dequeue operation is in O(k log n). Then, we show that if the semantics of the queue can be relaxed, by allowing concurrent Dequeue operations to retrieve the same element, then we can achieve O(log n) worst-case step complexity for both the Enqueue and Dequeue operations.

Published
2023
Full Text
View/download PDF

22. Optimized Silent Self-Stabilizing Scheme for Tree-Based Constructions

Author

Colette Johnen, Stéphane Devismes, and David Ilcinkas

Subjects
Scheme (programming language), 020301 aerospace & aeronautics, General Computer Science, Computer science, Applied Mathematics, 0102 computer and information sciences, 02 engineering and technology, Topology, 01 natural sciences, Computer Science Applications, 0203 mechanical engineering, 010201 computation theory & mathematics, Tree based, computer, computer.programming_language
Published
2021

48. FIFO and Atomic broadcast algorithms with bounded message size for dynamic systems

Author

Pierre Sens, Colette Johnen, Luciana Arantes, Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), DistributEd aLgorithms and sYStems (DELYS), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), This study was partially supported by ANR project ESTATE : ANR-16 CE25-0009-03., Sens, Pierre, and Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)

Subjects
communication primitive, FIFO (computing and electronics), Computer science, dynamic graphs, bounded message size, Identifier, Atomic broadcast, Distributed algorithm, Bounded function, [INFO.INFO-DC] Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Graph (abstract data type), Distributed algorithms, Communication source, Timestamp, Atomic Broadcast, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], FIFO broadcast, Algorithm, Causal Broadcast, Theory of computation
Abstract

International audience; FIFO broadcast provides application ordering semantics of messages broadcast by the same sender and have been mostly implemented on top of unreliable static networks. In this article, we propose a round-based FIFO broadcast algorithm with both termination detection and bounded message size for dynamic networks with recurrent connectivity (Class TC^R of Time-varying Graph formalism). Initially, processes only know the number of processes N in the system and their identifier. Due to the dynamics of the network links, messages can be lost. Since no unbounded timestamp is used to identify a message, its size is bounded to 2N + O(log(N)) + msgSize bits where msgSize is the bound size in bits of the broadcast data. We also present an FIFO atomic broadcast algorithm in Class TC^R that uses the proposed FIFO broadcast and deliver primitives.

Published
2021

Catalog

Books, media, physical & digital resources
See catalog results