CS 711 1 radu/2020
Assignment 4 v2 Assignment 4 requires one project and one brief essay.
Project
An implementation of the synchronous EIG-based Byzantine agreement algorithm,
working on the complete graph.
The project shall consist of a single source file, containing definitions for Node and for
Arcs, an adapted version of our previous Arcs (not part of the algorithm).
In the submitted version, your own standard output stream (Console.Out) must fully conform to the sample output described below. This is very important for our automarker.
The appendix contains snapshots with our visual Byzantine demo running a sample scenario.
Essay
Select and critically review any interesting paper(s) which discuss(es) one of the
following topics (your choice):
o Byzantine algorithms and blockchains.
o Authenticated Byzantine algorithms.
o Asynchronous Byzantine algorithms.
o Practical Byzantine algorithms (less costly).
Your review should be structured and formatted as a short conference paper, well- argued and supported by additional evidence, e.g. references/citations. It must adhere to a strict page limit, up to 3 pages (without references).
Note: Such topics appear under various names, such as: Byzantine / distributed / fault- tolerant generals / algorithm / agreement / consensus / protocol … not all for the same problem, but many are. E.g. just from the Dijkstra prize list: 2001, 2005, 2007, 2010, 2015, 2017 (https://en.wikipedia.org/wiki/Dijkstra_Prize)
If needed, please don’t hesitate to check with us about the suitability of your selected topic / papers.
CS 711 2 radu/2020
Config
Arcs reads the config file from stdin, e.g.:
There are N+1 lines in total, where N = # of process nodes, N in 1..9. End -of-line comments are optional and here indicate the meaning of each value: N = # of process nodes; L = # of EIG levels; V0 (well known); P = process number (1..N); V = initial choice; F = failure flag (0: loyal, 1: faulty).
Each faulty process line P continues with a script indicating the messages that that process P is expected to send. Conceptually, there are L∙N blocks of values, in order:
o S=1: N blocks of length 1
o S=2: N blocks of length N-1 o S=3: N blocks of length … o…
o S=L: N blocks of length …
For each given level S, the N blocks are to be sent to processes 1, 2, …, N, in this order. Each block represents the level S-1 values that need to be sent, in left-to-right order (considering an ordered EIG tree) – more precisely, what values that faulty process claims to have recorded at level S-1.
Faulty-script conventions (similar to our demo):
o legal sequence digits are 0, 1, 2, 3
o 0 and 1 indicate the two values exchanged by loyal participants
o 2 indicates null, missing/corrupt messages – to be replaced by v0
o 3 indicates that the faulty participant sends the correct value at this position
o illegal characters are assumed to be 2
o missing characters are assumed to a repeat of the last preceding digit (0, 1, 2, 3) o internal faulty script spaces are optional and only relevant for readability
o extra characters are discarded
4 2 0 // N L V0 1010011011011011011 //PVFscript 2 0 0 // P V F
410
310
CS 711 3 radu/2020
For example, the following faulty scripts are equivalent:
Workflow
There are 2∙L+1 steps, numbered S = 0, 1, 2, …, 2∙L. Step S = 0 is the initialisation; steps S = 1, 2, …, L are the top-down messaging rounds; steps S = L+1, L+2, …, 2∙L are the bottom-up evaluation.
Generally, at each step:
1. Arcs sends messages to each of the N processes, in numerical order P = 1, 2, …,
N. Process P uses the received messages to complete its step task, i.e. to
determine its next level down or up in the EIG tree.
2. Then, P prints the resulting level, in left-to-right order, in the format [S P values],
separating sibling groups by single spaces.
3. Finally, P sends its response messages to Arcs.
Messages may include either actual messages required by the Byzantine EIG algorithm, or special messages designed by you, or may even be “empty”- in the format of your choice.
A few specific details follow, where ellipses (…) designates generic subtasks mentioned above.
S=0: Arcs sends init messages to each of the N processes, in order P = 1, 2, …, N. Each init message contains N, P, V, V0, L. For a faulty node, the message also includes the required faulty script. Process P sets its EIG root (level 0) value to V [then prints and sends its own messages].
S=1, 2, … L-1: Arcs sends all due level S messages to each of the N processes, in order P = 1, 2, …, N. ….
S=L: Same as above, but we are at the leaves level, where there are no more messages to send. Conceptually, top-down values become bottom-up values. … Processes respond with “empty” messages.
S=L+1, L+2, …, 2∙L: Arcs sends “empty” messages to each of the N processes, in order P = 1, 2, …, N. Process P evaluates its level 2∙L-bottom-up value ….
S=2∙L: Processes print their final decisions, and then stop.
0 0 0 1 011 021 112 222
0001 0110211122
000101102112xxxxxxxxxxxxxxxxxx
CS 711 4 radu/2020
Sample printout corresponding to the above config file (N=4, etc):
010 020 031 041
1 1 0011 1 2 0011 1 3 1011 1 4 1011
21 000 111 111
22 000 111 111
23 000 111 111
24 000 111 111
3 1 1011
3 2 1011 3 3 1011 3 4 1011 411 421 431 441
011 011 011
011
Notes
You are free to select actual message format that suits you best. Important is to design a credible simulation, where all contacts between nodes is realised via messages gathered and forwarded by Arcs.
Please don’t hesitate to ask if you need clarifications. Thanks!
Submit electronically:
(1) Your programs, as single source file, to the COMPSCI automarker, and
(2) Your essay as PDF, to Canvas.
Deadline: Monday 12 October, 2020, 23:00.
Do not leave it for the last minute, please. Remember that you can resubmit and, by
default, we only consider your last submission.
Late submissions will incur penalties, 0.25% off for each hour late, for up to eight days.
CS 711 5 radu/2020
APPENDIX
CS 711 6 radu/2020
CS 711 7 radu/2020