# Quantum information of the Aharanov-Bohm ring with Yukawa interaction in the
presence of disclination

C. O. Edet  E-mail<EMAIL_ADDRESS>Faculty of Electronic
Engineering Technology, Universiti Malaysia Perlis, Malaysia.  Department of
Physics, Cross River University of Technology, Calabar, Nigeria.  F. C. E.
Lima  E-mail<EMAIL_ADDRESS>Department of Physics,
Universidade Federal do Ceará, Campus do Pici, Fortaleza, CE, Brazil.  C. A.
S. Almeida  E-mail<EMAIL_ADDRESS>Department of Physics, Universidade
Federal do Ceará, Campus do Pici, Fortaleza, CE, Brazil.  N. Ali  E-mail:
<EMAIL_ADDRESS>Faculty of Electronic Engineering Technology,
Universiti Malaysia Perlis, Malaysia.  M. Asjad  Department of Mathematics,
Khalifa University, Abu Dhabi 127788, United Arab Emirates.

###### Abstract

We investigate the quantum information by a theoretical measurement approach
of an Aharanov-Bohm (AB) ring with Yukawa interaction in curved space with
disclination. It is obtained the so-called Shannon entropy, through the
eigenfunctions of the system. The quantum states considered come from a
Schroedinger theory with the AB field in the background of curved space. With
this entropy it can explored the quantum information at the position space and
reciprocal space. Furthermore, we discussed how the magnetic field, the AB
flux, and the topological defect influence the quantum states and the
information entropy.

##  I Introduction

Structures with the profile of quantum rings attract the attention of several
researchers 1 , 2 , 3 , 4  due to their various technological applications, e.
g., nano-flash memories 5 , 6 , photonic detectors 5 , 7 , and spintronics 5 .
Generally, this type of system classifies into two classes, i. e., the one-
dimensional rings (configurations with constant radius) 8 , 9 , 10 , 11 , 12
and the two-dimensional rings (with variable radius) 13 , 14 , 15 , 16 . A
particular category of these structures is the Aharanov-Bohm (AB) rings.
Indeed, many works study AB rings 17 , 18 , 19 . In summary, we can understand
the AB ring as structures produced by particles in a circular motion and
subjected to the AB field. Actually, there are works in the literature
discussing these structures with mesoscopic decoherence 20 , electromagnetic
resonator 21 , and spin-orbit interaction 22 , 23 .

A physical model of great interest is a system composed of particles of spin-
zero 24 , 25 , 26 . In these systems, there is a screened Coulomb potential
known as the Yukawa potential (YP) 27 , 28 . This potential has the profile

$V(r)=-\frac{V_{1}e^{-\delta r}}{r},$ (1)

where the parameter $V_{1}$ is a coupling constant that regulates the
magnitude of the effective force and the parameter $\delta$ is a parameter
that makes the exponential argument dimensionless. Naturally, this potential
is central and attractive. These characteristics of this potential make the
interest in this topic growing 29 , 30 , 31 , 32 , 33 . In his seminal work,
H. Yukawa shows that this potential results in the interaction of a massive
scalar field with a massive bosonic field 34 . The fact is that today’s
theories with Yukawa’s interaction have several applications 35 , 36 , 37 . A
stimulating application is an interaction between two nuclei. In this case,
this application is interesting because two cores can experience attractive
interaction due to the interaction of charged pions 34 . In other words, pions
are similar to two particles interacting electromagnetically through the
exchange of photons.

Not far from quantum theory, information theory has been a practical tool to
investigate uncertainty measurements related to quantum-mechanical systems 38
, 39 , 40 , 41 , 42 . Information theory emerged with Shannon’s seminal paper
A Mathematical Theory of Communication in 1948 43 . Shannon sought to
understand the propagation of information in a noisy channel. Consequently, he
sought to explain the possible savings due to the statistical structure of the
original message and due to the nature of the final destination of the message
43 . Analyzing the likely interference events in the information, Shannon
proposes the entropic quantity

$S=-\sum_{i}\rho_{i}\text{ln}\rho_{i},$ (2)

where $\rho_{i}$ is the probability density associated with the event.
Shannon’s theory has also provided support for the cryptography 44 , and for
the noise theory 45 .

We seek in this study to answer the issue: How the magnetic field, the AB
flux, and the topological defect (i.e., the disclination defect) will
influence a particle restricted to a Yukawa-like potential. To reach our
purpose, we numerically investigate the Shannon entropy. This study is
influential because it allows us to predict how the measurement uncertainties
will change as the magnetic field, AB flux, or topological defect varies.

The paper is organized as follows. In Sec. II, we build the model considering
a particle confined by a Yukawa interaction. Furthermore, the model was
structured considering a disclination defect. In Sec. II, we exposed the
analytical solutions of the quantum eigenstates. Posteriorly, in Sec. III, the
numerical result of Shannon entropy is discussed. Finally, we close by
announcing in Sec. IV our findings.

##  II Theory and solutions

Let us consider that the particle is confined by a Yukawa potential (YP),
under the complete effect of the AB and magnetic fields. Let us assume that
there exists a disclination or topological defect in this region. The
disclination is described by the line element 46

$ds^{2}=dr^{2}+\alpha^{2}r^{2}d\phi^{2}+dz^{2}$ (3)

where $0<\alpha<1$ is the parameter associated with the deficit of angle. The
parameter $\alpha$ is related to the linear mass density $\hat{\mu}$ of the
string via $\alpha=1-4\hat{\mu}$ 47 . Notice that the azimuthal angle is
defined in the range $0\leq\phi\leq 2\pi$ 48 .

The Hamiltonian operator of a particle that is charged and confined to move in
the region of YP under the collective impact of AB flux and an external
magnetic fields with topological defect can be written in cylindrical
coordinates. Thus, the Schrödinger equation for this consideration is written
as follows 49 ;

$\left[\frac{1}{2\mu}\bigg{(}i\hbar\vec{\nabla}_{\alpha}-\frac{e}{c}\vec{A}_{\alpha}\bigg{)}^{2}-\frac{V_{1}\text{e}^{-\delta
r}}{r}\right]\psi(r,\phi)=E_{nm}\psi(r,\phi),$ (4)

where $E_{nm}$ denotes the energy level, $\mu$ is the effective mass of the
system, the vector potential which is denoted by “$\vec{A}$” can be written as
a superposition of two terms $\vec{A}=\vec{A}_{1}+\vec{A}_{2}$ having the
azimuthal components 49  and external magnetic field with
$\vec{\nabla}\times\vec{A}_{1}=\vec{B}$, $\vec{\nabla}\times\vec{A}_{2}=0$,
where $\vec{B}$ is the magnetic field.
$\vec{A}_{1}=\frac{\vec{B}\text{e}^{-\delta r}}{\alpha(1-\text{e}^{-\delta
r})}\hat{\phi}$ and $\vec{A}_{2}=\frac{\Phi_{AB}}{2\pi r}\hat{\phi}$
represents the additional magnetic flux $\Phi_{AB}$ created by a solenoid with
$\vec{\nabla}\cdot\vec{A}_{2}=0$. The Del and Laplacian operator are used as
in Ref. 49 .

The vector potential in full is written in a simple form as

$\vec{A}_{\alpha}=\bigg{(}0,\frac{\vec{B}\text{e}^{-\delta
r}}{\alpha(1-\text{e}^{-\delta r})}+\frac{\Phi_{AB}}{2\pi r},0\bigg{)}.$ (5)

Let us take a wave function in the cylindrical coordinates as

$\psi(r,\phi)=\frac{1}{\sqrt{2\pi r}}\text{e}^{im\phi}R_{nm}(r),$ (6)

where $m$ denotes the magnetic quantum number. Inserting this wave function
and the vector potential into Eq. (5) we arrive at the following radial
second-order differential equation:

$R^{\prime\prime}_{nm}(r)+\frac{2\mu}{\hbar^{2}}[E_{nm}-V_{\text{eff}}(r)]R_{nm}(r)=0,$
(7)

where $V_{\text{eff}}(r)$ is the effetive potential defined as

$\displaystyle V_{\text{eff}}(r)=$ $\displaystyle-\frac{V_{1}\text{e}^{-\delta
r}}{r}+\hbar\omega_{c}\left(\frac{m}{\alpha^{2}}+\frac{\xi}{\alpha}\right)\frac{\text{e}^{-\delta
r}}{(1-\text{e}^{-\delta
r})r}+\left(\frac{\mu\omega_{c}^{2}}{2}\right)\frac{\text{e}^{-2\delta
r}}{(1-\text{e}^{-\delta
r})^{2}}+\frac{\hbar^{2}}{2\mu}\left[\frac{(\frac{m}{\alpha^{2}}+\xi)^{2}-\frac{1}{4}}{r^{2}}\right],$
(8)

where $\xi=\frac{\Phi_{AB}}{\Phi_{0}}$ is an integer with the flux quantum
$\Phi_{0}=\frac{hc}{e}$ and $\omega_{c}=\frac{e\vec{B}}{\mu c}$ denotes the
cyclotron frequency. Fig. 1 is displayed the behavior of the effective
potential when the magnetic field, the topological defect, and the AB flux
undergo changes.

(a) (b)

(c)

Figure 1: (a) Effective potential when the magnetic field changes. (b)
Effective potential when the parameter $\alpha$ (topological defect) varies.
(c) Effective potential when flux AB varies.

Eq. (7) is a complicated differential equation that cannot be solvable easily
due to the presence of centrifugal term. Therefore, we employ the Greene and
Aldrich approximation scheme 50  to bypass the centrifugal term. This
approximation is given

$\frac{1}{r^{2}}=\frac{\delta^{2}}{(1-\text{e}^{-\delta r})^{2}}.$ (9)

We point out here that this approximation is only valid for small values of
the screening parameter $\delta$.

Inserting Eqs. (9) into Eq. (8) and introducing a new variable
$s=\text{e}^{-\delta r}$ allows us to obtain

$\displaystyle\frac{d^{2}R_{nm}}{ds^{2}}+\frac{1}{s}\frac{dR_{nm}(s)}{ds}+\frac{1}{s^{2}(1-s^{2})^{2}}[-(\varepsilon_{nm}+\beta_{0}+\beta_{2})s^{2}+(2\varepsilon_{nm}+\beta_{0}-\beta_{1})s-(\varepsilon_{nm}+\eta)]R_{nm}(s)=0.$
(10)

For Mathematical simplicity, let’s introduce the following dimensionless
notations;

$\displaystyle\varepsilon_{nm}=-\frac{2\mu
E_{nm}}{\hbar^{2}\delta^{2}},\,\,\,\,\,\,\beta_{0}=\frac{2\mu
V_{1}}{\hbar^{2}\delta},\,\,\,\,\,\,\beta_{1}=\frac{2\mu\omega_{c}}{\hbar\delta}\bigg{(}\frac{m}{\alpha^{2}}+\frac{\xi}{\alpha}\bigg{)},\,\,\,\,\,\,\beta_{2}=\frac{\mu^{2}\omega_{c}^{2}}{\hbar^{2}\delta^{2}},\,\,\,\,\,\text{and}\,\,\,\,\,\,\eta=\bigg{(}\frac{m}{\alpha}+\xi\bigg{)}^{2}-\frac{1}{4}.$
(11)

In order to solve eq. (10), we have transform the differential equation (8)
into a form solvable by any of the existing standard mathematical technique.
Hence, we take the radial wave function of the form

$R_{nm}(s)=s^{\lambda}(1-s)^{\nu}f_{nm}(s),$ (12)

where $\lambda=\sqrt{\varepsilon_{nm}+\eta}$, and
$\nu=\frac{1}{2}+\sqrt{\frac{1}{4}+\beta_{1}+\beta_{2}+\eta}$. On substitution
of Eq. (12) into Eq. (10), we obtain the following hypergeometric equation:

