view release on metacpan or  search on metacpan

lib/Algorithm/Kademlia.pod  view on Meta::CPAN

=pod

=encoding utf-8

=head1 NAME

Algorithm::Kademlia - Pure Perl implementation of the Kademlia DHT algorithm

=head1 SYNOPSIS

    use Algorithm::Kademlia qw[xor_distance xor_bucket_index];

    my $local_id = pack( 'H*', '00' x 20 ); # 160-bit ID
    my $rt = Algorithm::Kademlia::RoutingTable->new( local_id_bin => $local_id );

    # Add a peer (handles Least-Recently-Seen eviction policy)
    my $stale = $rt->add_peer( $peer_id, { addr => '127.0.0.1:4001' } );
    if ($stale) {
        # Bucket is full. The protocol requires you to ping the $stale node.
        # If the ping fails:
        #   $rt->evict_peer($stale->{id});
        #   $rt->add_peer($peer_id, ...);
        # If the ping succeeds:
        #   The new $peer_id is discarded (as $stale was moved to the tail).
    }

    # Storage for the DHT
    my $storage = Algorithm::Kademlia::Storage->new( ttl => 3600 );
    $storage->put($key_bin, $value_bin);

    # State management for iterative lookups
    my $search = Algorithm::Kademlia::Search->new(
        target_id_bin => $target_key,
        alpha         => 3
    );
    $search->add_candidates($rt->find_closest($target_key));

    while (!$search->is_finished) {
        my @to_query = $search->next_to_query();
        for my $node (@to_query) {
            # ... Send FIND_NODE RPC to $node ...
            # If response: $search->mark_responded($node->{id}, @found_peers);
            # If failure:  $search->mark_failed($node->{id});
        }
    }
    my @results = $search->best_results();

=head1 DESCRIPTION

C<Algorithm::Kademlia> provides the mathematical and structural foundations for a Kademlia Distributed Hash Table
(DHT). It is designed to be protocol-agnostic, meaning it only handles the XOR-metric distance calculations, the
k-bucket routing table logic, and the search state management.

This module is suitable for building BitTorrent-compatible DHTs, libp2p Kademlia implementations, or custom
peer-to-peer storage systems.

=head1 FUNCTIONS

These are bitwise logic utilities for the Kademlia XOR metrics.

=head2 C<xor_distance( $id1, $id2 )>

Returns the bitwise XOR of two binary strings.

    my $id1  = pack('H*', '00' x 20);
    my $id2  = pack('H*', 'ff' x 20);
    my $dist = xor_distance($id1, $id2);
    say unpack('H*', $dist); # ffffffffffffffffffffffffffffffffffffffff

=head2 C<xor_bucket_index( $id1, $id2 )>

Calculates the index of the k-bucket that C<$id2> would fall into relative to C<$id1>. Returns C<undef> if the IDs are
identical.

The index corresponds to the bit position of the most significant bit that differs between the two IDs. For 160-bit
IDs, the result is between 0 and 159.

    my $local = pack('H*', '00' x 20);
    my $peer  = pack('H*', '80' . ('00' x 19)); # 160th bit differs
    my $idx   = xor_bucket_index($local, $peer);
    say $idx; # 159

=head1 Algorithm::Kademlia::RoutingTable

This class implements the 160 k-bucket structure (or appropriate size for the ID length provided). Peers are bucketed
by their XOR distance from the local node ID.

=head2 C<new( local_id_bin =E<gt> ..., [ k =E<gt> 20 ] )>

Constructor. C<local_id_bin> is the binary string of the local node's ID.

    my $rt = Algorithm::Kademlia::RoutingTable->new(
        local_id_bin => $my_id_bin,
        k            => 20
    );

=head2 C<add_peer( $id_bin, $data )>

Adds a peer to the appropriate bucket.

=over

=item * If the peer is already present, it is moved to the "most recently seen" position (the tail of the bucket).

=item * If the bucket is full (reaches size C<k>), it returns the "least recently seen" peer (the head of the bucket). According to the Kademlia whitepaper, the caller should ping this stale peer.

lib/Algorithm/Kademlia.pod  view on Meta::CPAN

        say 'Key: ' . unpack('H*', $key) . ' Value: ' . $info->{value};
    }

=head1 Algorithm::Kademlia::Search

A state manager for the iterative Kademlia lookup algorithm. It tracks which nodes have been queried, which have
responded, and which have failed.

=head2 C<new( target_id_bin =E<gt> ..., [ k =E<gt> 20, alpha =E<gt> 3 ] )>

Constructor. C<alpha> is the concurrency parameter (how many parallel queries to allow).

    my $search = Algorithm::Kademlia::Search->new(
        target_id_bin => $target_key,
        alpha         => 3
    );

=head2 C<add_candidates( @peers )>

Adds new potential nodes to the search shortlist.

    $search->add_candidates( $rt->find_closest($target_key) );

=head2 C<pending_queries( )>

Returns a list of nodes that have been queried but have not yet responded or failed.

    my @waiting = $search->pending_queries();
    say 'Waiting for ' . scalar(@waiting) . ' nodes...';

=head2 C<next_to_query( )>

Returns a list of up to C<alpha> nodes that have not yet been queried, sorted by proximity to the target.

    my @to_query = $search->next_to_query();
    # Now send your RPCs to these nodes...

=head2 C<mark_responded( $id_bin, @new_peers )>

Marks a node as having responded and adds any new peers it returned to the shortlist.

    # After getting a response from a FIND_NODE RPC:
    $search->mark_responded($peer_id, @peers_from_rpc);

=head2 C<mark_failed( $id_bin )>

Marks a node as failed (e.g., RPC timeout).

    # After a timeout or connection error:
    $search->mark_failed($peer_id);

=head2 C<is_finished()>

Returns true if the search has reached a termination condition (either C<k> nodes have responded, or there are no more
nodes to query and no pending requests).

    while (!$search->is_finished) {
        # ... keep querying ...
    }

=head2 C<best_results()>

Returns a list of the C<k> closest nodes that successfully responded.

    my @k_closest = $search->best_results();

=head1 SEE ALSO

L<InterPlanetary::Kademlia> (for the libp2p implementation)

L<Net::BitTorrent::DHT> (for the BitTorrent implementation)

L<https://xlattice.sourceforge.net/components/protocol/kademlia/specs.html>

=head1 AUTHOR

Sanko Robinson E<lt>sanko@cpan.orgE<gt>

=head1 COPYRIGHT

Copyright (C) 2023-2026 by Sanko Robinson.

This library is free software; you can redistribute it and/or modify it under the terms of the Artistic License 2.0.

=cut