7 releases (breaking)

0.7.0 Dec 29, 2020
0.6.0 Dec 20, 2020
0.5.0 Jul 2, 2020
0.4.0 Jun 7, 2020
0.1.0 Apr 27, 2020

#463 in Algorithms

44 downloads per month
Used in clepsydra

MIT/Apache

49KB
1K SLoC

Concorde

This crate is a work in progress attempt to implement a small, special-case consensus-like algorithm called "reconfigurable lattice agreement", which has some desirable properties:

  • It's asynchronous, small, fast and simple compared with other consensus-like algorithms. Few states, message types and round-trips. The paper introducing it describes it in 20 lines of pseudocode.

  • It supports online reconfiguration without any separate phases: you can add or subtract peers while it's running and it adapts to the changed quorum on the fly.

The price for these desirable properties is high relative to general consensus, but a price you may able and willing to pay:

  • The "object" domain of discourse -- about which you're trying to come to agreement -- has to be a (join semi-)lattice.

  • You have to be ok with the "lattice agreement" API, which is one where you might get an "object" value that's possibly further up its lattice from the value you proposed, and might not even be a value that anyone proposed (just a join of proposals).

Further, the representation of your quorum system (eg. a set of peers) has itself to be a lattice, though in this implementation it is a fixed peer-set quorum system, so you don't really get an option about that here.

Reference

Petr Kuznetsov, Thibault Rieutord, Sara Tucci-Piergiovanni. Reconfigurable Lattice Agreement and Applications. [Research Report] Institut Polytechnique Paris; CEA List. 2019. ffcea-02321547f

https://hal-cea.archives-ouvertes.fr/cea-02321547

Name

Wikipedia:

The Aérospatiale/BAC Concorde is a British–French turbojet-powered supersonic passenger airliner

...

Concorde is from the French word concorde, which has an English equivalent, concord. Both words mean agreement, harmony or union.

(Unrelated to the same-named TSP solver; sorry for name collision)

Dependencies

~7MB
~149K SLoC