#header-inner {background-position: right !important; width: 100% !important;}

8/26/13

How computers 'think', or conditional instruction 'if' explained.

Computers do not think, they compute (count expression values).

Let's see how processor instruction with assembler mnemonic jne (jump if not equal) may work.

Code:

101. jne val1 val2 :my_section
102. ...
103. ...
104. ...
105. ...

(...)

:my_section: 205. ...

above code is easy to explain:

1. At line 101, jne compares val1 with val2. if they are equal, it continues without jump (at line 102).
2. If val1 is not equal with val2, then jne jumps to memory address to which :my_section label points (line 205).


How it works?

This 'magic' of conditional instruction is explained with few simple tricks:

1. compute eq.

eq = (val1 - val2 == 0) (this is logical expression with boolean value, which in low level evaluates to 0 for false, or 1 for true).

2. next part-instruction for jne is addition.

result of (eq + 1) is added to instruction pointer register, that is either 0 for false or 1 for truth.

3. processor continues with next instruction, as pointed by instruction pointer register.

4. depending on value added at point 2, we end up jumping to line 102, or to line pointed by :my_section label.

That's it, this is conditional branch. We end up executing different code depending on whether val1 is equal with val2 or not.


P.S. please note that memory address and assembly language line are different things.. but work in similar way.


See also: Conditional Instruction & Expressions.

8/21/13

Lazy evaluation.

Laziness speeds up computers.

It's not anything new, that laziness (lazy evaluation) speeds up computers.

Values are not evaluated unneccessarily, freeing up processor for other important evaluations.

It has its uses in conditional instructions ('if') argument evaluations, but not only... it's easy to imagine how (hint: OR logical operator does not need to evaluate everything, to know result of whole logical expression).

8/14/13

Chord (DHT Algorithm).

Introduction.

The elegance of the Chord algorithm, derives from its simplicity.

The keys of the DHT are l-bit identifiers, i.e., integers in the range [0, 2l-1].

They form a one-dimensional identifier circle modulo 2l wrapping around from (2l)-1 to 0.

Identifier Space

Chord Identifier Space. photo chord-identifier-space-transparent_zpsd25b2a34.png

Chord Address Space. Spheres represent nodes. Boxes represent keys. Arcs that do not belong to circle represent successor pointers.




Each data item and node is associated with and identifier. An identifier of a data item is referred to as a key, that of a node as an ID. Formally, the (key, value) pair (k,v) is hosted by the node whose ID is greater than or equal to k. Such node is called successor of key k.

Routing.

Given a Chord identifier circle, all identifiers are well-ordered and keys and nodes are uniquely associated. Thus, each (key, value) pair is located and managed on a single, well-defined node. The DHT is formed by the set of all (key, value) pairs on all nodes of an identifier circle. The key to efficient lookup and modification operations on this data is to quickly locate the node responsible for a particuolar key.

For a very simple routing algorithm, only very little per-node state is required. Each node needs to store its successor node on the identifier circle. When a key is being looked up, each node forwards the query to its successor in the identifier circle. One of the nodes will determine that the key lies between itself and its successor. Thus, the key must be hosted by this successor.

This inefficient form of key location involves a number of messages linear to the number of nodes on the identifier circle. Chord utilizes additional per-node state for more scalable key lookups.

Chord Finger table. photo chord_finger_zps2e18cad3.png

Chord Finger Table. Nodes are connected at intervals increasing by powers of 2.

Each node maitains a routing table, the finger table, pointing to other nodes on the identifier circle. Given a circle with l-bit identifiers, a finger table has a maximum of l entries. On node n, the table entry at row i identifies the first node that succeeds n by at least 2i-1, i.e., successor(n+2i-1), where 1 <= i <= l. The first finger of a node is always its immediate successor on identifier circle.

As a finger table stores at most l entries, its size is independents of the number of keys or nodes forming the DHT. Each finger entry consits of a node ID, an IP address and port pair (or equivalent), and possibly some book-keeping information. Even for large identifiers, e.g., l=256, this is a relatively small amount of data per node which can be efficiently managed and searched. The routing information from finger tables provides information about nearby nodes and a coarse-grained view of long-distance links at intervals increasing by powers of two.

The Chord routing algorithm exploits the information stored in the finger table of each node. A node forwards queries for a key k to the closest predecessor of k on the identifier circle according to its finger table. When the query reaches a node n such that k lies between n and the successor of n on the identifier circle, node n reports its successor as the answer to the query.

Thus, for distant keys k, queries are routed over large distances on the identifier circle in a single hop. Furthermore, the closer the query gets to k, the more accurate the routing information of the intermediate nodes on the location of k becomes. Given the power-of-two intervals of finger IDs, each hop covers at least half of the remaining distance on the identifier circle between the current node and the target identifier. This results in an average of O(log N) routing hops for a Chord circle with N participating nodes. For example, a Chord network with 1000 nodes, forwards queries, on average, in roughly O(10) steps.

Self-Organization

The Chord system described so far also needs to allow for nodes joining and leaving the system as well as to deal with node failures.

Node Arrivals

In order to join a Chord identifier circle, the new node first determines some identifier n. The original Chord protocol does not impose any restrictions on this choice. For example, n could be set at random assuming that the probability for collisions with existing node IDs is low in a identifier space large enough. There have been several proposals to restrict node IDs according to certain criteria, e.g., to exploit network locality or to avoid identity spoofing.

