ByzantineAgreement

A fundamental problem of distributed computing is that of simulating a (secure) broadcast channel (see also KommunikationsInfrastruktur), within the setting of a P2P network.

A byzantine aggrement can always be reached, if more than 2/3 of the parties are honest, i.e., cast vote for the correct result according to their actual input (which in turn might be falsified).

If this sound too "technical", here is a real world application/implementation scrutinised.

Byzantine Agreement in Askemos

This section is quite old. Needs update.

Askemos deploys atomic broadcast protocol (see Sintra section 2.2) to synchronize process steps's with slight variations:

• A ProcessStep is defined in such a way, that the binary value to agree in the voting (the checksum of state changes during the step) is often deterministic. Therefore the agreement protocol does not need to proceed in (possibly infinit many) rounds.

  "Often deterministic" means here, is deterministic, if it depends exclusive on the input and internal state of the process. But if, for instance, the process reads additional input with "fetch" while processing the message, or depends on local values like the current time, it can become non-deterministic. See the accuracy test for actual measurements of such a case. The BALL implementation could easily proceed in additional rounds as standard byzantine algorithm do. I don't think additional rounds should be made standard behaviour instead we should put that into applications control.

• If the network is fragmented messages can be lost. If nodes miss - one by one - the final ready message in the agreement, the network can get out of sync in such a way, that resynchronisation becomes impossible. The BALL implementation extents the echo/ready messages in such a way, that the last phase can be recovered.

Further Work

This section is very outdated, but still contains useful references not incorporated anywhere so far.

Utilizing a setup or preprocessing phase it is possible to lower that requirement to some extend, Y. Lindell, A. Lysyanskaya and T. Rabin show http://www.wisdom.weizmann.ac.il/home/lindell/public_html/composeBA_abs.html upper bounds of utility of that approach.

TODO The 0.7.x version of BALL deploys HTTPS as node-node protocol. Availibility of a second message bus (from the references) is desired feature. The current implementation will be kept readily available and brought forward to protect against anticipated, future security bug in the alternate message bus, to be be deployed at the (accepted) cost of degrading performance until the bug is fixed.

References

''Byzantine Generals Problem''

Leslie Lamport, Robert Shostak, and Marshall Pease, ACM Transactions on Programming Languages and Systems, Vol. 4(3), July 1982, Pages 382-401

L. Kesteloot

Fault-Tolerant Distributed Consensus (1995).:

Upright (2010-12-05)

Upright provides the same services as ''dispatch layer'' module structure in BALL.

Capability handling seems to be missing (is it actually?).

Features/Applications: file systems (at this time, 2010-12-04)

Implemented in Java.

Open question on http://code.google.com/p/upright/wiki/ProgrammingWithUpRight#Architecture_and_Procedure 4./5.: Is there one application server (aka. single point of failure) or one application server per node running in byzantine agreement?

Sintra ( Sintra )

A fault tolereant replication architecture based on ByzantineAgreement.

on (broadcast) group membership protocols

http://www.cs.colorado.edu/~mishras/research/papers/pdcs03.pdf

spread

a unified messaging bus (candidate for use in ball implementation).

The recovery algorithm of spread is quite similar to our implementation. The main difference is that when spread delivers a message to the application layer the corresponding Askemos event is the permanent commitment of a transaction (see ProcessStep).

Ensemble

Ensemble another unified messaging bus (candidate for use in ball implementation)

M. Naor and U. Wieder. A simple fault tolerant distributed hash table, 2003

http://citeseer.ist.psu.edu/560557.html

Bfs

A byzantine file system. (No byzantine processes.)

symetric cluster management

http://sources.redhat.com/cluster/faq.html

related notes

• http://epubs.siam.org/sam-bin/dbq/article/18708
• A small essay
• On hardening the underlying host system: http://immunix.org