Byzantine Generals Coding Sample

Author:

Reshen Amin <reshen@zensrc.com>

General Notes

• A digital copy of the source code for this coding sample is available under version control at <http://bitbucket.org/reshen/byzantine_generals/src>.

• Generally speaking, the Google C++ Style Guide was used for this coding sample, it is available at <http://google-styleguide.googlecode.com/svn/trunk/cppguide.xml>.

• The source code has been marked up with Doxygen style commenting, which can make for much easier navigation. The generated doxygen output can be viewed at <http://zensrc.com/byzgen_doxygen/html/index.html>

Byzantine Generals Introduction

This simple program demonstrates the Byzantine Generals Problem in which multiple generals of the Byzantine Empire's army need to coordinate to attack or retreat from a city. They believe that either some of the other Generals or their Messengers are traitors and may corrupt Orders passed between them, yet they still need to coordinate to all come to the same course of action.

For a good synopsis of the problem, see either Wikipedia <http://en.wikipedia.org/wiki/Byzantine_generals> or Byzantine Generals Problem by Mark Nelson at <http://marknelson.us/2007/07/23/byzantine/>.

For a solution to exist, we must:

1. Terminate - all loyal generals need to reach a decision regarding the orders they've been given.
2. Agree - all loyal generals have to agree on the decision they are making.
3. Valid - all loyal generals have to agree on the value they have been given by their commanding general if and only if the commanding general is loyal.

Build Dependencies

1. a2ps / ps2pdf - for printing of source code
2. Boost
3. cppcheck - for static analysis of code during compilation
4. Doxygen - for doxygen documentation
5. etags - for TAGS generation over source code
6. GNU Make
7. GNU poject C++ compiler
8. Graphviz / dot - for graph generation
9. Log4cpp
10. Valgrind - for memory self tests

Build Targets

See 'make help' for latest target options.

Example Usage

The following example demonstrates 5 loyal generals and 2 disloyal generals.

> byzgenerals --loyalists 5 --traitors 2 --verbose=true --graph=true
Byzantine Generals Problem Coding Sample
Copyright (C) 2010  Reshen Amin <reshen@zensrc.com>
This program comes with ABSOLUTELY NO WARRANTY; This is free
software, and you are welcome to redistribute it under certain
conditions; See the GNU General Public License for more
details.

15:35:42.374 NOTICE : Number of traitor generals set to 2.
15:35:42.376 NOTICE : Number of loyal generals set to 5.
15:35:42.376 NOTICE : Graph output is enabled.
15:35:42.376 NOTICE : Verbose debugging is enabled.
15:35:42.376 INFO : Each general should receive 37 messages in all.
15:35:42.378 NOTICE : General 1 randomly chosen to be disloyal.
15:35:42.379 NOTICE : General 5 randomly chosen to be disloyal.
15:35:42.380 INFO : Starting Lieutenant General #4
15:35:42.381 INFO : Starting Lieutenant General #5
15:35:42.381 INFO : Starting Lieutenant General #3
15:35:42.381 INFO : Starting Lieutenant General #1
15:35:42.381 INFO : Starting Commanding General
15:35:42.381 NOTICE : Commanding General (loyal) issuing order to Retreat
15:35:42.381 INFO : Current round: 0
15:35:42.381 INFO : Starting Lieutenant General #6
15:35:42.381 INFO : Starting Lieutenant General #2
15:35:42.382 INFO : Current round: 1
15:35:42.387 INFO : Current round: 2
15:35:42.424 NOTICE : Lieutenant General #4 decided to Retreat
15:35:42.424 NOTICE : Lieutenant General #5 decided to Retreat
15:35:42.432 NOTICE : Lieutenant General #1 decided to Retreat
15:35:42.434 NOTICE : Lieutenant General #3 decided to Retreat
15:35:42.434 NOTICE : Lieutenant General #6 decided to Retreat
15:35:42.434 INFO : Completed Commanding General
15:35:42.434 INFO : Writing tree_0.dot
15:35:42.436 INFO : Writing tree_1.dot
15:35:42.436 NOTICE : Lieutenant General #2 decided to Retreat
15:35:42.437 INFO : Writing tree_2.dot
15:35:42.438 INFO : Writing tree_3.dot
15:35:42.439 INFO : Writing tree_4.dot
15:35:42.441 INFO : Writing tree_5.dot
15:35:42.442 INFO : Writing tree_6.dot

The graph below shows the output from General #1's communication tree. As each message is received, it is added to the tree using the communication path contained therein. The communication path is simply an ordered list of each General who touched that particular message. The second line, labeled Rx, shows what the order was when the message was received. The third line, labeled Vote, is a majority vote of all of the node's childrens' Rx fields. Each level in the tree represents all of the messages sent during that round of communication. Nodes that are colored pink are messages that have passed through at least one disloyal general. The white nodes should always outnumber the pink nodes, indicating that despite the disloyal generals best efforts, a deterministic outcome is always possible.

[ PDF ]

License

Byzantine Generals Problem Coding Sample
Copyright (C) 2010 Reshen Amin

This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, version 3 of the License.

This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with this program. If not, see <http://www.gnu.org/licenses/>.