Spoiler Package II

This spoiler package contains some answers for Exercise Package II.

Assignment 5, Spoiler

In Chord the identifier space forms a ring that is used to decide which node is responsible for which object. The identifier space wraps so after the biggest identifier it returns to the smallest. Each object that matches a node identifier will be stored on the matching node. If the object identifier does not match a node the object will be stored on the next node in the ring.

Thus, a node would typically store objects that have an identifier which is smaller or equal to the node identifier. The wrapping point is an exception where the node with the smallest identifier may end up storing some objects with large identifiers. Also, some nodes might end up storing no objects.

Below you'll find an example how a simplified json input would transform. It is interactive. Try modifying the input.

input	output
{ "nodes": ["00036", "34783", "76321", "93125"], "objects": ["00737", "01105", "01564", "76475", "76493", "76494", "76512", "93125", "93127"] }	{ "00036": ["93127"], "34783": ["00737", "01105", "01564"], "76321": [], "93125": ["76475", "76493", "76494", "76512", "93125"] }

Note that json is agnostic to the order of keys in the object, and the assignment definition did not specify the order for object identifiers in the list. You might write the transformation in javascript as follows.

While the assignment description had example code written in Python I ended up using javascript here so I was able to hook it up to the example above.

Exercise Checker

Select some json answers with the file selector below to check the answers.

Assignment 6, Spoiler

a.

Lets consider node 8D84 with the neighbours 3D67, 5610, 6065, 8072, 8120, 8121, 82B9, 83F3, 8412, 891F, 8CF9, 8D01, 8D21, 8D59, 8D70, 8D82, 8D83, 8D88, 8D8A, 8D8C, 8D8D, 8D8F, 8D99, 8DCE, 8DFD, 8F2A, 9AD1, B380, DBCA and E782.


	symbol
	0	1	2	3	4	5	6	7	8	9	A	B	C	D	E	F
1				3D67		5610	6065			9AD1		B380		DBCA	E782
2	8072	8120	82B9	83F3	8412					891F			8CF9			8F2A
3	8D01		8D21			8D59		8D70		8D99			8DCE			8DFD
4			8D82	8D83					8D88		8D8A		8D8C	8D8D		8D8F

As 8120 and 8121 would go into the same slot in the routing table Tapestry discards one or the other based on proximity of the two nodes in the underlay. The white cells in the routing table are never accessed, since they match the local node identifier.

b.

Queries contain an identifier for the object that is to be stored or retrieved. The object identifiers and node identifiers have the same format. Each node that receives the query does routing decisions based on its local routing table.

To determine a cell in the routing table the local node needs to examine the object identifier present in the query. The correct column in the routing table is determined by the first symbol that differs from the local node identifier. The correct row is determined based on the longest common prefix between the object identifier and the local node identifier. No common prefix selects row 1, a common prefix of length one selects row 2, and so forth.

After selecting a cell in the routing table the node forwards the query to the neighbour identified by the cell. When the selected cell is empty, the node picks another node deterministically using a separate algorithm.

c.

Node insertion starts by finding the node that is currently closest to the identifier of the new node. The objects at that node are distributed between the two. Nodes that have common prefixes with the new node are notified, so they can update their routing tables. Some of these nodes are used to bootstrap the routing table of the new node. The new node queries these initial nodes to fill in gaps in its roting table. The nodes that happen to come in touch with the queries as a side effect of this process use them to optimize their local routing tables.

Assignment 7, Spoiler

a.

Freenet is a storage system that attempts to provide some privacy for publishers of information and their audience. The goal is to provide these guarantees in the presence of adversaries that monitor the system and may participate in running the system. The degree to which the guarantees work depend on the soundness of the design and quality of the software implementation.

b.

The content is encrypted by the publisher before storing the content in the network and decrypted by the audience after retrieving it from the network. This hides the information from nodes that participate in the network. Hashing and cryptographical signatures are used to prevent nodes from modifying the published information.

Privacy is protected by using recursive requests. The replies traverse the same path with the queries, just in the opposite direction. Each node stores the origin of the request for long enough to route the response correctly. As the response arrives, or the request times out, the origin of the request is cleared from the routing table. Thus, an adversary would need to control a large amount of nodes at request time to determine the true origin of a request.

The connections between peers are also encrypted to prevent monitoring of the network. The nodes are referred to with cryptographic identities to prevent man in the middle attacks. Freenet also supports limiting connections to trusted nodes. This feature can be used to make it less likely that one would connect directly to a node run by an adversary.

c.

The identifiers used with Freenet's location swapping are virtual coordinates on a ring. The goal of location swapping is to create optimal identifiers for a given topology that ignores the properties of the underlay. Thus, the location swapping does not take into account geographical locations.

The topology of the overlay may however reflect some properties of the real world, in which case the location swapping might accidentally have some correspondence to the geographical locations. This could be the case for example if a local Freenet club decided to limit their connections to trusted nodes only.

Assignment 8, Spoiler

a.

Power laws tell us something about distribution, but there is no single power law. Instead some distribution laws can be categorized as power laws. A distribution is considered to follow a power law if it draws a straight line when plotted on a plane where both axes have a logarithmic scale.

b.

The term small-world network refers to a network with small relative diameter. In a small-world network the average path length grows logarithmically as more nodes join the network.

The term scale-free network refers to a network where node linkage follows the power law distribution. That is there are lots of nodes that have only a few links, but there are some highly connected nodes available as well.

The small-world networks and scale-free networks both tell us something about routing efficiency in the network. Small-world network consider on the path length directly, while scale-free networks concentrate on clustering that effects the routing efficiency indirectly.

c.

Being able to categorize distributions and networks help network researchers crop out possibilities that do not match the network that they are studying. Having a common language also spurs co-operation between network researcher in different fields.