Askemos 2000 (Archive)
home · features · download · archive

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





border
last modification: Sun, 05 Dec 2010 21:20:09 +0100
authors: jfw,
document identifier: A849640f672ed0df0958abc0712110f3c
delivered to public at Sun, 17 Dec 2017 20:38:08 +0100
short comments


rss

pdf :: context view

search



www.jangoo.de
24 Apr 2004 DefineInsecureMode
12 Dez 2010 FreeBSD
07 Dez 2010 BALLFeatures
05 Dez 2010 ByzantineAgreement
04 Dez 2010 SQLITE
03 Dez 2010 SRS
12 Okt 2010 WebDAV
12 Sep 2010 SQL
16 Jun 2010 BALL
16 Jun 2010 CouchDB
16 Jun 2010 AskemosServer
07 Mai 2010 SystemRequirements
30 Mar 2010 ProjectsOnThePlate
30 Mar 2010 AskemosResources
30 Mar 2010 RSchemeInstall
30 Mar 2010 INSTALL
30 Mar 2010 ChickenScheme
debug-access.scm
27 Nov 2009 subscriber
development
12 Jul 2009 test
01 Jul 2009 TrustCenter
27 Dez 2008 JKomG
26 Dez 2008 FanOut
26 Dez 2008 MIME
NetBSD
NOTE
02 Mai 2006 AskemosTopMenu
18 Nov 2008 StorageAdaptor
18 Nov 2008 PStoreStorageAdapt
18 Nov 2008 OperationTips
15 Nov 2008 PCRE
04 Nov 2008 ProgrammingLanguag
09 Sep 2008 RelatedProjects
23 Jul 2008 ModuleStructure05
17 Jun 2008 NEWS
17 Jun 2008 HTML
17 Jun 2008 ACM
22 Mai 2008 HTTP
22 Mai 2008 BOSH
10 Mai 2008 AskemosBibliograph
10 Mai 2008 JerrysDreamAbstrac
20 Apr 2008 XSLT
11 Mar 2008 CodingStyle
10 Mar 2008
09 Mar 2008 MIMEConverter
BSD
07 Mar 2008 XML
06 Mar 2008 SRFI
01 Mar 2008 RFC4810






Add


home · features · download · archive