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.
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
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.
- ''Byzantine Generals Problem''
- Leslie Lamport, Robert Shostak, and Marshall
Pease, ACM Transactions on Programming Languages and Systems, Vol. 4(3), July 1982, Pages
- 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
- 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).
another unified messaging bus
(candidate for use in ball implementation)
- M. Naor and U. Wieder. A simple fault tolerant distributed hash table, 2003
- A byzantine file system. (No byzantine processes.)
- symetric cluster management