On peut approcher l’ensemble de Julia d’une fonction complexe en itérant son inverse un nombre suffisant de fois. Étudions la (classique) fonction, avec c ∈ ℂ,
$$\begin{aligned} Q_c : \ensuremath{\mathbb{C}}&\to \ensuremath{\mathbb{C}}\\ z &\mapsto z^2 + c \end{aligned}$$
On définit l’orbite à rebours comme {f_c^− n(z₀); n ∈ ℕ}. Pour la calculer, on note que si z² + c = w, alors z = ρexp (iθ) avec $\rho = \sqrt{|w - c|}$ et $\theta = \frac{\vartheta}{2} + \delta \pi$ avec δ ∈ {0, 1} et
$$\vartheta = \arctan(\Im(w - c)/\Re(w - c)) + \begin{cases} 0 & \text{si } \Re(w-c) > 0 \\ \pi & \text{sinon} \end{cases}$$

Le point initial w₀ n’a pas d’importance. On se propose de créer un fil d’exécution par orbite, chaque orbite ayant un point initial différent.

On notera les points ou bien sur la sortie standard, ou bien dans un fichier, chaque ligne étant de la forme x y. Si les points sont notés dans un fichier nommé julia.dat, on peut tracer avec la commande gnuplot julia.p en supposant l’existence du script [fig:gnuplot-julia].

set terminal png size 500,500
set output 'julia.png'
set title 'Julia set'
plot 'julia.dat'

On n’oubliera pas d’importer math.h et complex.h et de compiler avec -lm en fin de ligne de commande. La commande suivant devrait convenir, gcc julia.c -lpthread -lm.

On pourra essayer de tracer l’ensemble de Julia avec les paramètres c ∈ { − 1,  − 0.4 − 0.6i,  − 1.5,  − i,  − 0.8 + 0.4i, 0.5, 3, 1 + i, 2}

Un problème important dans la programmation concurrente est de choisir un leader, e.g. pour l’organisation et la coordination d’un réseau. On part avec un nombre n d’ordinateurs ou de processus (on parlera des nœuds) à priori identiques, à l’exception d’un identifiant unique. En suivant un même protocole, tous les nœuds vont s’accorder sur le choix d’un leader.

Il existe une grande variété de protocoles menant à ce résultat. Nous allons dans ce TP en étudier et en réaliser un: le protocole Dolev, Klawe, and Rodeh qui se distingue par le faible nombre de messages échangé pour l’élection: 𝒪(nlog n). Par comparaison, les approches simples ont tendance à utiliser 𝒪(n²) messages. Le protocole a été presenté en cours et les diapos explicatives sont aussi disponibles dans le répertoire du TD.

Le protocole part du principe que les nœuds sont organiseés en anneau, chaque nœud envoie des messages à son voisin de droite. Le répertoire du TP contient un squelette qui créera n processus (les nœuds) pour n donné; ces processus seront déjà équipés de pipes pour communiquer. Votre tâche est de compléter le programme en réalisant le protocole:

• Au départ, tous les nœuds sont actifs et possèdent un identifiant unique.

• Un nœud actif attend une petite période aléatoire (fonction delay()), puis envoie son identifiant à son voisin de droite. Ensuite, il attend les identifiants de ses deux plus proches voisins actifs à sa gauche. Il décidera ensuite s’il reste actif, devient passif, ou se déclare leader. Les conditions seront précisées dans la présentation. S’il reste actif, il répète le comportement présenté ci-dessus.

• Un nœud passif transmet simplement tous les messages reçus de gauche vers son voisin de droite. En plus, si le message déclare un leader, il affiche un message correspondant à l’écran.

• Il y a trois types de messages échangés par les nœuds, tous dans le format (type,identifiant).

  • “voisin” (v): pour envoyer son identifiant vers le voisin de droite.

  • “prochain” (p): un nœud qui a reçu l’identifiant de son voisin de gauche l’envoie vers son voisin de droite.

  • “gagnant” (g): un nœud se déclare leader.

Un code d’amorçage est disponible a l’adresse http://www.lsv.fr/~hondet/resources/archos/ring.tar.gz.

Complétez la fonction <<protocole>> du fichier <<ring-pipe.c>> qui implémente le protocole sus-décrit.

ring-pipe crée plusieurs processus reliés par des pipes.

Testez votre code avec plusieurs valeurs de n. Observez si votre programme termine toujours et s’il y a toujours un seul leader.

Au besoin réduire la valeur de DELAY pour n grand. Pour n > 255 le code de sortie (obtenu par wait ne suffit plus pour stocker l’identifiant du gagnant.

La version réseau du programme, <<ring-net.c>> instancie un seul nœud par exécution. Vous pouvez recopier votre fonction <<protocole>> depuis <<ring-pipe.c>>. Le programme prend 3 arguments : le port d’écoute du nœud, le nom du nœud voisin (nom de machine), le port de connexion au nœud voisin. Le programme crée un serveur dans un thread et attend la connexion d’un voisin. En parallèle, dans un autre thread, il tente une connexion sur son voisin (nom de machine et port passés en argument). Écrivez un script mettant en œuvre l’exécution de votre code sur 5 machines du département. Commencez par tester l’exécution de votre code localement (machine localhost en utilisant différents ports). Étendre progressivement la taille de l’anneau.

Créez un anneau avec vos voisins et l’étendre à toute la salle de TP.