$\displaystyle
s(1-s)f^{\prime\prime}_{nm}(s)+[(2\lambda+1)-(2\lambda+2\nu+1)s]f^{\prime}_{nm}(s)-[(\lambda+\nu)^{2}-(\sqrt{\varepsilon_{nm}+\beta_{0}+\beta_{2}})^{2}]f_{nm}(s)=0.$
(13)

By considering the finiteness of the solutions, the quantum condition is given
by

$(\lambda+\nu)-(\sqrt{\varepsilon_{nm}+\beta_{0}+\beta_{2}})=-n$ (14)

which in turn transforms into the energy eigenvalue equation follows;

$\displaystyle\varepsilon_{nm}=$
$\displaystyle-\eta+\frac{1}{4}\left[\frac{\beta_{0}+\beta_{2}-\eta-\bigg{(}n+\frac{1}{2}+\sqrt{\frac{1}{4}+\beta_{1}+\beta_{2}+\eta}\bigg{)}^{2}}{n+\frac{1}{2}+\sqrt{\frac{1}{4}+\beta_{1}+\beta_{2}+\eta}}\right]^{2}.$
(15)

Substituting Eq. (11) into Eq. (15) and carrying some simple manipulative
algebra, we arrive at the energy eigenvalue equation of the Yukawa potential
in the presence of magnetic and AB fields with topological defect in the form

$\displaystyle E_{nm}=$
$\displaystyle\frac{-(\hbar^{2}\delta^{2}/8\mu)}{\bigg{[}n+\frac{1}{2}+\sqrt{\frac{\mu^{2}\omega_{c}^{2}}{\hbar^{2}\delta^{2}}+\frac{2\mu\omega_{c}}{\hbar\delta}\bigg{(}\frac{m}{\alpha^{2}}+\frac{\xi}{\alpha}\bigg{)}+\bigg{(}\frac{m}{\alpha}+\xi\bigg{)}^{2}}\bigg{]}}\bigg{\\{}\frac{2\mu
V_{1}}{\hbar^{2}\delta}+\frac{\mu^{2}\omega_{c}^{2}}{\hbar^{2}\delta^{2}}-\eta-\bigg{[}n+\frac{1}{2}+$
$\displaystyle+$
$\displaystyle\sqrt{\frac{\mu^{2}\omega_{c}^{2}}{\hbar^{2}\delta^{2}}+\frac{2\mu\omega_{c}}{\hbar\delta}\bigg{(}\frac{m}{\alpha^{2}}+\frac{\xi}{\alpha}\bigg{)}+\bigg{(}\frac{m}{\alpha}+\xi\bigg{)}^{2}}\bigg{]}^{2}\bigg{\\}}+\frac{\hbar^{2}\delta^{2}\eta}{2\mu}.$
(16)

Furthermore, the wave eigenfunction is

$\displaystyle\psi_{nm}(r,\phi)=$ $\displaystyle\frac{1}{\sqrt{2\pi
r}}\text{e}^{im\phi}\,_{1}F_{1}(a,b,c;\text{e}^{-\delta r})\text{e}^{-\delta
r\sqrt{\varepsilon_{nm}+\eta}}(1-\text{e}^{-\delta
r})^{\frac{1}{2}+\sqrt{\frac{1}{4}+\beta_{1}+\beta_{2}+\eta}},$ (17)

where $a=\lambda+\nu+\sqrt{\varepsilon_{nm}+\beta_{0}+\beta_{2}}$,
$b=\lambda+\nu-\sqrt{\varepsilon_{nm}+\beta_{0}+\beta_{2}}$, and
$c=2\lambda+1$.

In Fig. 2 are displayed the plots of the probability density of the particle
confined to the Yukawa interaction (Eq. (8)) in the presence of a disclination
defect. Note that the wave function profile changes when the magnetic field,
the AB flux, and the topological defect change in the theory. Furthermore,
when the declination defect (i.e., when $\alpha>1$) is changed, the
probability density of the wave function translates in its profile so that the
highest probability is close to the atomic core. Here, it is interesting to
mention that the excited eigenstates of the model will have a profile similar
to that shown in Fig. 2. However, a change in the height of the solitonic wave
function can be verified in excited states.

(a) (b)

(c)

Figure 2:  Probability density $|\psi(r)|^{2}$ in position space $r$ when
magnetic field changes (a), the parameter $\alpha$ (topological defect) varies
(b) and AB flux varies (c).

##  III Shannon’s entropy

Quantum information entropy has helped to understand the physics of several
systems 51 , 52 , 53 . Indeed, one of the quantum entropies used to study the
information of quantum systems is the Shannon entropy. Shannon’s entropy
emerged within the scope of information theory seeking to describe the best
way to propagate information between a source and a receiver 43 . Along with
the development of the Shannon entropy concept in physics, studies on the
thermodynamics of an ensemble of particles led to mathematical expressions
with a similar profile. This similarity of Shannon information and Boltzmann
entropy allowed Shannon information to be called Shannon entropy 54 . Some
conceptual applications of Shannon’s entropy help us understand the
information and uncertainty measurement of quantum systems, e. g., the Shannon
entropy gives us the uncertainty of non-Hermitian particle systems 55 .
Furthermore, Shannon formalism allowed the study of fermionic particles 56 ,
problems with effective mass distribution 57 , 58 , and mechanical-quantum
models with double-well potential 59 .

An interpretation of the Shannon entropy of a quantum-mechanical system tells
us the measure of uncertainties of a probability distribution associated with
a source of information 60 , 61 . The Born interpretation of the quantum
mechanics 62  takes us to the statistical perception of the stationary quantum
system, i. e.,

$\displaystyle\rho(\vec{r})\,dr=|\psi(\vec{r},t)|^{2}\,dr\equiv|\psi(\vec{r})|^{2}\,dr.$
(18)

In this case, $\rho(\vec{r})$ is the probability of finding the particle in
the state $\psi(\vec{r},\,t)$ between $\vec{r}$ and $\vec{r}+d\vec{r}$ 62 .
Furthermore, $|\psi(\vec{r},\,t)|^{2}$ is the probability density of the
quantum-mechanical system.

Let us now study Shannon’s entropy in the context of quantum mechanics.
Remembering that the probability density has the form of Eq. (18), we define
Shannon’s entropy as

$\displaystyle S=-\sum_{i}\rho_{i}\,\text{ln}\rho_{i},$ (19)

so that for a probability density $\rho_{i}$ of a continuous system in
position space, Shannon entropy takes the form

$\displaystyle
S_{r}=-\int_{-\infty}^{\infty}\,|\psi(r)|^{2}\,\text{ln}(|\psi(r)|^{2})\,dr.$
(20)

On the other hand, Shannon’s entropy in reciprocal space (or momentum space)
is

$\displaystyle
S_{k}=-\int_{-\infty}^{\infty}\,|\psi(k)|^{2}\,\text{ln}(|\psi(k)|^{2})\,dk.$
(21)

Perceive that the expressions (20) and (21) have only two independent
variables. Our model is two-dimensional, i. e., a model of (2+1)D with spatial
coordinates $r$ and $\phi$. However, $\phi$ is a cyclic coordinate. In this
way, only the $r$ coordinate contributes to Shannon information.

The wave function in reciprocal space $\psi(k)$ is given by Fourier transform,
namely,

$\displaystyle\psi(k)=\frac{1}{\sqrt{2\pi}}\int_{-\infty}^{\infty}\,\psi(r)\,\text{e}^{-irk}\,dr.$
(22)

The entropic quantities of Eqs. (20) and (21) play a role analogous to the
Heisenberg uncertainty measures 55 , 56 . An entropic uncertainty relation
that relates to the entropic uncertainties was obtained by Beckner 61 ,
Bialynicki-Birula and Mycielski (BBM) 63 . The BBM relation of uncertainties
is

$\displaystyle S_{r}+S_{k}\geq\text{D}(1+\text{ln}\pi),$ (23)

where D is the dimension of effective spatial coordinates, i. e., the number
of spatial coordinates that contribute to the information propagation. In our
case, the results must respect the relation

$\displaystyle S_{r}+S_{k}\geq 2.14473.$ (24)

To investigate the quantum information of the model presented in Sec. II, we
consider the wave function (17) and numerically normalize it through the
expression

$\displaystyle\int_{-\infty}^{\infty}\,|\psi_{nm}(r,\phi)|^{2}\,dr=1.$ (25)

After, we use Eq. (20) to calculate Shannon entropy in position space. Using
the Fourier transform (22), it comes to eigenfunctions at the reciprocal
space. With the eigenfunctions normalized in the momentum space, we use Eq.
(21) to obtain Shannon’s entropy in this space. The numerical results of
Shannon’s entropy for the first energy levels are in tables 1 and 2. We
presented the physical discussion of the results found in the next section.

Table 1: Numerical result of Shannon’s entropy for several values of the
magnetic field and flux AB.

$n$ | $m$ | $B$ | $\Phi_{AB}$ | $S_{r}$ | $S_{k}$ | $S_{r}+S_{k}$
---|---|---|---|---|---|---
0 | 0 | 1 | 1 | 1.32078 | 2.91721 | 4.23799
2 | 1 | 0.69776 | 3.53949 | 4.23725
4 | 1 | 0.20082 | 4.37062 | 4.57144
1 | 2 | 0.68816 | 3.24081 | 3.92897
1 | 4 | 0.20081 | 5.93350 | 6.13431
1 | 0 | 1 | 1 | 4.41786 | 7.14836 | 11.56622
2 | 1 | 0.53510 | 10.14113 | 10.67623
4 | 1 | 0.41849 | 10.44393 | 10.86242
1 | 2 | 0.83093 | 4.83668 | 5.66761
1 | 4 | 0.19793 | 6.30831 | 6.50624
1 | 1 | 1 | 1 | 6.52497 | 8.45892 | 14.98389
2 | 1 | 0.36401 | 11.48506 | 11.84907
4 | 1 | 0.31416 | 11.78786 | 12.10202
1 | 2 | 0.35912 | 6.29333 | 6.65245
1 | 4 | 0.03149 | 6.36141 | 6.39290

Table 2: Numerical result of Shannon’s entropy when the disclination varies.

$n$ | $m$ | $\alpha$ | $S_{r}$ | $S_{k}$ | $S_{r}+S_{k}$
---|---|---|---|---|---
0 | 0 | 0.1 | -1.43473 | 5.30857 | 3.87384
0.2 | -0.73813 | 3.14145 | 2.40332
0.4 | 1.24625 | 1.96739 | 3.21364
1 | 0 | 0.1 | -1.52895 | 8.04484 | 6.51589
0.2 | -0.91699 | 6.30221 | 5.38522
0.4 | -0.05982 | 4.30012 | 4.24030
1 | 1 | 0.1 | -1.60572 | 9.35928 | 7.75356
0.2 | -0.96676 | 9.14016 | 8.17340
0.4 | -0.31977 | 5.52721’ | 5.20744

##  IV Final remarks

Throughout the paper, we studied the influences of the external magnetic
field, the AB flux, and the disclination defect on the AB quantum ring. The
wave function that describes the system is the confluent hypergeometric
function. Furthermore, the complete solution set, i. e., the wave
eigenfunctions, reproduces a null probability at the spatial infinity. This
condition leads us to a discretized energy spectrum indicating the existence
of bound states.

We measure the Shannon entropy to analyze the quantum information. It was
possible to notice that the disclination, the external magnetic field, and AB
flux directly influence the quantum information of the system. Considering the
numerical results displayed in tables 1 and 2, it is notorious that the
informational content decreases in the position space when the contribution of
the AB flux to the magnetic field increases. This is because the contribution
of the magnetic field and the AB field, when increasing their intensity, make
the quantum rings more localized, so the informational content decreases.
Indeed, this indicates a decrease in the uncertainties related to the
measurements of the position of the AB ring. In counterpoint, it is prominent
that if the disclination increases, quantum information increases (in position
space). Therefore, the increases in information (or uncertainties) in the
position space is grow up. Thereby, this is a consequence of the type of
defect. In the absence of disclination (i. e., $\alpha=1$), position
uncertainty is greater. However, occurring the rotational symmetry breaking,
the position measurement uncertainties begin to decreases. In this case, this
is because the ring became thinner and thinner.

