Consensus Mechanisms
This week, we are going to look at some different mechanisms by which a collection of agents can reach consensus on some question.
There are three parts to the lecture:
– Part A is an Introduction given by me
– Part B is Voter Models (aka Flag Colouring) given by Dr Kohan Marzagão
– Part C is on Consensus in Blockchain, and is given by me.
We will touch on some of the models and mathematics involved.
Image:
2
Intermission
First, I ask you to pause this presentation and look at the following video, about some small robots called Kilobots:
https://www.youtube.com/watch?v=rdM_xJkfn6k
Kilobot robots are 3.3cm tall and were developed from 2010 by & at Harvard University. They were intended to be low-cost robots for the study of swam robotics. They can be purchased from K-Team in Switzerland.
Image:
3
Assumptions 1
We have multiple agents or computational entities
Each agent is programmed with the same program
Each agent is connected to zero or more others
– either they are linked together, or they can see each other
So each agent has a local neighbourhood with a finite set of neighbours
We can represent this situation as a graph
– with agents as nodes, and “the connections” between them as
edges
– We use the terms “agent” and “node” interchangeably.
4
Assumptions 2
We assume each agent can take a finite number of states (often called “colours”).
– For example, they can be either Blue or Red
Interactions proceed in a series of rounds (or editions)
– Each round, each agent has to decide what state (colour) to be in
– Agents make their decision according to an algorithm (which could be random)
– All agents are using the same algorithm
– The algorithm may first check the colours of the neighbours in the previous round.
We assume the agents share a common goal to achieve an overall configuration of states, eg:
– All nodes have the same colour
– No two adjoining nodes have the same colour
– The colours alternate (if the nodes are in line or a circle),
5
Questions a computer scientist would naturally ask
If each agent can have a finite number of colours, will they ever converge to the desired configuration?
Is convergence possible from a random start?
If convergence is possible, what is the probability of convergence?
If convergence is possible, how fast will the nodes converge?
Are deadlocks possible?
Are cycles possible?
Can convergence be facilitated from particular starting configurations?
6
A problem domain with similar questions: Rubik’s Cube
Image source: Wikipedia
7
Questions an agents person would naturally ask
What happens if one or more agents are not following the common algorithm?
For instance, what if one agent is malicious and does not wish to achieve the common goal (of a particular configuration)?
What if one agent has the same shared goal but has buggy code?
– It is often difficult to distinguish malice from bugs when we can only
observe the agent’s external behaviour
What if one or more agents are temporarily offline?
Can the agents protect themselves from a malicious or buggy agent? Can the other agents isolate the influence of the dissident agent? Can the other agents even identify dissident behaviour?
8
Applications 1
Robot bucket brigades
– Each robot has to be either giving or receiving a bucket at each
round
– So the desired configuration is alternating colours.
Bucket Brigade, Dresden, Germany After WW II Source: Wikipedia
9
Applications 2
Consensus in distributed systems (eg, blockchains) – We will talk about this in Lecture 9 Part C
Designing and managing swarms
– Birds in flocks and bees in swarms seem to continually adjust their speed and trajectory according to the birds they can see around them
– We can create similar algorithms for swarms of autonomous vehicles, such as flying drones or convoys of ships or convoys of road vehicles.
10
Image Credit: Rolls Royce Blue Ocean
Thankyou!