A topology-aware implementation reduces communication times for parallel programs. MPI supports the distribution of processes on a virtual Cartesian grid via the MPI_Cart_Create function. In such situation, communications between process mostly occur between those in charge of adjacent cells. Thus, placing such processes close one to another reduces the risk of congestion. Using operations research techniques and tools, we compute process placements that realize this objective. We present two solutions: a mathematical modeling of this problem, that we then linearize to compute an optimal solution with a MILP solver; or a heuristic based on a dynamic programming algorithm that provides either an optimal guillotine solution or a good quality solution depending on the networks. This work is based on fat-tree topologies to validate the methods and hypotheses of this work.

Recently, stochastic rounding (SR) has been implemented in specialized hardware but most current computing nodes do not yet support this rounding mode. Several works empirically illustrate the benefit of stochastic rounding in various fields such as neural networks and ordinary differential equations. For some algorithms, such as summation, inner product or matrix-vector multiplication, it has been proved that SR provides probabilistic error bounds better than the traditional deterministic bounds. In this paper, we extend this theoretical ground for a wider adoption of SR in computer architecture. First, we analyze the biases of the two SR modes: SR-nearness and SR-up-or-down. We demonstrate on a case-study of Euler's forward method that IEEE-754 default rounding modes and SR-up-or-down accumulate rounding errors across iterations and that SR-nearness, being unbiased, does not. Second, we prove a $O(\sqrt{n})$ probabilistic bound on the forward error of Horner's polynomial evaluation method with SR, improving on the known deterministic O(n) bound.

Quantifying errors and losses due to the use of Floating-point (FP) calculations in industrial scientific computing codes is an important part of the Verification, Validation, and Uncertainty Quantification process. Stochastic Arithmetic is one way to model and estimate FP losses of accuracy, which scales well to large, industrial codes. It exists in different flavors, such as CESTAC or MCA, implemented in various tools such as CADNA, Verificarlo, or Verrou. These methodologies and tools are based on the idea that FP losses of accuracy can be modeled via randomness. Therefore, they share the same need to perform a statistical analysis of programs results to estimate the significance of the results. In this article, we propose a framework to perform a solid statistical analysis of Stochastic Arithmetic. This framework unifies all existing definitions of the number of significant digits (CESTAC and MCA), and also proposes a new quantity of interest: the number of digits contributing to the accuracy of the results. Sound confidence intervals are provided for all estimators, both in the case of normally distributed results, and in the general case. The use of this framework is demonstrated by two case studies of industrial codes: Europlexus and code_aster.

The distributed naming problem, assigning unique names to the nodes in a distributed system, is a fundamental task. This problem is nontrivial, especially when the amount of memory available for the task is low, and when requirements for fault-tolerance are added. The considered distributed communication model is population protocols. In this model, a priori anonymous and indistinguishable mobile nodes (called agents), communicate in pairs and in an asynchronous manner (according to a fairness condition). Fault-tolerance is addressed through self-stabilization, in terms of arbitrary initialization of agents. This work comprises a comprehensive study of the necessary and sufficient state space conditions for naming. The problem is studied under various combinations of model assumptions: weak or global fairness, arbitrary or uniform initialization of agents, existence or absence of a distinguishable agent (arbitrarily initialized or not), possibility of breaking symmetry in pair-wise interactions (symmetric or asymmetric transitions). For each possible combination of these assumptions, either an impossibility is proven or the necessary exact number of states (per mobile agent) is determined and an appropriate space-optimal naming protocol is presented.

