Many of the websites and services we use on a day to day basis are housed
and run on centralized servers. While centralized servers have their
beneifits, by virtue of being centralized they come with comprimises. A
centralized server means governments or individuals looking to intercept
certain traffic or shut down a service have a single target.
An anternative is the Peer-to-peer (P2P) network. In a P2P network users
talk directly to each other rather than through a centralized server.
A visual comparison between a centralized and a peer-to-peer Network
source
A full comparison between the two is beyond the scope of this piece. For
more in depth comparisons of Peer-to-peer and centralized networks as well
as examples of how Peer-to-peer networks are used check out these
articles:
Figuring out where to get the data you want, such as a video, file, or
website within a P2P network can be difficult as there isn't necessarily a
centralized system keeping track of what urls lead where. There are many
ways of searching for the desired data including many “deterministic”
approaches such as the well known
BitTorrent protocol. However S. Apel and E. Buchmann claim these approaches “leave aside that:
peers want to obtain queries at different rates, some keys are more popular
than others, and peers can be less reliable” (section 4).
To solve this problem S. Apel and E. Buchmann as well as others took
inspiration from ants. Ants have to deal with similar problems when
searching for food. The food could be anywhere and some food sources are
better than others. To solve this problem ants leave pheromones in their
path. Future ants can then simply follow the smelliest path to go where the
most of their fellow ants have gone. This allows them to quickly organize
and accomplish complicated tasks collaboratively without requiring a queen
to control them all.
To explore this idea I decided to create a program that simulated an Anthill
inspired P2P network
Implementing an Anthill Inspired P2P Network
The ants pheromone system can be implemented in a P2P network in various
albeit similar ways, however I decided to use the approach taken by A.
Montresor and O. Babaoglu in the aptly named Anthill framework for the
overall design, with some implementation details taken from the excellent
Sebastian Lague
Video on simulating ants and slime molds.
In this framework each "peer" or participant in the network is thought of as
an Anthill with various ants representing the tasks the anthill is capable of
such as retrieving a website. When these ants are called upon to carry out
actions, they leave information related to their current task at each anthill
they visit. This data left behind is the pheromones that can guide future ants
trying to accomplish the same task. Ideally, through this system efficient
pathways to popular sites, files, etc are formed so they are easier and take
less time to find.
The simulation I created goes through the following steps
Create a "map" with circles of various colors to represent each nest
The empty map
For each nest randomly decide whether to make a request.
This represents getting a website, downloading a file, sending a
chat message etc.
If the nest is making a request:
Randomly choose a color representing the desired data. This color is
chosen from the list of nest colors
Create an ant. This operates as the request. Exploring other
nests until it finds the nest of the desired color (i.e. containing the
desired data). It then brings an orb of that color back to it's
parent nest.
The ants logic while wandering is as follows:
for all the nests the ant could travel to: evaluate how good of a
next place to go it is.
this is calculated as $$f_d \cdot f_r \cdot f_p$$ where:
\(f_d\) is the factor for distance: $$
\left(\frac{1}{w_d}\right)^{p_d} $$ where \(w_d\) is the distance from
ant to nest
\(f_r\) is the factor for how recent the ant visited the nest:
$$ \left(\frac{1}{w_r}\right)^{p_r} $$ where:
\(n\) is the number of times we've visited the nest
\(i_n\) is the number of steps we've taken since visiting the nest
for the \(i\)'th time
and \(w_r = \prod_{i=0}^n\frac{1}{i_n}\)
and \(f_p\) is the factor for the pheromone strength of the nest:$$
(w_p)^{p_p}$$ where \(w_p\) is the strength of target nest color
pheromone at the nest in question
The powers \(p_d\), \(p_r\), \(p_p\) are each manaully configured to
control the impact each factor has
the "goodness" of each nest is then divided by the sum of the goodness'
for each nest to get a percentage
a nest is then chosen at random using a weighted average where each weight is it's calculated goodness
the ant then travels to the chosen nest increasing the pheromone strength
of the ants parent nest . The parent nests pheromone
strength is increased as a sort of trail of bread crumbs leading back home
once the ant reaches it's ultimate target it picks up an orb of the target
nests color and wanders home