On the other hand, quantum information (and consequently, measurement
uncertainty) increases at the momentum space. The measurement uncertainties
increase as the magnetic field and AB flux increase. However, when topological
defect increase, the information decrease in reciprocal space. The increment
(or reduction) of the information at the momentum space is a consequence of
the Heisenberg uncertainty principle (HUP). Moreover, in the communication
theory, the BBM relation plays the role of the HUP. Here is essential to
mention that BBM relation is valid in our model.

A direct perspective of this work is the study of the quantum information
measurement of a quantum ring in the presence of other topological defects.
Another possibility is to study the relativistic version of this theory. We
hope to produce these studies in the future.

## Acknowledgements

This research has been carried out under LRGS Grant 9012-00009 Fault-tolerant
Photonic Quantum States for Quantum Key Distribution provided by Ministry of
Higher Education of Malaysia (MOHE) and by Khalifa University through project
no. 8474000358 (FSU-2021-018). F. C. E. Lima is grateful the Coordenação de
Aperfeiçoamento do Pessoal de Nível Superior (CAPES), for the financial
support. C. A. S. Almeida thanks the Conselho Nacional de Desenvolvimento
Científico e Tecnológico (CNPq), for the financial support in the project no
309553/2021-0.

## References

  * [1] T. Kuroda, T. Mano, T. Ochiai, S. Sanguinetti, K. Sakoda, G. Kido and N. Koguchi, Phys. Rev. B 72, (2005) 205301.
  * [2] T. Chakraborty and P. Pietiläinen, Phys. Rev. B 50, (1994) 8460.
  * [3] J. C. Ahn, K. S. Kwak, B. H. Park, H. Y. Kang, J. Y. Kim and O’Dae Kwon, Phys. Rev. Lett. 82, (1999) 536.
  * [4] A. L. S. Netto, C. Chesman and C. Furtado, Phys. Lett. A 372, (2008) 3894.
  * [5] V. M. Fomin (Editor), Physics of Quantum Rings, in NanoScience and Technology (Springer-Verlag, Berlin, Heidelberg, 2014).
  * [6] T. Nowozin, Self-organized Quantum Dots for Memories: Electronic Properties and Carrier Dynamics, in Springer Theses (Springer, 2014).
  * [7] P. Michler, Single Quantum Dots: Fundamentals, Applications, and New Concepts, Vol. 90 (Springer-Verlag, Berlin, 2003).
  * [8] H. F. Cheung, Y. Gefen, E. K. Riedel and W. H. Shih, Phys. Rev. B 37, (1988) 6050.
  * [9] F. E. Meijer, A. F. Morpurgo and T. M. Klapwijk, Phys. Rev. B 66, (2002) 033107.
  * [10] D. Frustaglia, K. Richter, Phys. Rev. B 69, (2004) 235310.
  * [11] A. Lorke, R. J. Luyken, A. O. Govorov, J. P. Kotthaus, J. M. Garcia and P. M. Petroff, Phys. Rev. Lett. 84, (2000) 2223.
  * [12] S. Kettemann, P. Fulde and P. Strehlow, Phys. Rev. Lett. 83, (1999) 4325.
  * [13] W.C. Tan and J.C. Inkson, Phys. Rev. B 60, (1999) 5626.
  * [14] D. V. Bulaev, V. A. Geyler and V. A. Margulis, Phys. Rev. B 69, (2004) 195313.
  * [15] C. M. Duque, A. L. Morales, M. E. Mora-Ramos and C. A. Duque, J. Lumin. 143, (2013) 81.
  * [16] M. P. Nowak, B. Szafran, Phys. Rev. B 80, (2009) 195319.
  * [17] R. R. S. Oliveira, A. A. A. Filho, F. C. E. Lima, R. V. Maluf and C. A. S. Almeida, Eur. Phys. J. Plus 134, (2019) 495.
  * [18] S. Russo, J. B. Oostinga, D. Wehenkel, H. B. Heersche, S. S. Sobhani, L. M. K. Vandersypen and A. F. Morpurgo, Phys. Rev. B 77, (2008) 085413.
  * [19] A. Levy Yeyati and M. Büttiker, Phys. Rev. B 52, (1995) R14360(R).
  * [20] A. E. Hansen, A. Kristensen, S. Pedersen, C. B. Sorensen and P. E. Lindelof, Phys. Rev. B 64, (2001) 045327.
  * [21] B. Reulet, M. Ramin, H. Bouchiat and D. Mailly, Phys. Rev. Lett. 75, (1995) 124.
  * [22] U. Aeberhard, K. Wakabayashi and M. Sigrist, Phys. Rev. B 72, (2005) 075328.
  * [23] I. A. Shelykh, N. T. Bagraev, N. G. Galkin and L. E. Klyachkin, Phys. Rev. B 71, (2005) 113311.
  * [24] Faizuddin Ahmed, Scientific Reports 12, (2022) 8794.
  * [25] S. Zare, H. Hassanabadi, A. Guvendi and W. S. Chung, Int. J. Mod. Phys. A 37, (2022) 2250033.
  * [26] M. S. Shikakhwa and N. Chair, Eur. Phys. J. Plus 137, (2022) 560.
  * [27] H. Yukawa, Proceedings of the Physico-Mathematical Society of Japan. 3rd Series, v. 17, (1935) 48.
  * [28] J. S. Rowlinson, Physica A 156, (1989) 15.
  * [29] U. S. Okorie, E. E. Ibekwe, A. N. Ikot, M. C. Onyeaju and E. O. Chukwuocha, J. Kor. Phys. Soc. 73, (2018) 1211.
  * [30] C. O. Edet, P. O Okoi and S. O Chima, Rev. Bras. Ensino Fís. 42, (2020) e20190083.
  * [31] S. A. Khrapak, A. V. Ivlev, G. E. Morfill and S. K. Zhdanov, Phys. Rev. Lett. 90, (2020) 225002.
  * [32] A. Loeb and N. Weiner, Phys. Rev. Lett. 106, (2011) 171302.
  * [33] M. Hamzavi, M. Movahedi, K.-E. Thylwe and A. A. Rajabi, Chin. Phys. Lett. 29, (2012) 080302.
  * [34] B. R. Martin and G. Shaw, Particle Physics, 3rd, (Wiley, United Kingdom, 2008).
  * [35] J. C. N. Carvalho, W. P. Ferreira, G. A. Farias, and F. M. Peeters, Phys. Rev. B 83, (2011) 094109.
  * [36] H. Bahlouli, M. S. Abdelmonem and I. M. Nasser, Phys. Scr. 82, (2010) 065005.
  * [37] T. Imbo, A. Pagnamenta, U. Sukhatme, Phys. Lett. A 105, (1984) 183.
  * [38] L. G. Jiao, L. R. Zan, Y. Z. Zhang and Y. K. Ho, Int. J. Quantum Chem. 117, (2017) e25375.
  * [39] P. O. Amadi, A. N. Ikot, A. T. Ngiangia, U. S. Okorie, G. J. Rampho and H. Y. Abdullah, Int. J. Quantum Chem. 120, (2020) e26246.
  * [40] J. G. Dehesa, E. D. Belega, I. V. Toranzo and A. I. Aptekarev, Int. J. Quantum Chem. 119, (2019) e25977.
  * [41] C. Martínez-Flores, Phys. Lett. A 386, (2021) 126988.
  * [42] G. A. Sekh, A. Saha and B. Talukdar, Phys. Lett. A 382, (2018) 315.
  * [43] C. E. Shannon, Bell Syst. Tecn. J. 27, (1948) 379.
  * [44] F. Grasselli, Quantum Cryptography, Springer, Cham, 2021.
  * [45] J. M. Amigó, R. Dale and P. Tempesta, Chaos 31, (2021) 013115.
  * [46] H. Hassanabadi and M. Hosseinpour, Eur. Phys. J. C 76, (2016) 553.
  * [47] K. Bakke, L.R. Ribeiro, C. Furtado and J.R. Nascimento, Phys. Rev. D 79, (2009) 024008.
  * [48] P. Nwabuzor, C. Edet, A. Ndem Ikot, U. Okorie, M. Ramantswana and R. Horchani, Entropy 198, (2021) 1060.
  * [49] C. O. Edet and A. N. Ikot, J. Low Temp. Phys. 203, (2021) 84.
  * [50] R. L. Greene and C. Aldrich, Phys. Rev. A 14, (1976) 2363.
  * [51] S. Dong, G. -H. Sun, S. -H. Dong and J. P. Draayer, Phys. Lett. A 378, (2014) 124.
  * [52] G. -H. Sun, M. A. Aoki and S. -H. Dong, Chin. Phys. B 22, (2013) 050302.
  * [53] X. -D. Song,G. -H. Sun and S. -H. Dong, Phys. Lett. A 379, (2015) 1402.
  * [54] R. K. Pathria, Statistical Mechanics, $2^{nd}$ Ed., Butterworth-Heinemann, Oxford, 1996.
  * [55] F. C. E. Lima, A. R. P. Moreira, L. E. S. Machado and C. A. S. Almeida, Int. J. Quantum Chem. 121 (18), (2021) e26749.
  * [56] F. C. E. Lima, A. R. P. Moreira and C. A. S. Almeida, Int. J. Quantum Chem. 121, (2021) e26645.
  * [57] G. Yanez-Navarro, G. -H. Sun, T. Dytrych, K. D. Launey, S.-H. Dong, J. P. Draayer, Ann. Phys. 348, (2014) 153.
  * [58] F. C. E. Lima, Ann. Phys. 442, (2022) 168906.
  * [59] G. -H. Sun, S. -H. Dong, K. D. Launey, T. Dytrych and Jerry P. Draayer, Int. J. Quantum Chem. 115, (2015) 891.
  * [60] I. I. Hirschmann Jr., Amer. J. Math. 79, (1957) 152.
  * [61] W. Beckner, Ann. Math. 102, (1975) 159.
  * [62] M. Born, Science 122, (1955) 675.
  * [63] I. Bialynicki-Birula, J. Mycielski, Comm. Math. Phys. 44, (1975) 129.


# Pando: a Volunteer Computing Platform for the Web

Erick Lavoie  PhD CandidateSchool of Computer ScienceMcGill University845
Sherbrooke Street WestMontrealQuebecH3A 0G4Canada<EMAIL_ADDRESS>,  Laurie Hendren  Full ProfessorSchool of Computer ScienceMcGill
University845 Sherbrooke Street WestMontrealQuebecH3A 0G4Canada
<EMAIL_ADDRESS>,  Frederic Desprez  Senior ResearcherCentre de recherche
Grenoble Rhône-AlpesINRIA Grenoble Rhône-Alpes17, rue des MartyrsGrenoble
Cedex38054France<EMAIL_ADDRESS>and  Miguel Correia  INESC-ID,
Instituto Superior Técnico, Universidade de Lisboa
<EMAIL_ADDRESS>
###### Abstract.

Volunteer computing is currently successfully used to make hundreds of
thousands of machines available free-of-charge to projects of general
interest. However the effort and cost involved in participating in and
launching such projects may explain why only a few high-profile projects use
it and why only 0.1% of Internet users participate in them. In this paper we
present Pando, a new web-based volunteer computing system designed to be easy
to deploy and which does not require dedicated servers. The tool uses new
demand-driven stream abstractions and a WebRTC overlay based on a fat tree for
connecting volunteers. Together the stream abstractions and the fat-tree
overlay enable a thousand browser tabs running on multiple machines to be used
for computation, enough to tap into all machines bought as part of previous
hardware investments made by a small- or medium-company or a university
department. Moreover the approach is based on a simple programming model that
should be both easy to use by itself by JavaScript programmers and as a
compilation target by compiler writers. We provide a command-line version of
the tool and all scripts and procedures necessary to replicate the experiments
we made on the Grid5000 testbed.

Volunteer Computing, Streams, Pull-Streams, MATLAB, JavaScript, Web
Technologies, WebRTC