For the new node n, another node o must be known which already participates in the Chord system. By querying o for n's own ID, n retrieves its successor. It notifies its successor s of its presence leading to and update of the predecessor pointer of s to n. Node n then builds its finger by iteratively querying o for the successors of n+21, n+22, n+23, etc. At this stage, n has a valid successor pointer and a finger table. However n does not show up in the routing information of other nodes. In particular, it is not known to its predecessor as its new successor since the lookup algorithm is not apt to determine a node's predecessor.

Stabilization Protocol

Chord introduces a stabilization protocol to validate and update successor pointers as nodes join and leave the system. Stabilization requires an additional predecessor pointer and is performed periodically on every node. The stabilize method on a node k requests the successor of k to return its predecessor p. If p equals k, k and its successor agree on being each other's respective predecessor and successor. The fact that p lies between k and its successor indicates that p recentrly joined the identifier circle as k's successor. Thus, the node k updates its successor pointer to p and notifies p of being its predecessor.

With the stabilization protocol, the new node n does not actively determine its predecessor. Instead, the predecessor itself has to detect and fix inconsistencies of successor and predecessor pointers using stabilize method. After node n has thus learnt of its predecessor, it copies all keys it is responsible for, i.e., keys between predecessor(n) and n, while p the predecessor of n releases them.

At this stage, all successor pointers are up to date and queries can be routed correctly, albeit slowly. Since the new node n is not present in the finger tables of other nodes, they forward queries to the predecessor of n even if n would be more suitable. Node n's predecessor then needs to forward the query to n via its successor pointer. Multiple concurrent node arrivals may lead to several linear forwardings via successor pointers.

The number of nodes whose finger table needs to be updated is in the order of O(log N) in a system with N nodes. Based on the layout of a finger table, a new node n can identify, the nodes with outdated finger table as predecessor(n-2n-1) for 1 < i <= l. However, the impact of outdated finger tables on lookup performance is small, and in the face of multiple node arrivals, the finger table updates would be costly. Therefore, Chord prefers to update finger tables lazily. Similar to the stabilize method, each node n runs the fix_fingers method periodically. It picks a finger randomly from the finger table at index i (1 < i <= l) and looks it up to find the true current successor of n + 2i-1.

Node Failures

Chord adresses node failures on several levels. To detect node failures, all communication with other nodes needs to be checked for timeouts. When a node detects a failure of a finger during lookup, it chooses the next best preceeding node from its finger table. Since a short timeout is sufficient, lookup performace is not significantly affected in such a case. The fix_fingers method ensures that failed nodes are removed from the finger tables. To expedite this process, fix fingers can be invoked specifically on a failed finger.

It is particularly important to maintain the accuracy of the successor information as the correctness of lookups depends on it. If, for example, the first three nodes in the finger table of node n fail simultaneously, the next live finger f might not be the true live successor s. Thus, node n would assume that a certain key k is located at s and would accordingly send incorrect replies to queries for k. The stabilization protocol can fail in a similar fashion when multiple nodes fail, even if live fingers are used as backups for failed successors.

To maitain a valid succesor pointer in the presence of multiple simultaneous node failures, each node holds a successor list of length r. Instead of just a single successor pointer, it contains a node's first r successors. When a node detects the failure of its successor, it reverts to next live node in its successor list. During stabilize method call, a successor list with failed node is repaired by augmenting it with additional successors from a live node in the list. The Chord ring is affected only if all nodes from a successor list fail simultaneously.

The failure of a node not only means that it becomes unreachable but also that the data it managed is no longer available. Data loss from the failure of individual nodes can be prevented by replicating the data to other nodes. In Chord, the successor of a failed node becomes responsible for the keys and data of failed node. Thus, an application utilizing Chord ideally replicates data to successor nodes. Chord can use the successor list to communicate this information and possible changes to the application.

Node Departures

Treating nodes that voluntarily leave a Chord network like failed ones does not affect the stability of the network. Yet it is inefficient because the failure needs to be detected and rectified. Therefore, a leaving node should transfer its keys to its successor and notify its successor and predecessor. This ensures that data is not lost and that the routing information remains intact.

8/12/13

Hacking, Imagination and 3D Visualization.

'Imagination is more important than knowledge.' -- Albert Einstein.

When you can see 3D Map of The Internet (or part), and can imagine what happens next, it helps to foresee incoming attacks and develop strategy.

With this approach, Internet War resembles more or less old Core Wars game which requires both Imagination, Programming knowledge and Tactical / Strategic thinking.

Core War is a programming game, based around a variation of assembly language known as Redcode. In a standard game of Core War, two or more programs are placed in a circular region of memory with the objective of causing the other program to fail.

Jung on Active Imagination. (Imagination helps).

Mathematics and the Imagination. (3D Mathematics is basics for 3D Computer Graphics and 3D Visualization).

8/7/13

How to implement Dynamic Code Loading between Web Browsers?

Dynamic Programming.

Dynamic programming has few meanings. I use it in context that refers to maximizing program's flexibility by allowing user to control program at runtime (as opposed to only providing input data before its run).

Dynamic Code Loading.

It means loading code to different machines (either virtual or not) at runtime, without restarting computers. It should be able to be run there.

Solution.

Implement Stitie Machine in javascript using pointer arrays.

State and Strategy can be transmitted using ajax.

See also:

* How to implement linked list using arrays.
* Stitie Machine implementation.
* Stitie Machine 1.1 "Sunsail".