Lab 2 — Message Passing et Leader Election

Ce lab explore la communication entre goroutines en Go à travers le *message passing*, le random walk et l'élection d'un leader dans différents types de topologies. Nous allons examiner des échanges synchronisés de messages, des vecteurs complexes, des marches aléatoires et des algorithmes d'élection sur anneaux et graphes généraux.

1 — Message Passing System

Dans cette première partie, nous allons programmer en Go un système de *message passing* synchrone et une marche aléatoire (*random walk*). Nous allons explorer comment les goroutines échangent des messages et comment des structures plus complexes peuvent circuler dans un réseau.

Question 1 — Ping-Pong de messages

Deux goroutines échangent une balle via un canal. Chaque goroutine incrémente le compteur de la balle avant de la renvoyer.

Si time.Sleep est modifié, le nombre d'échanges change.
Ce code n'est pas event-driven : les goroutines bloquent sur le canal.
On peut simplifier en fusionnant les fonctions de joueurs en une seule fonction paramétrée.

package main

import (
  "fmt"
  "time"
)

// Structure représentant la balle
type Ball struct{ hits int }

// Fonction générique pour un joueur
func player(name string, table chan *Ball, delay time.Duration) {
  for {
    ball := <-table          // reçoit la balle
    ball.hits++              // incrémente le compteur
    fmt.Println(name, "hits:", ball.hits)
    time.Sleep(delay)        // temporisation pour simuler le temps de traitement
    table <- ball            // renvoie la balle
  }
}

func main() {
  table := make(chan *Ball)
  go player("Alice", table, 100*time.Millisecond)
  go player("Bob", table, 100*time.Millisecond)

  table <- &Ball{}           // lancer le jeu
  time.Sleep(1 * time.Second) // laisser les goroutines s'exécuter
  <-table                     // récupérer la balle à la fin
}

Question 2 — Passage de vecteurs

Ici, chaque nœud reçoit un vecteur. Chaque composante k est incrémentée de k à chaque passage, illustrant la circulation de structures plus complexes.

package main

import (
  "fmt"
  "time"
)

// Structure représentant le vecteur
type VectorBall struct{ hitsVector []int }

// Fonction générique pour un joueur qui traite des vecteurs
func player(name string, table chan *VectorBall, rounds int) {
  for range rounds {
    ball := <-table                   // réception du vecteur
    for i := range ball.hitsVector {
      ball.hitsVector[i] += i        // ajout de k à la k-ième composante
    }
    fmt.Println(name, "vector:", ball.hitsVector)
    time.Sleep(100 * time.Millisecond)
    table <- ball                     // renvoi du vecteur
  }
}

func main() {
  table := make(chan *VectorBall)
  rounds := 5
  go player("Alice", table, rounds)
  go player("Bob", table, rounds)

  table <- &VectorBall{hitsVector: []int{0, 0, 0}}
  time.Sleep(1 * time.Second)
  <-table
}

Question 3 — Random Walk

Un token se déplace aléatoirement dans un graphe représenté par une matrice d'adjacence. La probabilité qu'un voisin reçoive le token est 1/N_u, où N_u est le nombre de voisins du nœud actuel.

Question 4 — Implémentation du random walk

Exemple de Graphe pris ici

package main

import (
  "fmt"
  "math/rand"
  "time"
)

// Node pour Random Walk
type Node struct {
  edge  int
  token string
}

// Matrice du graphe
type RandomWalkMatrix struct {
  nodes [][]Node
}

// Fonction de random walk
func randomWalk(startNode int, matrix *RandomWalkMatrix, steps int) int {
  current := startNode
  for i := range steps {
    fmt.Println("Step", i+1, "token at node", current)
    neighbors := []int{}
    for j, node := range matrix.nodes[current] {
      if node.edge == 1 && j != current {
        neighbors = append(neighbors, j)
      }
    }
    if len(neighbors) == 0 {
      fmt.Println("Node", current, "has no neighbors, stopping walk")
      break
    }
    next := neighbors[rand.Intn(len(neighbors))]
    fmt.Println("Token moves from", current, "to", next)
    current = next
    time.Sleep(100 * time.Millisecond)
  }
  fmt.Println("Random walk finished, token at node", current)
  return current
}

