Soutenance de thèse Analyse probabiliste de protocoles de populationpeople.irisa.fr/Yves.Mocquard/presentationTheseYvesMoc... · 2019. 1. 28. · Image : Couverture de l’album

1/50

Soutenance de thèse

Analyse probabiliste deprotocoles de population

Yves MOCQUARD1,Directeur de thèse : Bruno SERICOLA2,

Co-encadrante : Emmanuelle ANCEAUME3

1Équipe Dionysos, Université de Rennes 1 / IRISA2Inria, France

3CNRS / IRISA, France

13 décembre 2018Analyse probabiliste de protocoles de population

2/50

Introduction

Analyse probabiliste de protocoles de population

3/50

Introduction

Structure de la présentation1 Définition des protocoles de population2 Protocoles basés sur la moyenne3 La diffusion de rumeur4 L’horloge globale5 La détection de convergence6 Conclusion


4/50

Le modèle des protocoles de population

Modèle minimaliste de systèmes distribués introduit en 2004 1

1 Chaque agent possède un ensemble fini d’états.2 Les agents n’ont pas d’identité.3 Les agents n’ont pas connaissance du temps.4 Les communications sont occasionnellement possibles

entre agents.

→ Uniformité : tous les agents exécutent le même code.→ Anonymat : les agents n’ont pas d’identité.

1. D. Angluin, J. Aspnes, Z. Diamadi, M. J. Fischer, R. Peralta, "Computationin networks of passively mobile finite-state sensors", PODC 2004


5/50


Un protocole de population est défini par (Σ,Q,Ξ, ι, f , ω), où :Σ est l’ensemble des états d’entrée.Q est l’ensemble des états de travail.Ξ est l’ensemble des états de sortie.ι : Σ → Q est la fonction d’entrée.f : Q × Q → Q × Q est la fonction transition.ω : Q → Ξ est la fonction de sortie.

Σι−→ Q Q × Q f−→ Q × Q Q ω−→ Ξ


6/50


FIGURE – Transition suite à une interaction avec f (x , y) = (x ′, y ′)


7/50

Notations et hypothèses

Une configuration est le vecteur Ct =(

C(1)t , . . . ,C(n)t

)∈ Qn

À chaque instant, une et une seule interaction a lieu entredeux nœuds distinctsLa probabilité que chaque couple de nœuds (i , j) interagisse,est

pi,j =1{i ̸=j}

n(n − 1)


8/50

Protocoles basés sur la moyenne

Protocoles basés sur la moyenne1 avec des entiers

2 avec des réels

Image : Couverture de l’album "Atom Heart Mother" Pink Floyd, 1970.


9/50

Exemple : surveillance de maladies

ExempleDes capteurs identiques sont fixés sur tous les animaux.Les capteurs des animaux malades sont dans l’état A(rouge).Les capteurs des animaux sains sont dans l’état B (bleu).Quand deux animaux sont proches, leurs capteursinteragissent.


10/50


ProblèmeConnaissant le nombre n de capteurs, nous voulons connaîtrela valeur nA du nombre de nœuds (capteurs) dans l’état A, eninterrogeant un seul capteur.


11/50

Solution pour calculer le nombre d’ animaux malades

Algorithme

Ensemble d’entrée Σ = {A,B}Ensemble de travail Q = {0,1, . . . , 3n}Ensemble de sortie Ξ = {0,1, . . . , n}

Fonction d’entrée ι : Σ −→ Q A 7−→ 3nB 7−→ 0

Fonction de transition f : (x , y) 7−→(⌊ x+y

2

⌋,⌈ x+y

2

⌉)Fonction de sortie ωA : x 7−→

⌊ x+13

⌋


12/50

ProblèmeQuel est le nombre d’animaux malades dans le troupeau?


13/50


∑5i=1 C

(i)0 = constante = 30


14/50


Nombre total d’interactions : t = 0


14/50




15/50


Le nombre d’animaux malades dans le troupeau est⌊ x+1

3

⌋= 2


16/50

Calcul avec des interactions aléatoires

Quand les nœuds i et j interagissent, la transition peuts’écrire :(

C(i)t+1,C(j)t+1

)=

(⌊C(i)t + C

(j)t

2

⌋,

⌈C(i)t + C

(j)t

2

⌉)C(k)t+1 = C

(k)t si k ̸= i , j

ℓ = 1n∑n

i=1 C(i)t ne dépend pas du temps

