Skip to main content



Algerian Revolutionaries, BitTorrent and Decentralized Search

Revolutionaries and P2P applications may seem to have little in common. However, they are connected by the concept of decentralized search  (Chapter 20, Networks, Crowds and Markets, D. Easley and J. Kleinberg).  A decentralized search algorithm is a method of routing on a random graph that uses only limited, local, information about the realization of the graph.

A crucial part of peer-to-peer networks is databases that map keys to values. A key could be, for example a filename, and the value could be the IP address that has the desired file. These (key,value) pairs can be stored in a centralized database or distributed among various peers belonging to the P2P network. A centralized database was adopted in early P2P systems such as Napster. Each node upon joining, would send a list of locally held files to the central server which would perform the searching and indexing functions. This central component exposed the system to attacks and lawsuits.

On the other hand, Distributed Hash Tables (DHTs) use a distributed database instead, with each node carrying some of the database. Applications like BitTorrent use DHTs. Now, if a peer A wants the value of a key, it needs to contact the peer with the required (key,value) pair. For this, each peer in the network would have to keep track of all other peers in the network, which is impractical for large scale networks. One solution is given by Circular DHTs.

In Circular DHT, each peer is aware of only its immediate successor and predecessor, which amounts to low computation and memory overhead for each peer. In the figure below, there are 8 peers and 8 overlay links arranged in a circle. Peer 4 knows the IP addresses of only peer 3 and peer 5. Take, for example, that peer 10 is responsible for key X, and peer 3 wants to know the value for this particular key. Peer 3 sends a message to its immediate successor, peer 4. Since Peer 4 does not have the key, it sends a message to its successor peer 5. This goes on until the message reaches peer 10. Since peer 10 has the required information, it sends the (key, value) pair to the origin of the message (peer 3).

 

The problem with a circular network is that in the worst case scenario, for a network with N nodes, N messages would be required for one query. Thus on an average, circular networks require N/2 messages. Thus there is a tradeoff between the number of neighbors (overhead cost) and number of messages sent to resolve one query (efficiency). One improvement is the addition of shortcuts, essentially creating small world networks. Optimizing the number of shortcuts is an area of active research. Stoica 2001 and Zhao 2004 provide some ingenious ways.

The fact that peers in circular DHTs know only their immediate predecessors and successors is reminiscent of the organization of the National Liberation Front or Front de Libération Nationale (FLN) during the Algerian revolution for independence from French rule. As highlighted in the Gillo Pontecorvo’s 1966 film, Battle of Algiers, the FLN had structured its network as a pyramid, with each operative knowing only the people he recruited and the people who recruited him. This made the FLN unusually elusive and robust, and the French Military had great difficulties trying to bring the FLN’s guerilla warfare under control.

It took a master strategist Colonel Mathieu, to make sense of the FLN’s structure and bring about a systematic attempt to wipe them out. In the infamous Operation Champagne, we see the French military employing concepts of decentralized search (along with controversial interrogation techniques) to defeat the Algerian guerillas in the Battle of Algiers.

– Kei25

Reference:

Computer Networking, A Top Down Approach, Kurose and Ross

“The Battle of Algiers”, Gillo Pontecorvo, 1966

 http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=1258114

http://pdos.csail.mit.edu/papers/chord:sigcomm01/chord_sigcomm.pdf

 

Comments

Leave a Reply

Blogging Calendar

November 2012
M T W T F S S
 1234
567891011
12131415161718
19202122232425
2627282930  

Archives