func main() {
  matrix := &RandomWalkMatrix{
    nodes: [][]Node{
      {{1, ""}, {1, ""}, {0, ""}, {1, ""}, {0, ""}, {1, ""}, {0, ""}, {0, ""}, {1, ""}, {0, ""}},
      {{1, ""}, {1, ""}, {1, ""}, {0, ""}, {1, ""}, {0, ""}, {1, ""}, {0, ""}, {0, ""}, {1, ""}},
      {{0, ""}, {1, ""}, {1, ""}, {1, ""}, {0, ""}, {1, ""}, {0, ""}, {1, ""}, {0, ""}, {0, ""}},
      {{1, ""}, {0, ""}, {1, ""}, {1, ""}, {1, ""}, {0, ""}, {1, ""}, {0, ""}, {1, ""}, {0, ""}},
      {{0, ""}, {1, ""}, {0, ""}, {1, ""}, {1, ""}, {1, ""}, {0, ""}, {1, ""}, {0, ""}, {1, ""}},
      {{1, ""}, {0, ""}, {1, ""}, {0, ""}, {1, ""}, {1, ""}, {1, ""}, {0, ""}, {1, ""}, {0, ""}},
      {{0, ""}, {1, ""}, {0, ""}, {1, ""}, {0, ""}, {1, ""}, {1, ""}, {1, ""}, {0, ""}, {1, ""}},
      {{0, ""}, {0, ""}, {1, ""}, {0, ""}, {1, ""}, {0, ""}, {1, ""}, {1, ""}, {1, ""}, {0, ""}},
      {{1, ""}, {0, ""}, {0, ""}, {1, ""}, {0, ""}, {1, ""}, {0, ""}, {1, ""}, {1, ""}, {1, ""}},
      {{0, ""}, {1, ""}, {0, ""}, {0, ""}, {1, ""}, {0, ""}, {1, ""}, {0, ""}, {1, ""}, {1, ""}},
    },
  }

  go randomWalk(0, matrix, 15)
}

2 — Leader Election on a Ring

Chaque nœud propage l'identifiant maximum qu'il connaît. Quand un nœud reçoit son propre identifiant, il devient leader. La structure Messagecontient : max, counter, terminate.

package main

import "fmt"

// Structure de message pour l'élection
type Message struct {
  max, counter int
  terminate    string
}

// Fonction représentant un nœud du ring
func nodeRing(id int, in, out chan *Message, decision chan *Message) {
  state := &Message{max:id, counter:1, terminate:"No"}

  for msg := range in {
    newCounter := msg.counter + 1

    if msg.max > state.max {
      state.max = msg.max
      state.counter = newCounter
      out <- state
    } else if msg.max < state.max {
      state.counter = newCounter
      out <- state
    } else {
      // Si le max revient au nœud initial → leader
      state.counter = newCounter + 1
      state.terminate = "Yes"
      decision <- state
      return
    }
  }
}

func main() {
  ch1to2 := make(chan *Message)
  ch2to3 := make(chan *Message)
  ch3to1 := make(chan *Message)
  decision := make(chan *Message)

  go nodeRing(1, ch3to1, ch1to2, decision)
  go nodeRing(2, ch1to2, ch2to3, decision)
  go nodeRing(3, ch2to3, ch3to1, decision)

  ch1to2 <- &Message{max:1, counter:1, terminate:"No"} // démarrage de l'élection
  res := <-decision
  fmt.Println("Leader elected in ring: max:", res.max, " counter:", res.counter, " terminate:", res.terminate)
}

3 — Leader Election in General Graphs

Chaque nœud propage le maximum qu'il connaît à tous ses voisins. Après un nombre de tours égal au diamètre du graphe, le nœud avec l'ID le plus élevé est élu leader.