††copyright: rightsretained††journalyear: 2018††publicationmonth: 3††article:
0

##  1\. Introduction

In volunteer computing, volunteers provide free-of-charge access to their
machine, sponsoring the purchasing cost of the hardware and the electricity
cost of computation. This way, computing resources that would otherwise be
idle are used for projects of general interest. This approach is currently
used with great success for the search of extra-terrestrial intelligence in
SETI@Home (seti@home, ), and for protein folding and computational drug design
in Folding@Home (folding@home, ). These are two examples out of the more than
thirty projects as part of the Berkeley Open Infrastructure for Network
Computing (BOINC) (boinc, ), the distributed.net (distributed.net, ), and the
World Community Grid (WCG, ) initiatives.

However, current approaches to the deployment of volunteer computing projects
require a significant effort for adapting the computation client, configuring
a server, and creating a marketing website (boincintro, ). In addition, they
usually require buying a dedicated server and have potentially costly
maintenance (boinc-needs-volunteers, ). Finally, they require efforts from
volunteers to install a computation client on their machine.

In this paper, we propose a volunteer computing approach that is simple and
quick to deploy, does not require a dedicated server, and can leverage a wide
variety of end-user devices by basing it on web technologies. Doing so should
make the approach beneficial to a wider number of projects, especially those
with a significant but smaller required amount of total computing power
compared to existing projects.

We present the design and evaluation of Pando111Pando, (”I spread” in Latin),
is also the name of the largest colony of genetically identical trees that
share the same root system. It comprises 40,000 trunks (stems). It is believed
to be 80,000 years old, making it one of the oldest living organism (pando-
tree, )., a tool that provides the ability to stream jobs to at least a
thousand of concurrently running browsers, while tolerating the disconnection
of cooperative volunteers by transparently reassigning incomplete jobs to
other volunteers. It takes a potentially infinite stream of values as input,
applies a JavaScript function on them, and outputs the corresponding results
in the same order as the inputs were received, regardless of the relative
processing speed of the different volunteers. The tool is compatible with
other Unix utilities so inputs are provided through the standard input and
results are obtained on the standard output, one per line. A processing
workflow is therefore expressed by integrating Pando in a Unix pipeline.

At the heart of Pando are stream abstractions structured around the pull-
stream pattern (pull-streams, ), a functional implementation pattern proposed
by Dominic Tarr. The pattern is consumer-driven and elegantly solves subtle
problems that arise in other producer-driven implementations when composing
multiple stream transformations in a pipeline, especially regarding flow-
control and error propagation (stream-history-node.js, ). We introduce new
abstractions structured along the pull-stream pattern for delegating values in
a stream to multiple concurrent unreliable sub-streams (volunteers) and
regulating the flow of values to quickly recover from sub-stream failures.

We use the WebRTC communication framework (webrtc-draft, ; Johnston:2012, ) to
connect volunteer code running inside browser tabs to the Pando tool. In order
to make the tool scalable, we bound the maximum number of connections between
nodes by organizing volunteers in a tree overlay rooted in the Pando tool
process. Each node handles the input-output traffic for all their children and
relays it to its parent, forming a fat-tree overlay (Leiserson85, ). We
designed the overlay so it quickly grows when a large number of volunteers
join, such as when a project becomes viral on social media or when it is
deployed on idle machines in a data center. The main goal of the tree design
was to test and debug the pull-stream abstractions to ensure they can
correctly and efficiently manage at least a thousand browser processes on
multiple machines.

To create a JavaScript function whose application can be distributed with
Pando, only two requirements are necessary: (1) it needs to accept an input
value and a callback function (to return the output value) as arguments; (2)
it should only use JavaScript packages that can execute in a browser. This
interface makes it easy to use with many existing JavaScript packages when
developers write a processing function by hand and also when a function is
generated by a compiler. Code written in other languages may therefore also be
executed on Pando (provided a compiler to JavaScript exists). To show it is
simple to do so, we adapted an existing MATLAB-to-JavaScript compiler,
Matjuice (Foley-Bourgon:2016, ; matjuice-repository, ), to produce Pando-
compatible JavaScript code.

In the remainder of the paper we present our web-based approach to volunteer
computing, the overall design of the Pando tool and its key components, how to
use it, and how well it scales. Our intention with this paper is to provide a
first comprehensive overview of the approach and its validation through a
tested concrete tool. We therefore make the following contributions:

  1. (1)

we propose a web-based volunteer computing approach based on a streaming
paradigm that does not require a dedicated server and is simple to deploy and
implement;

  2. (2)

we provide open source implementations in JavaScript of new stream
abstractions for volunteer computing, each individually available through the
node package manager (npm) for reuse in other projects (pull-lend-
implementation, ; pull-lendstream-implementation, ; pull-limit-implementation,
) and composable with a growing list of community developed pull-stream
modules (pull-stream-modules, );

  3. (3)

we explain the key design features of a new WebRTC tree overlay that enables
quickly scaling up to a thousand browser tabs running on multiple machines and
we provide a reusable implementation in JavaScript (webrtc-tree-overlay, );

  4. (4)

we adapt an existing MATLAB-to-JavaScript compiler, Matjuice (Foley-
Bourgon:2016, ; matjuice-repository, ), to produce Pando-compatible JavaScript
code, enabling jobs to be defined in MATLAB;

  5. (5)

we provide Pando as an open source command-line tool (pando) (pando-
repository, ) compatible with Unix pipelines that uses the stream abstractions
and tree overlay; we also provide the testing scripts (pando-handbook, ) for
replicating all experiments we performed both for correctness and performance
on the Grid’5000 testbed (itself accessible free-of-charge to other
researchers upon request).

##  2\. Background and Overview

In this section we provide some background on the general approach used in
existing volunteer computing systems, and we give a high-level overview of our
new approach which leverages JavaScript and web technologies, and provides a
system which is easy to deploy on a variety of web-enabled devices.

###  2.1. Current Solutions in Use for Volunteering and Launching Volunteer
Computing Projects

Existing volunteer computing platforms require significant effort from both
volunteers and project owners, and induce additional costs to project owners.

To participate in a volunteer computing project, volunteers must install a
computation client that runs in the background, usually when the computer is
idle. The effort required from volunteers in installing a computation client
may explain why less then 0.1% of Internet users participate in them222There
are about 300,000 active volunteers in the two projects combined at the time
of writing, compared to an estimated 3.6 billions Internet users in 2016
(internetworldstats, )., leaving unused most of the computing capability
theoretically available on the Internet.

To launch a new volunteer computing project, the project owners need to adapt
their computation client, usually previously written in C++ or Fortran, setup
a coordination server, and build a marketing website. Each of these three
tasks requires about a month of effort to complete and a dedicated server
(boincintro, ). Moreover, the yearly cost for a project that uses a petaflop
of computing is about 100,000$US (boinc-needs-volunteers, )333Renting the same
amount of computing power would cost 40M$/year on Amazon (boinc-needs-
volunteers, ).. The required development time and maintenance cost therefore
makes the approach viable only for a few high-profile long-running projects.

###  2.2. Pando’s Approach

In contrast, the Pando tool aims to reduce cost and effort: no dedicated
server to buy, no computation client to install, no marketing website to
setup. Using our system operates as follows: (1) Pando is started locally on a
laptop, desktop, or server and provides a web page url for volunteers to
connect to. If the local device does not have a publicly reachable IP address,
a small micro-server (pando-server, ) may be deployed on a cloud platform to
establish the initial connections. At the time of writing, the free tier of
the Heroku cloud platform444https://www.heroku.com/ is sufficient for that
purpose. (2) The url is opened in browser tabs on all other available
compatible devices, one per core on each machine. (3) Optionally, the url is
shared on social media to invite friends to connect and contribute more
computing power. (4) The tool runs until completion of all jobs.

####  2.2.1. Using JavaScript and Web Technologies

Our approach is based on web technologies for many reasons. JavaScript VMs
embedded in modern browsers execute JavaScript at a speed within a factor of 3
of equivalent numerical code written in C (Khan:2014, ), making the
performance sufficiently close to C to benefit from executing jobs inside web
browsers. They also provide a security sandbox that prevents code executing
within a web page from tampering with the host operating system. With WebRTC
(webrtc-draft, ), it is now possible to connect browsers directly, by-passing
the need for a server to relay all communications between the client of a
volunteer platform and the volunteers themselves. JavaScript serves as a
universal program representation to abstract the multitudes of combinations of
hardware devices (phones, tablets, laptops, etc.), operating systems, and web
browsers. More generally, the web technologies benefit from the combined
ongoing and full-time development and maintenance work of all browser vendors
and explicit efforts at interoperability, as well as collaborative design of
the Web APIs and protocols.

