<commit_before>Plain Paxos 
===========
<NAME> <<EMAIL>>
v1.0, May 2012


Overview
--------

This repository contains a basic implementation of the core Paxos algorithm. The
distinguishing characteristic of this implementation, as compared to other
freely available open-source implementations, is that this library is completely
agnostic of application domains and networking infrastructures. Whereas most
Paxos implementations are deeply and inextricably embedded within 
application-specific logic, this implementation focuses purely on the Paxos
algorithm and supporting utilities to enhance the algorithm's use in practical 
environments.

The goal of this implementation is to provide an algorithmically correct Paxos
implementation that may be used to provide strong consistency guarantees for
any networked application. Additionally, the tight focus of this implementation
provides an excellent basis for Paxos newcomers to learn about and experiment
with distributed consistency.


Implementation
--------------

The initial implementation language for this library is Python. However, it is
hoped that, should this libary prove useful to the open-source community,
implementations in additional languages will be added over time.

basic.py
~~~~~~~~

This module contains a Python class for each of the three basic roles in Paxos:
Proposer, Acceptor, & Learner. Additionally, it contains an aggregation class
to compose Proposer, Acceptor, and Learner instances into a single, logical 'Node'
class that fullfills the functions of all three roles.

This module provides a straight-forward implementation of the Paxos algorithm.
However, there are two implementation-specific items of note. First is that
each logical entity must be assigned a unique identifier (though this unique id
may be shared between the three roles associted with a particular node on the
network). Although this is implied by the description of the Paxos algorithm,
it is not stated explicitly. Also, "proposal numbers" in this implementation
are better described as proposal 'IDs'. Rather than an integer number, this
implementation uses a tuple of +(number,node_uid)+. The driving purpose for
this change is to prevent two Proposers from independently choosing the same
proposal number and attempting to reach concensus with it. The addition of the
node UID to the numeric proposal number ensures that a Proposer can never
confuse an acceptance for the 'promise' message of another node as a 'promise'
message for itself. The ordering characteristics for the tuples of
+(proposal_number, node_uid)+ are assumed to match those of the Python
interpreter.

multi.py
~~~~~~~~

This module provides a class that converts the single-value-only nature of the
basic Paxos algorithm into a continual stream of value resolutions which is
commonly known as Multi-Paxos. Most practical implementations of Paxos use a
variation on the theme of Multi-Paxos.

durable.py
~~~~~~~~~~

Correct implementations of the Paxos algorithm require saving the algorithm's
current state to persistent media prior to sending each message over the 
network. This is necessary to ensure that promises made to external entities
will never be reneged upon should the application crash and recover at an
inopportune time. This module implements a very simple mechanism for efficiently
saving application state to disk.

proposers
~~~~~~~~~

This is a package that contains useable, real-world implementations of Paxos
proposers. The Paxos algorithm states that when certain failures occur,
retransmissions are required to ensure progress. However, it fails to describe
the details of how these retransmissions or other progression-ensuring actions
should occur. There are likely an infinite number of correct and useful
Proposer implementations that both fulfill the basic Paxos requirements while
simultaneously ensuring efficient forward progress. Initially, this module
contains only a single, practical, heartbeat-based implementation. It is hoped
that other, additional modules will be added as the community develops them.

Testing
-------

As this library serves to provide correctness guarantees to higher-level consumers,
this library's testing must be comprehensive and exhaustive. The +test+
directory of the root source code repository contains the unittest files used to
excersise the implementation. 
<commit_msg>Updated documentation to match new approach<commit_after>Plain Paxos 
===========
<NAME> <<EMAIL>>
v2.0, January 2013


Overview
--------

This repository contains a basic implementation of the Paxos algorithm. The
distinguishing characteristic of this implementation, as compared to other
freely available open-source implementations, is that this library is
completely independent of application domains and networking
infrastructures. Whereas most Paxos implementations are deeply and inextricably
embedded within application-specific logic, this implementation focuses on
encapsulating the Paxos logic within opaque and easily re-usable classes.

The goal of this implementation is to provide an algorithmically correct Paxos
implementation that may be used to provide strong consistency guarantees for
any networked application. Additionally, the tight focus of this implementation
provides an excellent basis for Paxos newcomers to learn about and experiment
with distributed consistency.


Implementation
--------------

node.py
~~~~~~~

This module contains a Python class for each of the three basic roles in Paxos:
Proposer, Acceptor, and Learner as well as an aggregation class that combines
all three roles into a single, logcal 'Node' class. 

The module provides a straight-forward implementation of the Paxos algorithm.
However, there are two implementation-specific items of note. First is that
each node must be assigned a unique id. Although this is implied by the
description of the Paxos algorithm, it is not stated explicitly. Second,
"proposal numbers" in this implementation are better described as proposal
'IDs'. Rather than an integer number, this implementation uses a tuple of
+(number,node_uid)+. The purpose of this is to prevent two Proposers from
independently choosing the same proposal number and attempting to reach
concensus with it. The addition of the node UID to the numeric proposal number
ensures that a Proposer can never confuse an acceptance for the 'promise'
message of another node as a 'promise' message for itself. The ordering
characteristics for the tuples of +(proposal_number, node_uid)+ are assumed to
match those of the Python interpreter.

Another common approach to proposal ids, similar to that of the +(proposal_number,
node_uid)+ tuples, is to use an integer for the proposal id where the bottom few
bits contain a numeric node_uid and the remaining upper bits contain the proposal
number. This implementation may shift to that approach at a later date as it is
more space-efficient but the tuple approach was chosen initially for the sake of
simplicity.


heartbeat.py
~~~~~~~~~~~~

In terms of real-world usage, the core Paxos algorithim leaves a great deal of
functionality undefined. For example, The Paxos algorithm states that when
certain failures occur, retransmissions are required to ensure
progress. However, it fails to describe the details of how these
retransmissions or other progression-ensuring actions should occur. The
omissions were made with good reason though as there are likely an infinite
number of correct and useful implementations that both fulfill the basic Paxos
requirements while simultaneously ensuring efficient forward progress. This
module provides a simple and straight-forward approach based on
heartbeat messages sent from the current leader.


durable.py
~~~~~~~~~~

Correct implementations of the Paxos algorithm require saving the algorithm's
current state to persistent media prior to sending each message over the 
network. This is necessary to ensure that promises made to external entities
will never be reneged upon should the application crash and recover at an
inopportune time. This module implements a very simple mechanism for efficiently
saving application state to disk. 


Testing
-------

As this library serves to provide correctness guarantees to higher-level consumers,
this library's testing must be comprehensive and exhaustive. The +test+
directory of the root source code repository contains the unittest files used to
excersise the implementation. 

{'fraction_non_alphanumeric': 0.042011834319526625, 'fraction_numerical': 0.0014201183431952662, 'mean_word_length': 5.053724928366762, 'pattern_counts': {'":': 0, '<': 9, '<?xml version=': 0, '>': 9, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '4390333', 'n_tokens_mistral': 1921, 'n_tokens_neox': 1833, 'n_words': 1185}