Exemple de Graphe pris ici

package main

import "fmt"

// Structure de message
type Message struct {
  max, counter int
  terminate    string
}

type matriceAdj struct {
  nodes [][]int
}

// Diffusion sur tous les canaux sortants
func broadcast(outChans []chan *Message, m *Message) {
  for _, out := range outChans {
    out <- &Message{max: m.max, counter: m.counter, terminate: m.terminate}
  }
}

// Fonction représentant un nœud du graphe général
func generalNode(id int, inChans []chan *Message, outChans []chan *Message, decision chan *Message, diameter int) {
  state := &Message{max: id, counter: 1, terminate: "No"}
  fan := make(chan *Message, 100)

  for _, ch := range inChans {
    c := ch
    go func() {
      for msg := range c {
        fan <- msg
      }
    }()
  }

  for {
    msg := <-fan
    newCounter := msg.counter + 1
    if msg.max > state.max {
      state.max = msg.max
      state.counter = newCounter
      broadcast(outChans, &Message{max: state.max, counter: state.counter, terminate: "No"})
    } else if msg.max < state.max {
      state.counter = newCounter
      broadcast(outChans, &Message{max: state.max, counter: state.counter, terminate: "No"})
    } else {
      if newCounter < diameter {
        state.counter = newCounter
        broadcast(outChans, &Message{max: state.max, counter: state.counter, terminate: "No"})
      }
      state.counter = newCounter + 1
      state.terminate = "Yes"
      decision <- &Message{max: state.max, counter: state.counter, terminate: state.terminate}
      return
    }
  }
}

func main() {
  graph := &matriceAdj{
    nodes: [][]int{
      {0, 1, 0, 1, 0},
      {1, 0, 1, 0, 1},
      {0, 1, 0, 1, 0},
      {1, 0, 1, 0, 1},
      {0, 1, 0, 1, 0},
    },
  }

  n := len(graph.nodes)
  channelsFrom := make([][]chan *Message, n)
  for i := range n {
    channelsFrom[i] = make([]chan *Message, n)
    for j := range n {
      if graph.nodes[i][j] == 1 {
        channelsFrom[i][j] = make(chan *Message, 10)
      }
    }
  }

  decisionGraph := make(chan *Message)

  for i := range n {
    inbox := []chan *Message{}
    outbox := []chan *Message{}
    for j := range n {
      if graph.nodes[i][j] == 1 {
        outbox = append(outbox, channelsFrom[i][j])
        inbox = append(inbox, channelsFrom[j][i])
      }
    }
    go generalNode(i, inbox, outbox, decisionGraph, 10)
  }

  start := &Message{max: 1, counter: 1, terminate: "No"}
  for j := range n {
    if channelsFrom[0][j] != nil {
      channelsFrom[0][j] <- start
    }
  }

  resGraph := <-decisionGraph
  fmt.Println("Leader elected in general graph: max=", resGraph.max, " terminate=", resGraph.terminate, "
")
}

4 — Leader Election k-Neighborhood

4.1 — Maximum de winners en phase k :Chaque winner occupe au moins 2*f(k)+1 sommets (son voisinage). Donc le nombre maximal de winners est borné par ⌊ n / (2*f(k)+1) ⌋.
4.2 — Nombre de phases nécessaires :Le leader apparaît lorsque f(k) couvre au moins la moitié de l'anneau : le plus petit k tel que f(k) ≥ ⌊ n/2 ⌋. C'est donc K = log2(n/2) pour f(k) = 2^k.
4.3 — Nombre total de messages :À la phase k, chaque winner envoie 2 probes (2 directions), chaque probe parcourt 2^k arcs et revient → 4*2^k messages par winner. Nombre de winners ≤ n / 2^k + 1 → messages par phase ≤ (n / 2^k + 1) * 4*2^k = 2n. Nombre total de phases K+1 → total messages ≤ 2n * (K+1) = 2n * (log2(n/2)+1) = O(n log n)