On pose L = (ℓ, ℓ, . . . , ℓ) ∈ Rn


17/50

En combien de temps le protocole converge-t-il ?

Théorème 5.2.12Pour tout δ ∈ ]0,1[, s’il existe une constante K telle que∥C0 − L∥2 ≤ K , alors, pour toutt ≥ n (2 ln K + 2.12 ln n − 6.59 ln δ + 1.88), nous avons

P {∥Ct − L∥∞ ≥ 3/2} ≤ δ

Théorème 5.2.13Pour tout δ ∈ ]0,1[, nous avons, pour toutt ≥ n (5.12 ln n − 6.59 ln δ + 2.58), nous avons

P

{⌊C(i)t + 1

3

⌋= nA, pour tout i = 1, . . . , n

}≥ 1 − δ


18/50

Résultats de simulations

0

20

40

60

80

100

120

140

10 102 103 104 105

Tem

pspa

rallè

lede

conv

erge

nce

Nombre n d’agents

τ(n, δ = 10−3)simulations avec δ = 10−3τ(n, δ = 10−2)simulations avec δ = 10−2τ(n, δ = 10−1)simulations avec δ = 10−1

FIGURE – Temps parallèle de convergence du protocole de comptageen fonction de n avec N = 103


19/50

Protocole basé sur la moyenne

Protocole basé sur la moyenne

1 avec des entiers

2 avec des réelsImage : Couverture de l’album "Atom Heart Mother" Pink Floyd, 1970.


20/50

Protocole basé sur la moyenne avec des réels

Algorithme

Ensemble d’entrée Σ = {A,B}Ensemble de travail Q = [0,1]Ensemble de sortie Ξ = {0,1, . . . , n}

Fonction d’entrée ι : Σ −→ Q A 7−→ 1B 7−→ 0

Fonction de transition f : (x , y) 7−→( x+y

2 ,x+y

2

)Fonction de sortie ωA : x 7−→

⌊nx + 12

⌋


21/50


0

0.2

0.4

0.6

0.8

1

0 5 10 15 20 25 30 35 40Temps parallèle t/n

∥Ct − L∥∞proportion d’agents avec la bonne réponse

FIGURE – Évolution en fonction du temps parallèle de ∥Ct − L∥∞ etde la proportion d’agents ayant une réponse correcte, avec n = 106

et N = 1.


22/50


On approche ∥Ct − L∥∞, avec ∥Ct − L∥2 pour la norme 2 et∥Ct − L∥4 pour la norme 4.

Théorème (utilisant la norme 2)Pour tout δ ∈ ]0,1[ et t ≥ τ ′′, nous avons

P

{⌊nC(i)t + 1/2

⌋= nA, pour tout i = 1, . . . , n

}≥ 1 − δ

τ ′′ = (n − 1)(3 ln n + 4 ln 2 − ln δ)

Théorème 5.1.9 (utilisant la norme 4)Pour tout δ ∈ ]0,1[ et t ≥ τ ′, nous avons

P

{⌊nC(i)t + 1/2

⌋= nA, pour tout i = 1, . . . , n

}≥ 1 − δ

τ ′ =4n(n − 1)

7n − 6(5 ln n + ln(104/3)− ln δ)


23/50


5

10

15

20

25

30

35

40

45

50

10 102 103 104 105

Tem

pspa

rallè

lede

conv

erge

nce

Nombre d’agents n

τ ′′

τ ′

simulations nA = n/2simulations nA = n/4

FIGURE – Temps parallèle de convergence en fonction de n, avecδ = 10−3 et N = 105.


24/50


18

20

22

24

26

28

30

32

34

36

38

10−610−510−410−310−210−1

Tem

pspa

rallè

lede

conv

erge

nce

δ

τ ′′

τ ′

simulations nA = n/2 = 500simulations nA = n/4 = 250

FIGURE – Temps parallèle de convergence en fonction de δ avecn = 1000 et N = 106.


25/50

La diffusion de rumeur

Image : "Scrispin et Scapin" par Honoré Daumier, vers 1864Analyse probabiliste de protocoles de population

26/50

Diffusion de rumeur

C’est un protocole très simple qui peut modéliserla diffusion d’une maladie contagieusela diffusion d’un message dans un système distribuéla diffusion d’une rumeur


27/50

Diffusion de rumeur

1 ⇐⇒ "connaît la rumeur"0 ⇐⇒ "ne connaît pas la rumeur"

Algorithme

Ensemble d’entrée Σ = {0,1}Ensemble de travail Q = {0,1}Ensemble de sortie Ξ = {0,1}Fonction d’entrée : ι = Id{0,1}Fonction de transitionf : {0,1} × {0,1} −→ {0,1} × {0,1}

(1,0) 7−→ (1,1)(0,1) 7−→ (1,1)(1,1) 7−→ (1,1)(0,0) 7−→ (0,0)

Fonction de sortie : ω = Id{0,1}


28/50

Diffusion de rumeur

Yt est le nombre d’agents à l’état 1 à l’instant tYt est une chaîne de Markov sur {1,2, . . . , n}pi = P{Yt+1 = i + 1 | Yt = i} = 2i(n−i)n(n−1)

1 2 . . . n-1 n

1 − p1

p1

1 − p2

p2 pn−2

1 − pn−1

pn−1

1

FIGURE – Graphe des transitions de la chaîne de Markov Y

Tn = min{t | Yt = n}

En prenant Vi(t) = P{Tn > t | Y0 = i}, on obtient{Vi(t) = (1 − pi)Vi(t − 1) + piVi+1(t − 1)Vn−1(t) =

(1 − 2n

)tAnalyse probabiliste de protocoles de population

29/50

Diffusion de rumeur

Théorème 4.2.4Pour tout t ≥ 1, nous avons

P{Tn > t | Y0 = 1}≤∼

t−→∞

(1 +

2t(n − 2)2

n

)(1 − 2

n

)t−1et pour i ∈ {2, . . . , n − 1} et t ≥ 0

P{Tn > t | Y0 = i}≤∼

t−→∞

(n − i)(n − 2)i − 1

(1 − 2

n

)t

Théorème 4.2.5Pour tout δ ∈ ]0;1[ et t ≥ n (ln(n)− ln(δ)/2), nous avons

P {Yt = n | Y0 = 2} ≥ 1 − δ.


30/50

Diffusion de rumeur

2

4

6

8

10

12

14

16

18

20

10 102 103 104 105 106

Tem

pspa

rallè

lede

diffu

sion

Nombre n d’agents

τ(n, δ = 10−3)simulations avec δ = 10−3τ(n, δ = 10−2)simulations avec δ = 10−2τ(n, δ = 10−1)simulations avec δ = 10−1

FIGURE – Temps parallèle de convergence de la diffusion de rumeuren fonction de n, avec N = 104.


31/50

Diffusion de rumeur

4

6

8

10

12

14

16

10−510−410−310−210−1

Tem

pspa

rallè

lede

diffu

sion

δ

τ(n = 104, δ)simulations avec n = 104τ(n = 103, δ)simulations avec n = 103τ(n = 102, δ)simulations avec n = 102

FIGURE – Temps parallèle de convergence de la diffusion de rumeuren fonction de δ, avec N = 106.


32/50

Diffusion de rumeur

Théorèmes 4.2.9 et 4.2.10Pour tout c ∈ R+, nous avons

limn→+∞

P{Tn > cE(Tn)} =

0 si c > 11 − 2e−γK1 (2e−γ) si c = 11 si c < 1,avec 1 − 2e−γK1 (2e−γ) ≈ 0.448429.γ est la constante d’Euler et K1 est la fonction de Bessel modifiée dedeuxième espèce et d’ordre 1, pour z > 0 on a

K1(z) =z4

∫ +∞0

t−2e−t−z2/4tdt .


33/50

L’horloge globale

Image : "La Persistance de la mémoire" Salvador Dali, 1931.


34/50

Formalisation du problème

Algorithme de l’horloge globale

Ensemble d’entrée Σ = {0}Ensemble de travail Q = NEnsemble de sortie Ξ = NFonction d’entrée : ι = Id{0}Fonction de transitionf : N×N −→ N×N

si x ≤ y , alors (x , y) 7−→ (x + 1, y)si x > y , alors (x , y) 7−→ (x , y + 1)

Fonction de sortie : ω = IdN


35/50

Le paradigme à deux choix

En 2018, D. Alistarh 2 et al. ont proposé cet algorithme d’horlogebasé sur le paradigme à deux choix.Gap(t) = max1≤i≤n C

(i)t − min1≤i≤n C

(i)t

En 2010, Y. Peres 3 et al. ont démontré

ThéorèmePour tout t ≥ 0 et σ > 0, il existe des constantes positives a etb indépendantes de t , σ et n, telles que

P {Gap(t) ≥ a(1 + σ) ln (n) + b} ≤ 1nσ

But : déterminer les plus petites valeurs possibles de a et de b

2. D. Alistarh, J. Aspnes and R. Gelashvili. Space-optimal majority inpopulation protocols. SODA 20183. Y. Peres, K. Talwar and U. Wieder. The (1 + β)-choice process and

weighted balls into bins. SODA 2010Analyse probabiliste de protocoles de population

36/50

Formalisation du problème, définition de la mesure

La fonction de transition peut s’écrire pour tout t ≥ 0

(C(i)t+1,C

(j)t+1

)=

(

C(i)t + 1,C(j)t

)si C(i)t ≤ C

(j)t(

C(i)t ,C(j)t + 1

)si C(i)t > C

(j)t

C(k)t+1 = C(k)t si k ̸= i , j∑n

i=1 C(i)t = t

Γ(t) =∑n

i=1

(eα

(C(i)t −t/n

)+ e−α

(C(i)t −t/n

)), avec α > 0

Propriété : Γ(t) ≥ 2eαGap(t)/2


37/50

Résultat

En prenant α = 0.2, nous obtenons ces trois théorèmes

Théorème 6.3.12

Pour tout t ≥ 0, nous avons E{Γ(t)} ≤ 2e7.4n

Théorème 6.3.13Pour tout t ≥ 0 et σ > 0, nous avons

P {Gap(t) ≥ 10(1 + σ) ln (n) + 74} ≤ 1nσ

Théorème 7.4.1Pour tout t ≥ 0 et δ ∈]0,1[, nous avons

P {Gap(t) ≥ 10 ln(n)− 10 ln(δ) + 74} ≤ δ


38/50


0

2

4

6

8

10

12

14

16

18

20

10 102 103 104 105 106 107

Gap

n

Gap maximalGap moyen

Gap minimal

FIGURE – Gap minimum, moyen et maximum en fonction de n


39/50


0

50

100

150

200

250

300

350

400

10 102 103 104 105 106 107

Gap

n

Gap maximalGap moyen

Gap minimala=10, b=74

FIGURE – Résultats de simulations comparés aux résultatsthéoriques avec σ = 1


40/50

La détection de convergence

Image provenant du site lebigdata.fr, 2018Analyse probabiliste de protocoles de population

41/50

Pré-requis pour la détection de convergence

Soit P = (Σ,Q,Ξ, ι, f , ω), un protocole de population quelconque,vérifiant ces hypothèses :

L’événement {P converge à l’instant t} est croissantIl existe un instant τ3(n, δ) t. q. pour t ≥ τ3(n, δ), nousavons P {P converge à l’instant t} ≥ 1 − δ


42/50

Comment construire un mécanisme de détection deconvergence? (1)

Nous utilisons l’horloge globale et la diffusion de rumeur

L’état du nœud i à l’instant t est le triplet(

T (i)t ,S(i)t ,C

(i)t

):

T (i)t est l’état de l’horloge globale

S(i)t est l’état de la diffusion

C(i)t est l’état du protocole P

Soit τ1(n, δ) = 10 ln n + 10 ln δ + 74 la borne du Gap del’horloge globale avec probabilité supérieure à 1 − δSoit τ2(n, δ) = ln n + 0.5 ln δ, la borne de convergence de ladiffusion de rumeur avec probabilité supérieure à 1 − δ


43/50

Comment construire un mécanisme de détection deconvergence? (2)

Soit Tmax = τ1(n, δ/3) + τ3(n, δ/3)

Pour tout i , nous avons T (i)0 = 0 et S(i)0 = 0

Quand les nœuds i et j interagissent à l’instant t , nousavons

Si T (i)t = T(j)t = Tmax − 1, alors S

(i)t+1 := S

(j)t+1 := 1

Sinon

(T (i)t+1,T

(j)t+1

):=

(

T (i)t + 1,T(j)t

)si T (i)t ≤ T

(j)t(

T (i)t ,T(j)t + 1

)si T (i)t > T

(j)t

et(

C(i)t+1,C(j)t+1

):= f

(C(i)t ,C

(j)t

)


44/50

Résultat sur la détection de convergence

Soit τ(n, δ) = Tmax+τ2(n, δ/3) = τ1(n, δ/3)+τ2(n, δ/3)+τ3(n, δ/3),i.e. τ(n, δ) = 11 ln n + 10.5 ln δ + 62.46 + τ3(n, δ/3)

Théorème 7.4.3Pour tout δ ∈]0,1[ et t ≥ nτ(n, δ), nous avons

P

{P converge à l’instant t ,S(1)t = 1, . . . ,S

(n)t = 1

}≥ 1 − δ.

De plus, pour tout δ ∈]0,1[, nous avons

P

{∃t , i t.q. S(i)t = 1 et P n’a pas convergé à l’instant t

}≤ 2δ/3


45/50


Les animaux sont malades (A) ou en bonne santé (B).Quel est le nombre nA d’animaux malades?

Comptage sans la détectionde convergenceÀ différents instants, nous ob-tenons

nA = 11nA = 3nA = 5nA = 5

Comptage avec la détectionde convergenceÀ différents instants, nous ob-tenons

(nA,S) = (11,0)(nA,S) = (3,0)(nA,S) = (5,0)(nA,S) = (5,1)


46/50

Détection de convergence - simulations

Tmax = τ1(n, δ/3) + τ3(n, δ/3) = 15.12 ln n − 16.59 ln δ + 58.24

0

50

100

150

200

250

300

350

400

450

500

10 102 103 104 105

Tem

pspa

rallè

lede

conv

erge

nce

Nombre d’agents n

avec détection de convergencesans détection de convergence

FIGURE – Comparaison du temps parallèle de convergence duprotocole de comptage avec et sans détection de convergence enfonction de n, avec δ = 10−6.


47/50

Détection de convergence - simulations

T ′max = τ ′1(n, δ/3) + τ′3(n, δ/3) = 1.73 ln n − 1.23 ln δ + 1.05.

0

20

40

60

80

100

10 102 103 104 105 106

Tem

pspa

rallè

lede

conv

erge

nce

Nombre n d’agents

avec détection de convergencesans détection de convergence

FIGURE – Comparaison du temps parallèle de convergence duprotocole de comptage avec et sans détection de convergenceoptimisée en fonction de n, avec δ = 10−6.


48/50

Conclusion

Nous avons étudié quatre protocoles : les protocoles dediffusion, de moyenne avec des entiers, de moyenne avecdes réels et le protocole d’horloge.Pour chacun de ces protocoles, nous avons amélioré etexplicité les bornes du temps de convergence.En utilisant ces résultats, nous avons construit unprotocole avec détection de convergence.


49/50

Perspectives

Expliciter le temps de convergence d’autres protocoles depopulation.Étudier le protocole d’horloge "moyenne plus un".Rendre plus précises les bornes de convergence des pro-tocoles de population.

À partir de la connaissance précise des différents protocoles, ilsera possible de les assembler de manière efficace et prouvée.


50/50

Liste des publications

Yves Mocquard, Emmanuelle Anceaume, James Aspnes, Yann Busnel, BrunoSericola, "Counting with population protocols". NCA, Boston, MA, USA 2015

Yves Mocquard, "Compter avec les protocoles de population". Présentation au11ème Atelier en Evaluation de Performances, Toulouse 2016

Yves Mocquard, Emmanuelle Anceaume, Bruno Sericola "Optimal ProportionComputation with Population Protocols". NCA, Cambridge, MA, USA 2016

Yves Mocquard, Samantha Robert, Bruno Sericola, Emmanuelle Anceaume"Analysis of the Propagation Time of a Rumour in Large-scale DistributedSystems". NCA, Cambridge, MA, USA 2016. Best student paper award

Yves Mocquard, Bruno Sericola, Emmanuelle Anceaume, "Probabilistic Analysisof Counting Protocols in Large-scale Asynchronous and Anonymous Systems ".NCA, Cambridge, MA, USA 2017

Yves Mocquard, Bruno Sericola, Emmanuelle Anceaume, "Balanced allocationand global clock in population protocols : an accurate analysis". SIROCCO,Ma’ale HaHamisha, Israël 2018

Yves Mocquard, Bruno Sericola, Emmanuelle Anceaume, "Probabilistic Analysisof Rumor Spreading Time". INFORMS Journal On Computing (IJOC), 2018

Yves Mocquard, Bruno Sericola, Emmanuelle Anceaume, "Population Protocolswith Convergence Detection". NCA, Cambridge, MA, USA 2018


50/50


Documents

Soutenance de thèse Analyse probabiliste de protocoles de populationpeople.irisa.fr/Yves.Mocquard/presentationTheseYvesMoc... · 2019. 1. 28. · Image : Couverture de l’album