Moreover, existing social media platforms enable the quick bootstrap of new
platforms by providing connectivity with millions of users. It is therefore
possible to use them as publish-subscribe mechanisms to announce work and
quickly join volunteering efforts. For example, the official Twitter account
of a known and trusted scientific group can be used to share the url to a task
that requires volunteers to participate. A volunteer may then open the
corresponding url manually, or a third-party browser extension or background
process may open any url associated with a given hashtag (ex: #pando) from a
set of trusted accounts. It would therefore be possible for short-lived
volunteer projects to become viral and quickly mobilize thousands or even
millions of volunteers.

####  2.2.2. Using a Stream-based Paradigm

Our approach is based on a demand-driven streaming paradigm: it provides a
clear programming model for the project developer to use, enables working with
an infinite stream of jobs, and helps organize the implementation of Pando
around a few clear and simple abstractions.

####  2.2.3. Replacing the Server with a Tree of Volunteers

To replace the dedicated server, volunteers are arranged in a tree that is
dynamically created and maintained. Initially new volunteers start as
processing leaves. As more volunteers join, some of the existing volunteers
stop processing values and become coordinators of the newer volunteer
children, effectively becoming internal nodes in the tree. They manage the
distribution of input values and the retrieval and the reordering of results
of their children. If all its children disconnect, a coordinator goes back to
processing jobs until new volunteers join again.

###  2.3. Pando Design Goals

Overall, our design goals for Pando can be summarized as follows:

  * •

Clear Programming Model: Base the system on a programming model that is clear
and guides a correct implementation;

  * •

Easy Deployment: Make the system easy to deploy, both for the project owner
and the volunteers;

  * •

Usage of Existing Commodity Hardware: Use existing hardware including
workstations, laptops, tablets and mobile phones that individuals, businesses,
and universities already possess;

  * •

Scalability: Allow connecting at least a thousand volunteers;

  * •

Elasticity: Make the volunteer nodes available quickly;

  * •

Performance: Show a linear improvement in throughput compared to a single
processor;

  * •

Fault-tolerance: Tolerate individual nodes that suddenly disconnect or stop
answering.

###  2.4. Paper Organization

In the rest of this paper, we first present the core computation model
(Section 3) and a high-level view of the different components of the system
(Section 4). We then discuss how we adapted the fat-tree overlay to the
context of web technologies (Section 5). We discuss some implementation issues
and other design possibilities (Section 6). To illustrate a use case, we
explain how to provide JavaScript modules that are compatible with the tool
and show how an existing MATLAB-to-JavaScript compiler was adapted to target
Pando (Section 7). We present a performance evaluation of the tool and show it
scales to a thousand volunteers (Section 8). We present our work in the
context of other current and past initiatives (Section 9). Finally, we
summarize the paper in the conclusion and suggest future work to improve upon
our results (Section 10).

##  3\. Core Computation Model: A Stream of Jobs

The problems that are common in volunteer computing usually correspond to a
set of unordered independent jobs. The set may be finite or infinite. We
address a slightly more general version by processing a set of ordered but
independent jobs, also finite or infinite. It makes the problem correspond to
the intuitive behavior of Unix pipelines of commands while also supporting the
unordered case trivially.

We define the core computation model as a set of jobs that is streamed to a
processor that is free to process them in any order but must output the
results in the same order as their corresponding inputs. Each job has a
different input value $x$ but the same function $f$ is applied on each to
obtain a result $f(x)$ (Figure 1). The input $x$ may be a complex object to
pass multiple arguments and this object may include functions, therefore
enabling some jobs to be processed differently than others. In case big data
needs to be sent to volunteers, the compressed serialized data may be directly
embedded in the input or a reference (or url) to a different web service may
be stored. The processing function, while executing on a volunteer, is
responsible for recovering the data either from the compressed representation
or through a different protocol.

Figure 1. Visual Representation of the Streaming Processor

The processor reads input values lazily (pulls values) when its computing
resources become available. This provides flow-control and enables working
with infinite streams.

The processor may actually coordinate computation nodes on different machines,
some of which may fail by crashing suddenly or disconnecting. However, we
assume no node ever executes a different function $f$ than what was provided
or produces a result different from the application of $f(x)$. Even in the
presence of nodes that may fail by suddenly disconnecting, the processor
guarantees that once an input $x$ has been read, if it has active computing
nodes it will eventually provide $f(x)$.

In the next sections, we show how to implement such a processor.

##  4\. Pando’s Design

In this section we provide an overview of how the system is decomposed into
modules and how these modules are connected to leverage volunteer’s computing
power. These are represented graphically in Figure 2.

Figure 2. Overview of Pando’s Components

Our system executes across multiple processes on multiple machines, both on
the same local area network and across the Internet. Each of these processes
is shown as a dashed box.

The top left box represents the process of the Client command-line tool. The
top right box represents an optional Public Server, which is used in the
figure. Both the Client and the Public Server can run the Pando-Server module,
which provides the volunteer code through an HTTP server and provides the
initial connection to bootstrap the rest of the system. The Public Server is
used to relay connection information when direct connectivity to the Client is
not possible.

At the bottom of the figure are the processor, coordinator, and candidate
processes. They all represent different states of a volunteer node. The
processors perform the actual computations. The coordinator dispatches inputs
as well as retrieves and reorders results. The candidate is a volunteer that
is requesting to join the system.

The client and all the volunteers form a fat tree (Section 5) for efficient
data communication with a limited number of connections between nodes.
Together, the client and all coordinators replace the role of a coordination
server in existing volunteer computing platforms.

On starting, new volunteers request a web page from the Pando-Server. They
then open a bootstrap connection, send a request for joining, and wait for the
Client or any of its children to answer. If the request is accepted, a control
stream is opened to an existing node, which becomes the candidate’s parent
node and the bootstrap connection is closed. The candidate becomes a processor
and waits for data inputs. Otherwise, the candidate is rejected and may try to
connect again later. As more volunteers join, some of the processors become
coordinators of the newer volunteer children. They manage the distribution of
input values and the retrieval and the reordering of results of their children
processors. If all its children disconnect, a coordinator becomes a processor
again.

Once the control stream to a parent node is connected it is first used to
connect a second bi-directional data stream. Once opened, the data stream is
used for dispatching input values and transmitting the results. The control
stream also continues to be used for sending periodic status updates towards
the root. The updates are used by the client and coordinator nodes in the tree
for adapting their behavior when the tree changes.

The bootstrapping connections are made with WebSockets (websocket, ). It is a
reliable in-order protocol with flow-control similar to TCP/IP. It was
introduced so servers could push notifications to clients without requiring
clients to periodically ask the server for a status update through a regular
HTTP request. The connections between volunteers are made with WebRTC (webrtc-
draft, ). WebRTC provides a similar data protocol as WebSockets but enables
processes to establish a direct connection between one another, without the
need for a server to relay the data. In order to establish that connection
though, WebRTC peers need to exchange connectivity information and decide how
to connect. This is called signaling and requires an existing connectivity
scheme, so this is why the WebSockets and Public Server were introduced in the
first place. They are only used to establish the WebRTC connection.

Our stream abstractions are shown in Figure 2 as modules within the different
processes. The core synchronization is performed by the pull-lendStream
abstraction (pull-lendstream-implementation, ), which creates multiple
concurrent bi-directional sub-streams, one for each child. A sub-stream is a
stream that continuously borrows values from its source stream and return
results. It carries only a subset of all values from its source stream. The
sub-streams are dynamically created as volunteers join. The flow rate of
values within a sub-stream is determined by how fast a volunteer obtains
values, processes them, and returns the result. The system as a whole
therefore performs load-balancing automatically because the faster volunteers
will process more values. The flow rate of the main uni-directional stream,
which carries the input and outputs of the Client process in the figure, is
determined by the combined flow-rate of all sub-streams. It increases with the
number of volunteers and is ultimately limited by the CPU utilization and
bandwidth available on the Client process.

The pull-lendStream module is itself implemented using the pull-lend module
(not shown in the figure) (pull-lend-implementation, ). It lends values
individually and reorders results to output the corresponding outputs in the
same order as the inputs. In addition, it provides fault-tolerance by
remembering which values have been lent to whom. If a borrower fails with an
error, its value will be lent transparently to the next borrower. The memory
utilization is therefore proportional to the number of concurrently borrowed
values.

Most of the streams, both the main uni-directional stream and bi-directional
sub-streams, are demand-driven. However, the WebRTC and WebSocket streams are
exceptions. Although both use an underlying protocol that performs flow-
control to transport data, and therefore the rate at which data is
transmitted, flow-control is not exposed to programmers. Moreover, there is no
signaling that enables the receiving end of the channel to initiate and drive
the data transmission. So they actually behave as producer-driven streams
although they are compatible with the demand-driven stream interface through
compatibility libraries. It is problematic for coordinators and processors
exchanging data with WebRTC. Without any limitation mechanism, a single data
connection would drain all the values from the main stream.

We therefore use the pull-limit module (pull-limit-implementation, ) to bound
the number of values borrowed by volunteers. Once the borrowing limit has been
reached, pull-limit will delay borrowing a value until at least one result has
been returned. In addition, when a volunteer fails, the limit bounds the
number of values that need to be redistributed to other volunteers. The
optimal limit to use needs to be tuned empirically to balance memory
utilization and the throughput of the system.

##  5\. Tree Overlay

An overlay network is a logical way of organizing nodes that are distributed
on the Internet, potentially distinct from their physical connection(s). In a
fat-tree overlay (Leiserson85, ), nodes are arranged in a spanning tree and
the data traffic between a node and its parent is the sum of the traffic
between itself and all its children. It is simple, easy to implement, and
efficient. However, it requires that the nodes near the root of the tree have
enough bandwidth available to handle the necessary traffic of the network.
Moreover, the reliability of a sub-tree is determined by the reliability of
its root. These two factors determine the practical scale that can be reached.

This overlay (webrtc-tree-overlay, ) enables the system to scale the number of
volunteers that can participate by enabling plenty of data to be exchanged
with a limited number of concurrently active connections. During the
implementation we reached the limitations of the current WebRTC libraries for
Node.js quickly, as we determined that beyond 70 connections to the Client,
additional connections would slow down the overall throughput. We found out
that a performance bug in the libraries available made the management of
connections expensive in CPU time. Using a fat tree, we were able to sidestep
that limitation and were able to go from about 70 browser tabs to a thousand,
effectively increasing the number of usable CPUs by more than an order of
magnitude. We give here the key ideas that we used with the design goal(s)
that they served (in italic).

###  5.1. Balanced and Deterministic Delegation of Join Requests (Goals:
Scalability, Elasticity, and Performance)

To establish a WebRTC connection, each party has to exchange signals with the
other party to determine how to connect through the Network-Address
Translation (NAT) schemes used by routers. The ICE signaling protocol (ice-
draft, ) used by WebRTC has a trickle mode in which possible connection
endpoints are sent as they are discovered (rather than waiting for all
endpoints to be identified), which reduces the latency to open the connection.
The trickle mode generates multiple signal messages that need to be routed
through the tree to exactly the same destination node. Moreover, to minimize
the latency throughout the tree and make it grow quickly, the depth of nodes
should be minimized by making the number of children in sibling sub-trees
similar.

To solve both problems, we use a deterministic scheme to distribute join
requests uniformly between all children. To join the tree, a new candidate
volunteer opens a WebSocket channel to the bootstrap server and obtains a
random identifier. It then sends multiple join requests that each contain its
identifier, the origin, and a WebRTC ICE signal. The requests are all sent by
the Pando-Server to the root (Client) node. From there, each node has two
choices. If it has less than the maximum number of allowed children,
$maxDegree$, it creates a candidate connection and answers the requests by
replying to the originator through the Pando-Server with its own signals,
becoming the destination. Otherwise it delegates the requests to one of its
children.

The delegate child is chosen by xoring the origin identifier with the node’s
identifier, taking the hash of the result, and computing the numerical index
of the child in the children list by taking the hash modulo $maxDegree$:

$childIndex=hash(request.origin\wedge node.id)\%maxDegree$

If the index corresponds to a candidate that is not already connected, the
requests are stored until it is connected. The choice of a good hash function
ensures the requests are uniformly distributed between the children. The
determinism of the scheme ensures no coordination amongst nodes is necessary
and the decision of delegation can be made locally by each node with no
information about the global state of the tree. It also ensures all requests
are routed along the same path in the tree as long as no node along the path
fails in the meantime.

###  5.2. Handling Faults (Goal: Fault-tolerance)

Here we briefly explain how the overlay recovers from the following faults. In
all cases, after a fault occurred a node tries to reconnect through the
bootstrap server.

####  5.2.1. Connectivity Issues

A new volunteer candidate may fail to establish a connection with an existing
node after sending a join request. A candidate is purged from the children
list if it fails to establish a connection before a timeout, by default 60
seconds after the first join request has been received.

####  5.2.2. Control and Data Channel Disconnection

A node may suddenly disconnect or become unreachable because of a network
partition or because too much traffic is going through the same network
routes. The WebRTC standard already provides a failure detection mechanism
through the heartbeat mechanism part of the SCTP transport protocol (sctp, ).
A disconnection is manifested as a ’close’ or ’error’ event from the WebRTC
library we use. It therefore requires no special handling.

If either the control or data channel disconnect both are closed and the child
is purged from the parent list. The disconnected child in turns disconnects
all its children, forcing the entire sub-tree to reconnect through the
standard mechanism.

##  6\. Implementation Issues and Design Choices

We had different options available during the design of the system. In this
section we detail the issues or choices we encountered and how we solved them.
Where appropriate, we refer back to processes and modules of Figure 2.

###  6.1. Execution Environment

The system could be written in any combination of languages that support the
communication protocols. We used JavaScript to implement all modules because
we were more familiar with it and it ran directly in web browsers. Here is a
breakdown of the execution environments used by various processes.

Both the Client and the Public Server are executing on Node.js. As shown on
Figure 2 the Pando-Server module executes within the same Node.js process as
the Client unless, it is running in a separate Public Server.

The volunteer code, that performs the Coordinator or Processor roles, executes
in a browser or on Node.js. Volunteers joining from a web browser only execute
the volunteer code, while the Client executes both the volunteer code and the
Pando-Server code within the same Node.js process.

###  6.2. Number of Concurrent Clients

The current version of Pando supports a single Client at a time executing a
single function. We think spanning a different overlay for each Client is
simpler as it removes the need for account management. If multiple functions
that require volunteer computing need to be pipelined, each require a
different Client started on a different port and each will spawn its own
independent overlay network. This restriction is due to the way the tool is
currently implemented. However, it should be possible to handle multiple
stages of a Unix processing pipeline with the same overall approach by
decoupling the Unix interface from the Client.

###  6.3. Connectivity Across Local Networks Hidden Behind Network-Address
Translation Schemes

