The Head and tail random process appears, since the beginning of the art of computation, as a fundamental part of computer science. This talk will explore at a very basic level several ideas about computation of numbers, evaluation of quantities, checking techniques or recommendation evaluation. By small examples, we’ll try to establish links through ages between the probabilistic and algorithmic thinking.

One of the key features of small-worlds is the ability to route messages with few hops only using local knowledge of the topology. In 2000, Kleinberg proposed a model based on an augmented grid that asymptotically exhibits such property.

In this paper, we propose to revisit the original model from a simulation-based perspective. Our approach is fueled by a new algorithm that can draw an augmenting link in Õ(1).

The resulting speed gain enables detailed numerical evaluations. We show for example that in practice, the augmented scheme proposed by Kleinberg is more robust than predicted by the asymptotic behavior, even for very large finite grids. We also propose tighter bounds on the performance of Kleinberg's routing algorithm. At last, we show that, fed with realistic parameters, the model gives results in line with real-life experiments.

We present a Markov Decision Process (MDP) approach to compute the optimal on-line speed scaling policy to minimize the energy consumption of a processor executing a finite or infinite set of jobs with real-time constraints. The policy is computed off-line but used on-line. We provide several qualitative properties of the optimal policy: monotonicity with respect to the jobs parameters, comparison with on-line deterministic algorithms. Numerical experiments show that our proposition performs well when compared with off-line optimal solutions and out-performs on-line solutions oblivious to statistical information on the jobs.