-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy pathreading_assignment_1.tex
87 lines (75 loc) · 6.01 KB
/
reading_assignment_1.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
\documentclass[10pt]{proc}
\begin{document}
\large{\textbf{Reading Assignment 1}}\\
\large{\textbf{Authors: Gerard Marin Nogueras \newline Nicolae Paladi}}\\
\section{Motivation}
The paper presents Chord, a protocol that defines a mechanism for an efficient and scalable location of data items in peer-to-peer systems \cite{stoica2001chord}.
In most peer-to-peer systems and applications the core operation is the location of a particular data item stored by some peer.
This operation becomes difficult when the current system needs to be dynamic or scalable.
Chord addresses these problems.
\section{Contributions}
%The paper presents the Chord, along with a proof of its correctness and performance measurements.
%List of contributions:
\begin{itemize}
\item Description of Chord, a distributed algorithm with no node with higher responsibility, no single point of failure.
% The algorithm provides load balancing by using consistent hashing is dynamic in nature (allow nodes to frequently join and leave), robust and routing-efficient with information about few nodes.
\item Theoretical proof of Chord’s correctness
\item Proof of correctness of the Chord algorithm by test and simulation.
\item Proof of performance: briefly presentation of applications for peer-to-peer systems built on top of Chord.
\end{itemize}
\section{Solution}
Chord assigns keys to nodes responsible for them using consistent hashing and evenly distributes them across all nodes.
A query for a certain key uses successor information in the state of the node to visit the nodes along the Chord circle until the two nodes between which a key is stored are identified and points to the second node of the two.
An optimization of the algorithm that allows for scalable lookups extends required node state with a routing table containing information about \emph{m} number of distinct nodes in the Chord circle called fingers.
Finger nodes are selected such that the \emph{i}-th entry of \emph{n}s routing table contains the identity of the first node \emph{s} that succeeds \emph{n} by at least $2^{i-1}$ on the chord circle, which ensures query resolution by contacting O(logN) nodes.
A stabilization algorithm runs periodically to update each node's configuration information.
By maintaining a list of \emph{r} successors on each node, the algorithm ensures the resilience of the Chord ring in the case of \emph{r-1} successor node failures.
%Finally, two optimizations for the case of voluntary node departures can be made by nodes copying their keys to the successor before leaving and informing their predecessor about leaving the Chord circle.
\section{Strong Points}
%\begin{itemize}
%\item Addresses data location in peer-to-peer systems with realistic assumptions
%\item The article analyzes the behaviour of the algorithm in several relevant use cases
%\item Efficiency of the algorithm is proved in the presented evaluation and simulation
%\end{itemize}
%Strong points of the algorithm (advantages over existing algorithms)
\begin{itemize}
\item S1. Load balance, decentralization, scalability, availability, flexible naming
\item S2. Nodes participating in the algorithm need routing information about a limited number O(logN) other nodes for efficient routing.
\item S3. Chord relies on consistent hashing does not require a hierarchical structure to store routing information.
\item S4. Chord is able to handle concurrent node joins and crashes
\end{itemize}
\section{Weak Points}
\begin{itemize}
\item W1. Chord does not provide anonymity for lookup operations.
\item W2. Chord does not ensure that a query will never travel further in network distance than the node where the key is stored.
\item W3. Application requirements: application using Chord is responsible for providing desired authentication, caching, replication and user-friendly naming of data.
\item W4. Not random keys: random choose among a set of hash functions.
% \item W5. Chord behaviour needs to be improved against adversarial nodes or network partitions.
% \item W6. (might be a detail on a different abstraction level) The choice of IP as node identifier excludes the use of nodes behind NAT, which is often the case for virtualized nodes.
% \item W7. The load balancing property does not address the case when one certain key is requested in the overwhelming majority of cases.
\end{itemize}
%\section{Questions}
%None.
\newpage
\section{Questions}
Answers to the questions on the article ``Navigation in a small world'' \cite{kleinberg2000navigation}
\begin{itemize}
\item Q1. What does navigability mean for a small world network?
A small-word network is a network where nodes are rich in structured short-range connections and have a few random long-range connections.
In other words, nodes are highly clustered, and they have random long-connections with other nodes.
According to this model, small-world networks show the property of existing short paths between any pair of nodes.
Concretely, the diameter of the network (the longest path in the network) is bounded to log(N), where N is the number of nodes in the network.
Navigation is the capacity of nodes to discover such short paths given a particular target node, only using its local information.
It means that a node only can forward a particular message intended for a particular target to the known nodes, that is, neighbors.
No node has a general knowledge or view of the network; nodes forward messages based on their acquaintances with other nodes.
\item Q2. Are all small-world networks navigable? explain why.
No, they are not.
Navigability depends on the correlation between local structure and long-range connections.
A certain level of correlation in the small-world network is required to guarantee navigability.
Under this threshold, the long-range connections are generated uniformly at random.
As a result, the network becomes unnavigable.
The short paths between any pair of nodes still exist, but the nodes in the network are not able to find them.
\end{itemize}
\bibliographystyle{plain}
\bibliography{reading_assignments_bibliography}
\end{document}