-Load balancing algorithms are extensively used in parallel and distributed
-applications in order to reduce the execution times. They can be applied in
-different scientific fields from high performance computation to micro sensor
-networks. They are iterative by nature. In literature many kinds of load
-balancing algorithms have been studied. They can be classified according
-different criteria: centralized or decentralized, in static or dynamic
-environment, with homogeneous or heterogeneous load, using synchronous or
-asynchronous iterations, with a static topology or a dynamic one which evolves
-during time. In this work, we focus on asynchronous load balancing algorithms
-where computer nodes are considered homogeneous and with homogeneous load with
-no external load. In this context, Bertsekas and Tsitsiklis have proposed an
-algorithm which is definitively a reference for many works. In their work, they
-proved that under classical hypotheses of asynchronous iterative algorithms and
-a special constraint avoiding \emph{ping-pong} effect, an asynchronous
-iterative algorithm converge to the uniform load distribution. This work has
-been extended by many authors. For example, Cortés et al., with
-DASUD~\cite{cortes+ripoll+cedo+al.2002.asynchronous}, propose a
-version working with integer load. This work was later generalized by
-the same authors in \cite{cedo+cortes+ripoll+al.2007.convergence}.
-\FIXME{Rajouter des choses ici. Lesquelles ?}
-
-Although the Bertsekas and Tsitsiklis' algorithm describes the condition to
-ensure the convergence, there is no indication or strategy to really implement
-the load distribution. In other word, a node can send a part of its load to one
-or many of its neighbors while all the convergence conditions are
-followed. Consequently, we propose a new strategy called \emph{best effort}
+Load balancing algorithms are widely used in parallel and distributed
+applications to achieve high performances in terms of response time, throughput and resources usage. They play an important role and arise in various fields ranging from parallel and distributed
+computing systems to wireless sensor networks (WSN).
+The objective of load balancing is to orchestrate the distribution of the global workload so that
+the load difference between the computational resources of the network is
+minimized as low as possible. Unfortunately, this problem is known to be {\bf NP-hard} in its
+general forms and heuristics are required to achieve sub-optimal solutions but in
+polynomial time complexity.
+
+In this paper, we focus on asynchronous load balancing of non negative real numbers of {\it divisible loads}
+in homogeneous distributed systems. Loads can be divided in arbitrary {\it fine-grain} parallel parts size
+that can be processed independently of each other. This model of divisible loads arise in
+a wide range of real-world applications. Common examples among many, include signal processing,
+feature extraction and edge detection in image processing, records search in a huge databases,
+average consensus in WSN, pattern search in Big data and so on. % c'est pout toi raphael ;-)
+
+
+In the literature, the problem of load balancing has been formulated and studied in various ways. The first pioneering work is due to Bertsekas and Tsitsiklis~\cite{bertsekas+tsitsiklis.1997.parallel}. Under some specific hypothesis and {\it ping-pong} awareness conditions (see section~\ref{sec.bt-algo} for more details), an asymptotic convergence proof is derived.
+\begin{comment}
+This algorithm has been borrowed and adapted in many works. For instance, in~\cite{CortesRCSL02} a static load balancing (called DASUD) for non negative integer number of divisible loads in arbitrary networks topologies is investigated. The term {\it "static"} stems from the fact that no loads are added or consumed during the load balancing process. The theoretical correctness proofs of the convergence property are given. Some generalizations of the same authors' own work for partially asynchronous discrete load balancing model are presented in~\cite{cedo+cortes+ripoll+al.2007.convergence}. The authors prove that the algorithm's convergence is finite and bounded by the straightforward network's diameter of the global equilibrium threshold in the network. In~\cite{bahi+giersch+makhoul.2008.scalable}, a fault tolerant communication version is addressed to deal with average consensus in wireless sensor networks. The objective is to have all nodes converged to the average of their initial measurements based only on nodes' local information. A slight adaptation is also considered in~\cite{BahiCG10} for dynamic networks with bounded delays asynchronous diffusion. The dynamical aspect stands at the communication level as links between the network's resources may be intermittent.
+\end{comment}
+%in order to reduce the execution times. They can be applied in
+%different scientific fields from high performance computation to micro sensor
+%networks. In a distributed context (i.e. without centralization), they are iterative by nature.
+%In literature many kinds of load
+%balancing algorithms have been studied. They can be classified according
+%different criteria: centralized or decentralized, in static or dynamic
+%environment, with homogeneous or heterogeneous load, using synchronous or
+%asynchronous iterations, with a static topology or a dynamic one which evolves
+%during time. In this work, we focus on asynchronous load balancing algorithms
+%where computing nodes are considered homogeneous and with homogeneous load with
+%no external load.
+%In this context, Bertsekas and Tsitsiklis have proposed an
+%algorithm which is definitively a reference for many works. In their work, they
+%proved that under classical hypotheses of asynchronous iterative algorithms and
+%a special constraint avoiding \emph{ping-pong} effect, an asynchronous
+%iterative algorithm converges to the uniform load distribution. This work has
+%been extended by many authors. For example, Cortés et al., with
+%DASUD~\cite{cortes+ripoll+cedo+al.2002.asynchronous}, propose a
+%version working with integer load. This work was later generalized by
+%the same authors in \cite{cedo+cortes+ripoll+al.2007.convergence}.
+%\FIXME{Rajouter des choses ici. Lesquelles ?}
+Although Bertsekas and Tsitsiklis' describe the necessary conditions to
+ensure the algorithm's convergence, there is no indication or any strategy to really implement
+the load distribution. %In other word, a node can send some amount of its load to one or many of its neighbors while all the convergence conditions are followed.
+Consequently, we propose a new strategy called \besteffort{}