Population protocols are a popular model of distributed computing, in which randomly-interacting agents with little computational power cooperate to jointly perform computational tasks. Inspired by developments in molecular computation, and in particular DNA computing, recent algorithmic work has focused on the complexity of solving simple yet fundamental tasks in the population model, such as leader election (which requires stabilization to a single agent in a special "leader" state), and majority (in which agents must stabilize to a decision as to which of two possible initial states had higher initial count). Known results point towards an inherent trade-off between the time complexity of such algorithms, and the space complexity, i.e. size of the memory available to each agent. In this paper, we explore this trade-off and provide new upper and lower bounds for majority and leader election. First, we prove a unified lower bound, which relates the space available per node with the time complexity achievable by a protocol: for instance, our result implies that any protocol solving either of these tasks for $n$ agents using $O( \log \log n )$ states must take $Ω( n / \rm{polylog} n )$ expected time. This is the first result to characterize time complexity for protocols which employ super-constant number of states per node, and proves that fast, poly-logarithmic running times require protocols to have relatively large space costs. On the positive side, we give algorithms showing that fast, poly-logarithmic stabilization time can be achieved using $O( \log^2 n )$ space per node, in the case of both tasks. Overall, our results highlight a time complexity separation between $O(\log \log n)$ and $Θ( \log^2 n )$ state space size for both majority and leader election in population protocols, and introduce new techniques, which should be applicable more broadly.

The mobility of ad hoc networks requires solutions that are adaptive to topological changes. Random walks offer a topology-adaptive traversal scheme that can be used in such a context. In random walk based distributed algorithms, topology changes are no fault, which leaves two major fault types (i) the absence of token in the system, (ii) the presence of more than one token in the system. In this paper, we focus on the presence of several token. When a node owns two tokens at a time, it deletes one of them and sends only one token. The purpose of this paper is to give an algorithm to compute the average time for several tokens to meet and be merged, hence the stabilization time of a random walk circulation when several tokens are present.

In this paper, we present a fully distributed clustering algorithm based on random walks that works on arbitrary topologies. A cluster is composed of a set of nodes called the core that coordinates the clustering process, and of non-core nodes called ordinary nodes. A core is built through a random walk based procedure. Its neighboring nodes that do not belong to any cluster are recruited by the core as ordinary nodes into its cluster. The correctness and termination of our algorithm are proven. We also prove that when two clusters are adjacent, at least one of them has a complete core (i.e. a core with the maximum size allowed by the user). Our algorithm is not deterministic, which allows a better load balancing, since the core nodes are not determined by their ids and/or location.

Self-stabilizing token circulation algorithms are not always adapted for dynamic networks. Random walks are well known to play a crucial role in the design of randomized algorithms. The combination of these two concepts makes it possible to design a solution that is adaptive to topology changes and is tolerant to transient faults. Our purpose in this paper is to study the behavior of such algorithms with possible transient failures. We provide a probabilistic analysis of the waiting time. More precisely, we give two bounds on the probability for a processor to wait for the token more than a certain amount of time. The first bound is based on the token return time (the expected time for the token to visit again a processor) and the second one, a tighter upper bound, is based on its variance. Next, we characterize a local ¿criterion of suspicion¿ for each processor to be in a faulty global configuration; in fact a token loss detection. Thanks to this criterion, we propose to refine the timeout procedure used in [6, 1]. Thus, an improved version of an adaptive and self-stabilizing random walk token circulation algorithm can be designed.

Summary form only given. Random walks based algorithms give efficient solutions to many distributed problems. The hitting time, i.e. the average time for the walk starting at a given vertex to first hit another given vertex is one of the main quantity used in the analysis of such algorithms. The growing use of peer-to-peer systems leads to a high bandwidth consumption and random walks are currently investigated as a solution to improve peer-to-peer systems efficiency. Such systems are often modeled by weighted graphs. We show how hitting times can be used in peer-to-peer distributed systems to compare the efficiency of deterministic and random-walks based procedures. An expression of the hitting times on a weighted graph in terms of effective resistances is established. Then, an efficient method to compute all the hitting times on a graph is presented. This method is illustrated by a detailed example.

Random walks constitute an attractive technique in distributed computing. In this paper, we present an original method using relationship between electrical resistance and random walks, to automatically compute quantities such as cover time, and more generally any processing time measure defined through hitting times. This method comes from electrical theory by using Millman's theorem.