flock_of_birds_-_tower.py 1.09 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38
# -*- coding: utf-8 -*-
params = {
  "scheme": {
    "c": {
      "descr":  "Threshold c",
      "values": range(1, 201),
      "value":  3
    }
  }
}

def generateProtocol(params):
  c = params["scheme"]["c"]["value"]

  states = range(1, c + 1)
  transitions = []

  for i in states:
    for j in states:
      if i < c and i == j:
        transitions.append(Utils.transition((i, j), (i, j+1)))
      elif (i == c or j == c) and (i != c or j != c):
        transitions.append(Utils.transition((i, j), (c, c)))

  return {
    "title":         "Flock-of-birds protocol (Tower)",
    "states":        states,
    "transitions":   transitions,
    "initialStates": [1],
    "trueStates":    [c],
    "predicate":     "C[1] >= {}".format(c),
    "description":   """This protocol computes whether a population of
                        birds contains at least c sick birds, i.e. whether
                        C[1] >= c. Described in Dana Angluin, James
                        Aspnes, David Eisenstat, Eric Ruppert. 
                        The Computational Power of Population Protocols.
                      """
  }