In most cases, the direct connectivity to the Client process is not possible
because many networks perform Network-Address Translation (NAT) which
basically hides the IP address of a machine within a local area network (LAN).
Connecting to a machine behind a NAT is complicated. It may require a change
of configuration of the LAN router to expose the machine publicly. Requiring
such steps from users would have made the tool much less usable. Instead, we
chose to optionally expose a public interface through a Public Server (top
right box) when the client starts and rely on WebRTC (webrtc-draft, ) for NAT
traversal. Making the Public Server optional makes the basic case of deploying
Pando on a local network simple, with volunteers connecting directly with the
url provided. However, if the user wants to enable volunteers outside of the
local network to connect and the machine on which the Client is started does
not have a public IP address, the Pando-Server should be started on a machine
with a public IP such as a Heroku instance. Upon connection, the WebRTC
protocol will try to find a way of connecting the volunteers and the Client
through the NAT of the local network555The connection may still fail if the
Client is behind a firewall or the router blocks some protocols or ports..

###  6.4. Multiplexing Control and Data Messages

When designing the communication topology, we considered multiplexing the data
and control messages in a single stream. However that approach is fraught with
subtle issues. For example, data messages may delay the transmission of
control messages if flow control is not implemented correctly (multiplexing-
considerations, ). For the simplicity of the protocol implementation we kept
the two channels separate.

###  6.5. Debugging Connectivity Issues during Development

During development, we optionally use the Pando-Server to monitor all the
nodes through an additional persistent WebSocket connection, which helps
diagnose connectivity bugs in the tree overlay.

##  7\. Writing Functions for Pando

In this section we explain how to build modules in JavaScript that are
compatible with Pando. Our API follows the Node.js conventions for defining
modules, which should be familiar to any experienced JavaScript developer.
Modules can depend on any package of the node package manager (npm) ecosystem.
Our commandline tool automatically bundles all dependencies using Browserify
(browserify, ). The resulting bundle is ready to run inside web browsers.

We show here the conventions expected by Pando. To show these conventions make
it easy to adapt existing compilers that target JavaScript, we adapted an
existing MATLAB to JavaScript compiler to produce Pando-compatible code
(matjuice-repository, ). We then show on a concrete example how the compiler
produces compatible code.

###  7.1. Conventions

A Pando-compatible JavaScript module has the following structure:

    var module.exports[’/pando/1.0.0’] = \
        function (x, cb) {
        // perform computation

        if (error) {
            cb(error)
        } else {
            cb(null, result)
        }
    }

The module.exports is the object exported by the JavaScript module, following
the CommonJS Module Specification followed by Node.js (commonjs-module, ). The
’/pando/1.0.0’ property specifies the first version of the Pando protocol for
processing functions. That protocol expects a function with two parameters: a
value (x) and a callback (cb) as arguments. When called, x will have the
currently processing string value666It may represent an arbitrary object in
JSON notation. and cb will be used by the function to return the result. The
explicit usage of a callback enables the function to use asynchronous
libraries. The callback itself expects two arguments: an error flag and a
result. If the function could not complete its job, an error must be returned
through the callback. Otherwise, the error flag must use a falsy value,
usually null by convention.

###  7.2. MATLAB Compilation Example: Collatz Conjecture

The Collatz conjecture is one of the many BOINC projects (boinc-collatz, ). We
use a simple MATLAB implementation of the conjecture to illustrate how
compilers from other languages may be adapted to produce JavaScript code
compatible with Pando.

    function y = collatz(n)
        y = 0;
        while n ~= 1
            if mod(n, 2) == 0
                n = n / 2;
            else
                n = 3*n + 1;
            end
            y = y+1;
        end
    end

It counts the number of steps that are required to obtain 1 from a starting
integer n and performing either a division by 2 if n is even or a
multiplication by 3 and addition by 1 otherwise.

We adapted the Matjuice compiler (Foley-Bourgon:2016, ; matjuice-repository, )
to produce a Pando-compatible JavaScript module. Matjuice produces a self-
contained JavaScript file that corresponds to the content of a directory of
Matlab functions (saved in files), given the name of the main function of the
program. We changed the output of the compiler so that it adds extra lines
following our conventions. The same code compiled to JavaScript becomes:

    // Prelude with various libraries required
    // by Matjuice code

    // Matjuice Compiled Collatz
    // (Manually simplified output to remove
    // spurious temporaries)
    function collatz_S(n) {
        var y = 0;
        while (n !== 1) {
            if (mc_mod_SS(n, 2) === 0) {
                n = n / 2;
            } else {
                n = 3 * n + 1;
            }
            y = y + 1;
        }
        return y;
    }

    // Pando convention
    module.exports[’/pando/1.0.0’] = \
    function (x, cb) {
      try {
        var r = collatz_S(x)
        cb(null, r)
      } catch (e) {
        cb(e)
      }
    }

We only had to add the last part to follow the Pando convention in which the
compiled function is called within a try/catch. This example shows that it is
straightforward to adapt existing compilers that target JavaScript to produce
Pando-compatible code.

The previous implementation is a great simple example but lacks practical
interest. The single CPU execution of a single execution is much faster than
the latency of sending it to a volunteer for any integer representable using
JavaScript’s numbers representation. So to make it closer to the actual
Collatz implementations, we adapted the resulting JavaScript code to use
arbitrary large integers (bignums) with minimal effort using the existing
bignumber.js library (bignumber.js, ). The example is available in the
examples of the Pando Hanbook (pando-handbook, ). We show the speedup that can
be obtained on this example by using Pando in Section 8.3.

##  8\. Evaluation

In the previous sections, we have shown how our web-based approach makes the
development and deployment of volunteer computing projects easy and
accessible. In this section, we now evaluate the approach with a concrete
implementation in the form of the Pando command-line tool.

Our goal with the evaluation is to show that a web-based approach is now
viable because (1) the web technologies have an overhead that is small enough
and (2) that the practical scale and performance obtained correspond to what
small- and medium-business and organizations as well as academic departments
have access to in terms of existing hardware, which opens the volunteer
computing approach to new users.

To do so, we measure the performance in terms of overall throughput for the
task because that corresponds to the experience of an end-user of the
platform. When users have to decide whether they should use the platform to
accelerate their computation, it is the overall speedup that they get compared
to a single processor execution that will influence their choice of a
platform. Moreover, a linear improvement in throughput means that users can
expect that the more machines that contribute to the jobs, the faster they
will be completed.

The overall throughput on a given application depends (1) on application-
specific characteristics, such as the time it takes to complete an individual
job, the memory usage, and the amount of data it needs to transfer as well as
(2) the hardware characteristics of the machine on which volunteers run such
as the CPU power, main-memory available, and bandwidth available. We isolate
and quantify the baseline overhead that is specific to the platform in a way
that does not depend on the particular application and hardware used.

To do so we first performed an experiment with a quick, simple task which
requires very little network bandwidth: squaring a stream of numbers. The
results are easy to verify to ensure the correctness of the implementation. We
fixed the computation time of the task by returning the result after a
predefined timeout, so that its ”computation time” is independent of the
actual hardware on which it is run. We used a somewhat arbitrary timeout of
one second to represent a job whose computation time takes significantly
longer than its transfer time on the network (otherwise it might be simpler
and faster to run locally). In practice, as long as the data transfer time is
significantly smaller than the computation time, independent jobs may always
be be combined in bigger tasks to increase their duration and increase the
ratio of computation to transfer time 777We did it for the Collatz example in
Section 8.3.. Moreover, by simulating the computation time with a timeout,
multiple volunteers can run on a few hardware cores.

We then measure the throughput obtained with a varying number of volunteers
and compare it to the throughput that would be obtained if the platform had no
overhead (the perfect throughput) to obtain a speedup. The experiment and
results are described in Section 8.2.

Then, we verify that the expectations obtained with the previous experiment
correspond to what is really obtained in practice on a real volunteer
computing problem, the Collatz Conjecture, in Section 8.3.

###  8.1. Testbed Characteristics

We used the following software for our tests: Node.js (7.8.0), Linux
(3.16.0-4-amd64), and Debian (3.16.39-1+deb8u1, 2017-02-22). Browser tabs that
represent volunteers are deployed using Chromium (57.0.2987.98) in headless
mode with the remote debugging port activated (\--headless --remote-debugging-
port=9222). The hardware nodes were provided by Grid5000 (grid5000, ) from the
Grenoble site. Depending on the cluster usage at the time of the tests, the
nodes were a combination of the Edel and Genepi configurations listed in Table
1. We chose the Grid5000 platform for these tests because it was freely
available to us, and it allowed us to scale up to 1000 volunteers (browser
tabs) in a controlled manner running on 10 different machines for a total of
80 cores. The scripts necessary for deploying the required software are
available in the Pando Handbook on GitHub (pando-handbook, ).

Cluster Name | Edel | Genepi
---|---|---
Model | Bullx Blade B500 | Bull R422-E1
Nodes Number | 72 | 34
CPU |  Intel Xeon E55202.27 GHz (8 cores8882 CPUs * 4 Cores/CPU) |  Intel Xeon E5420 QC2.5 GHz (8 cores999Idem)
Memory | 24 GB | 8 GB
Network |  | 1 Gigabit Ethernet
---
1 cards InfiniBand 40G QDR)
| 1 Gigabit Ethernet
---
34 cards InfiniBand 20G DDR)
Table 1. Grid5000 Hardware Configuration.

###  8.2. How does the speedup grow with the number of processors?

For our baseline tests we used a simple computation that is easy to check for
correctness. The task is simply squaring a stream of numbers, starting at 0.
This was accomplished using the following Unix processing pipeline:

        count | pando square [options...] |
        expect-square | measure-throughput

The first process, count, outputs the numbers from 0 to Infinity on the
standard output, one per line . The second process, pando, applies a
JavaScript square function on numbers it receives from its standard input
(square: x -> x * x) and outputs the result on the standard output. The third
process expect-square outputs the input it received but only if it is the
corresponding expected value of the series $0^{2},1^{2},2^{2},...$. If it
receives a different number than the one expected it stops and outputs an
error. The last process measures the throughput at periodic intervals and for
the overall pipeline execution. We used the pv Unix tool in line-oriented mode
(-l option) for that purpose.

We show the speedups vary linearly with the number of tabs that are connected
to the system (Figure 3) when using between 5-1000 tabs. Here is how we
obtained the figure.

We fixed the processing time to complete a job returning the square of the
input value after one second using a timeout. We then varied the number of
browser tabs that are opened, from 5 tabs to 1000 tabs. The first measurements
were made by using 5 nodes and by varying the number of tabs from 1 tab/node
to 100 tabs/node. We did a final measurement with 10 nodes with 100 tabs/node
to obtain 1000 tabs.

We chose a number of jobs to perform for each data point so that the overall
execution takes about a minute for each data point. It makes it convenient to
test and keeps the proportion of time it takes for the overlay to be
established (5-10 seconds) roughly constant compared to the overall execution
time.

In order to compare the different measurements, which have a different number
of jobs to perform, we used the throughput measured for the entire duration of
the pipeline. Our measurements therefore include the time it takes for
volunteers to connect and the deployment of the overlay. This is
representative of the experience an end-user would have.

Finally, the overlay was configured to have a maximum of 10 children per node
(maxDegree) and the pull-limit modules were set to limit the number of values
to maxDegree * nbLeafNodes.

Figure 3.  Linear speedup between 5-1000 browser tabs on the squaring example.
Figure 4.  Speedup obtained in parallelizing the Collatz conjecture by using
1-64 hardware cores (on 1-8 nodes). The y axis is divided by 175 so it can
also be read directly as a speedup (because 1 core processes 175 values/sec).

In Figure 3, we show the individual experiment measurements with dots. For
each number of tabs, we show ten successful measurements and discard cases
where a failure prevented the successful completion of the experiment. This
may happen because the Grid5000 deployment script failed to secure the nodes,
because the browser failed to start all the tabs and successfully connect, or
there is a stall in the pipeline.

We averaged the individual measurements to obtain the average throughput which
shows a linear trend. It is roughly 50% of the perfect throughput that would
be obtained if all volunteers were constantly used for processing jobs and the
system had no overhead.

In addition, we can see in the average trend that the throughput is getting
further away from the perfect throughput as the number of tabs grows. We also
see clear inflexion points when a new level of the tree is added ($>10$ and
$>100$), which adds latency. Moreover, right after these inflexion points is
where the overhead for coordination is the highest and diminish until the next
inflexion point. This is explained by the diminishing proportion of the number
of coordination nodes.

