CS代考 Consensus Mechanisms – cscodehelp代写

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!