Source author record

Laurence Pilard

Laurence Pilard appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Distributed, Parallel, and Cluster Computing Data Structures and Algorithms

Catalog footprint

What is connected

4works

2topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2016arXiv

Polynomial self-stabilizing algorithm and proof for a 2/3-approximation of a maximum matching

We present the first polynomial self-stabilizing algorithm for finding a $\frac23$-approximation of a maximum matching in a general graph. The previous best known algorithm has been presented by Manne \emph{et al.} \cite{ManneMPT11} and has a sub-exponential time complexity under the distributed adversarial daemon \cite{Coor}. Our new algorithm is an adaptation of the Manne \emph{et al.} algorithm and works under the same daemon, but with a time complexity in $O(n^3)$ moves. Moreover, our algorithm only needs one more boolean variable than the previous one, thus as in the Manne \emph{et al.} algorithm, it only requires a constant amount of memory space (three identifiers and $two$ booleans per node).

preprint2016arXiv

Self-Stabilizing Maximal Matching and Anonymous Networks

We propose a self-stabilizing algorithm for computing a maximal matching in an anonymous network. The complexity is $O(n^3)$ moves with high probability, under the adversarial distributed daemon. In this algorithm, each node can determine whether one of its neighbors points to it or to another node, leading to a contradiction with the anonymous assumption. To solve this problem, we provide under the classical link-register model, a self-stabilizing algorithm that gives a unique name to a link such that this name is shared by both extremities of the link.

preprint2010arXiv

A Distributed Clustering Algorithm for Dynamic Networks

We propose an algorithm that builds and maintains clusters over a network subject to mobility. This algorithm is fully decentralized and makes all the different clusters grow concurrently. The algorithm uses circulating tokens that collect data and move according to a random walk traversal scheme. Their task consists in (i) creating a cluster with the nodes it discovers and (ii) managing the cluster expansion; all decisions affecting the cluster are taken only by a node that owns the token. The size of each cluster is maintained higher than $m$ nodes ($m$ is a parameter of the algorithm). The obtained clustering is locally optimal in the sense that, with only a local view of each clusters, it computes the largest possible number of clusters (\emph{ie} the sizes of the clusters are as close to $m$ as possible). This algorithm is designed as a decentralized control algorithm for large scale networks and is mobility-adaptive: after a series of topological changes, the algorithm converges to a clustering. This recomputation only affects nodes in clusters in which topological changes happened, and in adjacent clusters.

preprint2007arXiv

A New Self-Stabilizing Maximal Matching Algorithm

The maximal matching problem has received considerable attention in the self-stabilizing community. Previous work has given different self-stabilizing algorithms that solves the problem for both the adversarial and fair distributed daemon, the sequential adversarial daemon, as well as the synchronous daemon. In the following we present a single self-stabilizing algorithm for this problem that unites all of these algorithms in that it stabilizes in the same number of moves as the previous best algorithms for the sequential adversarial, the distributed fair, and the synchronous daemon. In addition, the algorithm improves the previous best moves complexities for the distributed adversarial daemon from O(n^2) and O(delta m) to O(m) where n is the number of processes, m is thenumber of edges, and delta is the maximum degree in the graph.