We have not optimized the number of children per node or the limit used by
pull-limit. We expect higher throughputs for the same number of tabs to be
possible.

###  8.3. Do the Speedups Translate to a Real Application?

We show here the speedup gains obtained in practice using the system. We
checked the Collatz conjecture (boinc-collatz, ) starting with the number
3,179,389,980,591,125,407,167, which produces a sequence of 2760 steps, the
longest known so far (longest-collatz, ). Each individual node tests a range
of 175 numbers to find the longest sequence amongst them, which takes about 1
second on a core on Grid5000. We parallelized the task by creating a stream of
consecutive ranges, process them using Pando, and measured the overall
throughput the same way as in the previous section. The equivalent abstract
pipeline is:

        count-ranges | pando collatz [options...] |
        measure-throughput

We progressively increased the number of cores used on Grid5000. We scaled up
to 64 cores (8 nodes * 8 cores/node) to use at least a full level of
coordinator nodes in our tree and enough values to show the overall growing
trend.101010Given the results in the previous section we could have
confidently scaled from 64 to a thousand cores. However we didn’t want to
waste Grid5000 resources scaling up to 1000 on this problem, which is very
similar. However, we can perform the complete experiment for the final version
if the reviewers would like to see those results. We show the speedup obtained
compared to a single core in Figure 4.

We see a similar linear speedup on that example compared to the previous
experiment. We see also a similar inflexion point when going from 8 cores to
16 cores, which corresponds to another level being added in the overlay tree.
Our example therefore behaves similarly as our simple example used in the
previous section, confirming that we can indeed abstract the computation task
to measure the performance of the overlay and stream abstractions.

Our JavaScript implementation of the Collatz conjecture is an obvious
implementation, and unlikely to be as fast as the implementation used on the
BOINC platform (boinc-collatz, ). Nonetheless, even in its current form it
shows scalable number crunching.

The results in this section provided fully working examples of our system and
measured the performance of our stream abstractions and fat-tree overlay in a
repeatable and controlled manner on Grid5000. Measurements on a simple example
and an actual volunteer computing project showed that our implementation
provides a linear speedup in throughput when using up to 1000 browser tabs.
This level of performance makes the system useful to leverage idle computers
at scales that range from all end-user devices in a single home to all
computers available in a typical university department or small-to-medium
sized businesses.

##  9\. Related Work

The first publication on using idle computing resources in end-user machines
has been made almost three decades ago by Litzkow et al. (litzkow1988condor,
). The system was designed to transparently use idle workstations for
performing jobs. As a successor, BOINC (boinc, ) is maybe the most well-known
software plaform used to build volunteer computing infrastructures using a
similar approach. It has been used in many different projects, from the search
for extraterrestrial intelligence (SETI@Home) to applications with an
important societal impact (World Community Grid (WCG, ; BBD+09, )). In
February 2016, 166 petaFLOPS were made available for these projects, compared
to 93 petaFLOPS for the most powerful supercomputer (Sunway TaihuLight).

Fabisiak and Danilecki (fabisiak2017browser, ) have surveyed more than 40
articles on browser-based voluntary computing published over two decades.
Notably, in the 90s and early 2000s, work in volunteer computing was done
using Java and Web Applets (Sarmenta1998, ; fedak:tel-01158462, ;
DurraniShamsi14, ; Venkataraman2016, ), technologies that have now been almost
completely abandoned and replaced with the modern web standards. Issues of
sandboxing, portability of the code, and direct connectivity between volunteer
nodes are now all handled by browser implementations and web standards. In
2007, a second generation of projects started using JavaScript for computation
(boldrin2007distributed, ; klein2007unwitting, ; konishi2007rabc, ) albeit at
the time JavaScript was orders of magnitude slower than Java. In 2010, the
speed of JavaScript in browsers was such that it could now compete with Java
on its own, and a third generation of projects followed
(martinez2014implementing, ; martinez2015capataz, ; meeds2015mlitb, ;
ryza2010mrjs, ; pan2015gray, ). All the previous projects were based on a
server-client architecture in which all the workers would communicate directly
with the server to obtain tasks to perform and return results. Starting with
browserCloud.js (dias2015browsercloud, ) and Pando, we are seeing a 4th
generation of projects that leverages WebRTC-based overlays to remove the
necessity of a master server. Compared to previous approaches, ours
drastically simplifies the implementation of volunteer computing platforms
because it is based on a streaming paradigm and combines with existing web
services. We notably avoid account management and do not require a database to
manage a bag of tasks. By using a connection-oriented protocol such as WebRTC
(or WebSockets (websocket, )), we get the detection of crash-stop failures
”for free” because those mature protocols already provide a heartbeat
mechanism to detect failures (other approaches had to implement it on top of
an HTTP protocol). By using a functional interface to create jobs rather than
a job description language (danilecki2017job, ) or an object-oriented
protocol, we simplified the creation of jobs for usage as a compiler target.

Compared to browserCloud.js (dias2015browsercloud, ), by using a pull-driven
streaming model, we avoid issues of load-balancing that arise when the Client
initiates remote procedure calls on Volunteers (workers). We also create a
specific overlay for a single stream of jobs which couples the joining of the
overlay with the participation in a specific stream. Therefore volunteers are
not peers, they cannot submit jobs once they have joined a stream. To submit a
stream of jobs, they have to span a different overlay. We also rely on
existing social medias to publish work to be performed, benefiting from their
reliability, popularity, and the good reputation of public accounts.

The fat-tree topology has been studied in the networking field to efficiently
create physical connections between nodes (Leiserson85, ; ruft-fat-tree, ;
adaptive-vs-deterministic-routing, ). Variations of a tree topology have been
used to design peer-to-peer topologies for different applications such as
multicast transmission (Birrer2004, ; Kostic:2003, ; zigzag, ; Banerjee:2006,
) of large files or real-time multimedia streaming.

Many content delivery and streaming platforms using WebRTC have been
envisioned (Nurminen2013, ; Werner2013, ) and built (Vogt2013, ; hive.js, ).
Other uses for WebRTC include user-centric data replication with conflict-free
replicated data types (vanderLinde:2017, ) and a virtual reality peer-to-peer
environment (Hu:2017, ).

Pando uses the excellent simple-websocket (simple-websocket-repo, ) and
simple-peer (simple-peer-repo, ) libraries from WebTorrent (webtorrent, ),
respectively providing simple JavaScript APIs for WebSocket and WebRTC.

Finally, when comparing the volunteer computing approach to other parallelism
approaches based on leveraging multi-cores, GPUs, or clusters, it is
interesting to notice that in a volunteer computing platform, the number of
CPUs is not fixed nor bounded (for all practical purposes). It implies that
when designing a system with that approach, it is more important to scale
first to as many nodes as possible and then optimize individual node
performance later. Since nodes do not incur costs (to the client of the
platform) and would otherwise be idle, even a small but positive contribution
by each node is a net gain in the overall throughput. Moreover, our volunteer
computing approach can be used in combination with other parallelism
approaches by using their techniques to optimize the performance of a single
volunteer.

##  10\. Conclusion and Future Work

In this paper, we have presented a new approach for building volunteer
computing platforms for the web using pull-stream abstractions and a WebRTC
fat-tree overlay. This approach lowers the effort in participating in and
launching volunteer computing projects by leveraging the convenience and
ubiquity of the web, removes the cost of dedicated hardware by organizing
volunteers in a fat-tree overlay so they participate in coordinating the work
to be performed, and drastically simplifies the implementation compared to
other browser-based volunteer computing platforms.

We have shown how to connect volunteers using a fat-tree overlay that scales
quickly using a deterministic scheme to route WebRTC signaling messages
through the tree.

We provide modular open source and documented implementations of stream
abstractions (pull-lend-implementation, ; pull-lendstream-implementation, ;
pull-limit-implementation, ) and fat-tree overlay (webrtc-tree-overlay, ) for
easy and quick individual reuse in other projects through the node package
manager (npm). We also built an open source command-line tool (pando-
repository, ) that uses those abstractions to integrate volunteer computing
with general Unix processing pipelines.

We adapted an existing MATLAB-to-JavaScript compiler to produce compatible
code showing how other languages could leverage volunteer computing.

We measured the performance of our implementations and shown them to scale
linearly up to a thousand browser tabs making the approach widely useful in
practice from single users with multiple devices up to entire university
departments with plenty of idle desktop computers. We provide all scripts and
procedues necessary to replicate our experiments (pando-handbook, ).

All these results provide a nice foundation for further performance tuning
both of the stream abstractions, the fat-tree overlay, and the processing
function performance. Moreover, volunteer computing using web technologies is
an exciting approach to parallelism that would benefit from more study.

##  11\. Acknowledgements

This material is based upon work supported by the National Science and
Engineering Research Council (NSERC) of Canada, Fond de Recherche du Quebec –
Nature et Technologies (FRQNT). Any opinions, findings, and conclusions or
recommendations expressed in this material are those of the author and do not
necessarily reflect the views of NSERC or FRQNT.

