There is a handshake between two nodes in a network, if the two nodes are communicating with one another in an exclusive mode. In this paper, we give a mobile agent algorithm that allows to decide whether two nodes realize a handshake. Our algorithm can be used in order to solve some other classical distributed problems, e.g., local computations, maximal matching and edge coloring. We give a performance analysis of the algorithm and we compute the optimal number of agents maximizing the mean number of simultaneous handshakes. In particular, we obtain $\Omega(m\delta/\Delta^2)$ simultaneous handshakes where $m$ is the number of edges in the network, and $\Delta$ (resp. $\delta$) is the maximum (resp. minimum) degree of the network. For any almost $\Delta$-regular network, our lower bound is optimal up to a constant factor. In addition, we show how to emulate our mobile agent algorithm in the message passing model while maintaining the same performances. Comparing with previous message passing algorithms, we obtain a larger number of handshakes, which shows that using mobile agents can provide novel ideas to efficiently solve some well studied problems in the message passing model.

This paper concerns the efficient construction of sparse and lowstretch spanners for unweighted arbitrary graphs with $n$ nodes. All previous deterministic distributed algorithms, for constant stretch spanner of $o(n^2)$ edges, have a running time $\Omega(n^{\epsilon})$ for some constant $\epsilon > 0$ depending on the stretch. Our deterministic distributed algorithms construct constant stretch spanners of $o(n^2)$ edges in $o(n^{\epsilon})$ time for any constant $\epsilon >0$. More precisely, in the Linial's free model, we construct in $n^{O(1/\sqrt{\log n}\,)}$ time, for every graph, a $5$-spanner of $O(n^{3/2})$ edges. The result is extended to $O(k^{2.322})$-spanners with $O(n^{1+1/k})$ edges for every parameter $k \ge 1$. If the minimum degree of the graph is $\Omega(\sqrt{n}\,)$, then, in the same time complexity, a $9$-spanner with $O(n)$ edges can be constructed.

This paper presents efficient deterministic and randomized distributed algorithms for decomposing a graph with $n$ nodes into a disjoint set of connected clusters with small radius and few intercluster edges. Our algorithms can be easily implemented in the distributed CONGEST model of computation i.e., limited message size, improving the time complexity of previous algorithms from linear to sublinear. One important application of our algorithms is efficient construction of sparse graph spanners. In fact, given a parameter $k$, we show that there exists a sublinear deterministic distributed algorithm that constructs a graph spanner of stretch $2k-1$ with at most $O(n^{1+1/k})$ edges in the CONGEST model.

We present a linear time distributed algorithm for decomposing a graph into a disjoint set of clusters. This algorithm is truly parallel since many clusters can be constructed in parallel, which gives an answer to a question asked by S. Moran and S. Snir in [MS00]. Moreover, no precomputed spanning tree is required for the computation of clusters. We apply the designed algorithm to construct covers for synchronizers $\gamma_1$ and $\gamma_2$.

Visidia is a software platform for the simulation and the visualization of distributed algorithms. The simulation used to be done using only one machine [BMMS,VMT2002]. In this paper, we present a new collaborative approach for runnig the simulation using a network of machines. More preciely, we suppose that several machines connected by a network can take part in the simulation. We give both a specification of our model and a description of the  its implementation.