Experiments presented in this paper were carried out using the Grid’5000
testbed, supported by a scientific interest group hosted by Inria and
including CNRS, RENATER and several Universities as well as other
organizations (see https://www.grid5000.fr).

We would like to thank João Coelho Garcia and the anonymous reviewers for
suggestions that helped improve the paper.

## References

  * [1] World Community Grid.  http://www.worldcommunitygrid.org, 2009.  [Online; accessed 17-April-2017].
  * [2] The WebSocket Protocol.  https://tools.ietf.org/html/rfc6455, 2011.  [Online; accessed 13-February-2017].
  * [3] CommonJS Module Specification 1.1.1.  http://wiki.commonjs.org/wiki/Modules/1.1.1, 2014.  [Online; accessed 14-February-2017].
  * [4] bignumber.js.  https://www.npmjs.com/package/bignumber.js, 2017.  [Online; accessed 15-April-2017].
  * [5] Boinc.  https://boinc.berkeley.edu, 2017.  [Online; accessed 05-April-2017].
  * [6] BoincIntro.  https://boinc.berkeley.edu/trac/wiki/BoincIntro, 2017.  [Online; accessed 13-February-2017].
  * [7] Browserify.  http://browserify.org/, 2017.  [Online; accessed 15-April-2017].
  * [8] distributed.net.  http://www.distributed.net/, 2017.  [Online; accessed 13-February-2017].
  * [9] Folding@Home.  https://folding.stanford.edu/, 2017.  [Online; accessed 13-February-2017].
  * [10] Internet World Stats.  http://www.internetworldstats.com/stats.htm, 2017.  [Online; accessed 13-February-2017].
  * [11] Longest Collatz Sequence.  https://boinc.thesonntags.com/collatz/highest_steps.php, 2017.  [Online; accessed 16-April-2017].
  * [12] Matjuice Repository.  https://github.com/sable/matjuice, 2017.  [Online; accessed 13-February-2017].
  * [13] Pando - I Spread.  https://www.fs.usda.gov/detail/fishlake/home/?cid=STELPRDB5393641, 2017\.  [Online; accessed 27-January-2017].
  * [14] Pando Handbook.  https://github.com/elavoie/pando-handbook, 2017.  [Online; accessed 24-July-2017].
  * [15] Pando Repository.  https://github.com/elavoie/pando-computing, 2017.  [Online; accessed 15-April-2017].
  * [16] Pando Server.  https://github.com/elavoie/pando-server and https://www.npmjs.com/package/pando-server, 2017.  [Online; accessed 25-July-2017].
  * [17] Pull-Lend Implementation.  https://github.com/elavoie/pull-lend and https://www.npmjs.com/package/pull-lend, 2017.  [Online; accessed 15-April-2017].
  * [18] Pull-LendStream Implementation.  https://github.com/elavoie/pull-lend-stream and https://www.npmjs.com/package/pull-lend-stream, 2017.  [Online; accessed 15-April-2017].
  * [19] Pull-Limit Implementation.  https://github.com/elavoie/pull-limit and https://www.npmjs.com/package/pull-limit, 2017.  [Online; accessed 15-April-2017].
  * [20] Pull-Stream Module List.  https://pull-stream.github.io/, 2017.  [Online; accessed 25-July-2017].
  * [21] SETI@Home.  http://setiathome.berkeley.edu/, 2017.  [Online; accessed 13-February-2017].
  * [22] Simple-Peer.  https://github.com/feross/simple-peer, 2017.  [Online; accessed 17-April-2017].
  * [23] Stream Control Transmission Protocol.  https://tools.ietf.org/html/rfc4960, 2017.  [Online; accessed 09-April-2017].
  * [24] TCP and heartbeats.  http://250bpm.com/blog:22, 2017.  [Online; accessed 15-April-2017].
  * [25] The Collatz Conjecture.  http://boinc.thesonntags.com/collatz/, 2017.  [Online; accessed 14-February-2017].
  * [26] Trickle ICE: Incremental Provisioning of Candidates for the Interactive Connectivity Establishment (ICE) Protocol.  https://datatracker.ietf.org/doc/html/draft-ietf-ice-trickle, 2017\.  [Online; accessed 09-April-2017].
  * [27] US supercomputer needs more people power.  https://www.natureindex.com/news-blog/us-supercomputer-needs-more-people-power, 2017\.  [Online; accessed 05-April-2017].
  * [28] WebRTC 1.0: Real-time Communication Between Browsers.  https://www.w3.org/TR/webrtc/, 2017.  [Online; accessed 05-April-2017].
  * [29] WebRTC Tree Overlay.  https://github.com/elavoie/webrtc-tree-overlay and https://www.npmjs.com/package/webrtc-tree-overlay, 2017.  [Online; accessed 25-July-2017].
  * [30] WebTorrent.  https://webtorrent.io/, 2017.  [Online; accessed 17-April-2017].
  * [31] Daniel Balouek, Alexandra Carpen Amarie, Ghislain Charrier, Frédéric Desprez, Emmanuel Jeannot, Emmanuel Jeanvoine, Adrien Lèbre, David Margery, Nicolas Niclausse, Lucas Nussbaum, Olivier Richard, Christian Pérez, Flavien Quesnel, Cyril Rohr, and Luc Sarzyniec.  Adding virtualization capabilities to the Grid’5000 testbed.  In IvanI. Ivanov, Marten Sinderen, Frank Leymann, and Tony Shan, editors, Cloud Computing and Services Science, volume 367 of Communications in Computer and Information Science, pages 3–20. Springer International Publishing, 2013.
  * [32] Suman Banerjee, Seungjoon Lee, Bobby Bhattacharjee, and Aravind Srinivasan.  Resilient multicast using overlays.  IEEE/ACM Trans. Netw., 14(2):237–248, April 2006.
  * [33] Viktors Berstis, Raphael Bolze, Frédéric Desprez, and Kevin Reed.  From Dedicated Grid to Volunteer Grid: Large Scale Execution of a Bioinformatics Application.  Journal of Grid Computing, 7(4):463–478, December 2009.
  * [34] Stefan Birrer, Dong Lu, Fabián E. Bustamante, Yi Qiao, and Peter Dinda.  FatNemo: Building a Resilient Multi-source Multicast Fat-Tree.  In Web Content Caching and Distribution: 9th International Workshop, WCW 2004, pages 182–196. Springer Berlin Heidelberg, 2004.
  * [35] Fabio Boldrin, Chiara Taddia, and Gianluca Mazzini.  Distributed computing through web browser.  In Vehicular Technology Conference, 2007. VTC-2007 Fall. 2007 IEEE 66th, pages 2020–2024. IEEE, 2007.
  * [36] Arkadiusz Danilecki, Tomasz Fabisiak, and Maciej Kaszubowski.  Job Description Language for a Browser-Based Computing Platform—A Preliminary Report.  In Advanced Topics in Intelligent Information and Database Systems, pages 443–453. Springer, 2017.
  * [37] David Dias.  browserCloud.js-A federated community cloud served by a P2P overlay network on top of the web platform.  Master’s thesis, Tecnico Lisboa, 2015.
  * [38] Muhammad Nouman Durrani and Jawwad A. Shamso.  Volunteer Computing: Requirements, Challenges, and Solutions.  Journal of Networks and Computer Applications, 39:369–380, July 2014.
  * [39] Tomasz Fabisiak and Arkadiusz Danilecki.  Browser-based harnessing of voluntary computational power.  Foundations of Computing and Decision Sciences, 42(1):3–42, 2017\.
  * [40] Gilles Fedak.  Contributions to Desktop Grid Computing .  Habilitation à diriger des recherches, Ecole Normale Supérieure de Lyon, May 2015.
  * [41] Vincent Foley-Bourgon and Laurie Hendren.  Efficiently implementing the copy semantics of matlab’s arrays in javascript.  In Proceedings of the 12th Symposium on Dynamic Languages, DLS 2016, pages 72–83, New York, NY, USA, 2016. ACM.
  * [42] C. Gomez, F. Gilabert, M. E. Gomez, P. Lopez, and J. Duato.  Deterministic versus Adaptive Routing in Fat-Trees.  In 2007 IEEE International Parallel and Distributed Processing Symposium, pages 1–8, March 2007.
  * [43] Yonghao Hu, Zhaohui Chen, Xiaojun Liu, Fei Huang, and Jinyuan Jia.  WebTorrent Based Fine-grained P2P Transmission of Large-scale WebVR Indoor Scenes.  In Proceedings of the 22Nd International Conference on 3D Web Technology, Web3D ’17, pages 7:1–7:8, New York, NY, USA, 2017. ACM.
  * [44] Alan B. Johnston and Daniel C. Burnett.  WebRTC: APIs and RTCWEB Protocols of the HTML5 Real-Time Web.  Digital Codex LLC, USA, 2012.
  * [45] Faiz Khan, Vincent Foley-Bourgon, Sujay Kathrotia, Erick Lavoie, and Laurie Hendren.  Using JavaScript and WebCL for Numerical Computations: A Comparative Study of Native and Web Technologies.  In Proceedings of the 10th ACM Symposium on Dynamic Languages, DLS ’14, pages 91–102, New York, NY, USA, 2014. ACM.
  * [46] Jon Klein and Lee Spector.  Unwitting distributed genetic programming via asynchronous JavaScript and XML.  In Proceedings of the 9th annual conference on Genetic and evolutionary computation, pages 1628–1635. ACM, 2007.
  * [47] Fumikazu Konishi, Manabu Ishii, Shingo Ohki, Ryo UMESTU, and Akihiko Konagaya.  RABC: A conceptual design of pervasive infrastructure for browser computing based on AJAX technologies.  In Cluster Computing and the Grid, 2007. CCGRID 2007. Seventh IEEE International Symposium on, pages 661–672. IEEE, 2007.
  * [48] Dejan Kostić, Adolfo Rodriguez, Jeannie Albrecht, and Amin Vahdat.  Bullet: High Bandwidth Data Dissemination Using an Overlay Mesh.  In Proceedings of the Nineteenth ACM Symposium on Operating Systems Principles, SOSP ’03, pages 282–297, New York, NY, USA, 2003. ACM.
  * [49] Charles E. Leiserson.  Fat-trees: Universal networks for hardware-efficient supercomputing.  IEEE Transactions on Computers, C-34(10), October 1985.
  * [50] Michael J Litzkow, Miron Livny, and Matt W Mutka.  Condor-a Hunter of Idle Workstations.  In Distributed Computing Systems, 1988., 8th International Conference on, pages 104–111. IEEE, 1988.
  * [51] Gonzalo Martínez and Leonardo Val.  Implementing crossplatform distributed algorithms using standard web technologies.  In Computing Conference (CLEI), 2014 XL Latin American, pages 1–8. IEEE, 2014.
  * [52] Gonzalo J Martınez and Leonardo Val.  Capataz: a framework for distributing algorithms via the World Wide Web.  CLEI Electronic Journal, 18(08), 2015.
  * [53] Edward Meeds, Remco Hendriks, Said Al Faraby, Magiel Bruntink, and Max Welling.  MLitB: machine learning in the browser.  PeerJ Computer Science, 1:e11, 2015.
  * [54] J. K. Nurminen, A. J. R. Meyn, E. Jalonen, Y. Raivio, and R. Garcıa Marrero.  P2P media streaming with HTML5 and WebRTC.  In 2013 IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS), pages 63–64, April 2013.
  * [55] Yao Pan, Jules White, Yu Sun, and Jeff Gray.  Gray computing: an analysis of computing with background JavaScript tasks.  In Proceedings of the 37th International Conference on Software Engineering-Volume 1, pages 167–177. IEEE Press, 2015.
  * [56] C. G. Requena, F. G. Villamón, M. E. G. Requena, P. J. L. Rodríguez, and J. D. Marín.  RUFT: Simplifying the Fat-Tree Topology.  In 2008 14th IEEE International Conference on Parallel and Distributed Systems, pages 153–160, Dec 2008.
  * [57] R. Roverso and M. Högqvist.  Hive.js: Browser-Based Distributed Caching for Adaptive Video Streaming.  In 2014 IEEE International Symposium on Multimedia, pages 143–146, Dec 2014.
  * [58] Sandy Ryza and Tom Wall.  MRJS: A JavaScript MapReduce Framework for Web Browsers.  http://www.cs.brown.edu/courses/csci2950-u/f11/papers/mrjs.pdf, 2010\.  [Online; accessed 10-August-2017].
  * [59] Luis F. G. Sarmenta.  Bayanihan: Web-based volunteer computing using Java.  In Yoshifumi Masunaga, Takuya Katayama, and Michiharu Tsukamoto, editors, Worldwide Computing and Its Applications — WWCA’98: Second International Conference Tsukuba, Japan, March 4–5, 1998 Proceedings, pages 444–461, Berlin, Heidelberg, 1998. Springer Berlin Heidelberg.
  * [60] https://github.com/feross/simple-websocket.  [Online; accessed 17-April-2017].
  * [61] Dominic Tarr.  Pull Streams.  http://dominictarr.com/post/145135293917/history-of-streams, 2016\.  [Online; accessed 7-February-2017].
  * [62] Dominic Tarr.  The history of streams.  http://dominictarr.com/post/145135293917/history-of-streams, 2016\.  [Online; accessed 7-February-2017].
  * [63] D. A. Tran, K. A. Hua, and T. Do.  ZIGZAG: an efficient peer-to-peer scheme for media streaming.  In IEEE INFOCOM 2003. Twenty-second Annual Joint Conference of the IEEE Computer and Communications Societies (IEEE Cat. No.03CH37428), volume 2, pages 1283–1292 vol.2, March 2003.
  * [64] Albert van der Linde, Pedro Fouto, João Leitão, Nuno Preguiça, Santiago Castiñeira, and Annette Bieniusa.  Legion: Enriching Internet Services with Peer-to-Peer Interactions.  In Proceedings of the 26th International Conference on World Wide Web, WWW ’17, pages 283–292, Republic and Canton of Geneva, Switzerland, 2017. International World Wide Web Conferences Steering Committee.
  * [65] Neelanarayanan Venkataraman.  A survey on desktop grid systems-research gap.  In V. Vijayakumar and V. Neelanarayanan, editors, Proceedings of the 3rd International Symposium on Big Data and Cloud Computing Challenges (ISBCC – 16’), pages 183–212. Springer International Publishing, 2016.
  * [66] C. Vogt, M. J. Werner, and T. C. Schmidt.  Leveraging WebRTC for P2P content distribution in web browsers.  In 2013 21st IEEE International Conference on Network Protocols (ICNP), pages 1–2, Oct 2013.
  * [67] M. J. Werner, C. Vogt, and T. C. Schmidt.  Let Our Browsers Socialize: Building User-Centric Content Communities on WebRTC.  In 2014 IEEE 34th International Conference on Distributed Computing Systems Workshops (ICDCSW), pages 37–44, June 2014.