29-06-2010, 12:44 PM
[attachment=3896]
PARASITIC COMPUTING
OUTLINE
Introduction
Experimental evidence
Theory
Proof of concepts
2-SAT problem
How it differs from others
Advantages
Disadvantages
conclusion
References
INTRODUCTION
First reported in Journal Nature in 2001 by
Barabasi, Freeh, Jeong and Brockman
A Successor to distributed computing
Used for solving complex computational problems
Exploits standard set of communication protocol on internet
What Is Parasitic computing
DEFINITION
The term parasitic computing refers to the technique of using the resources of one computer by another computer without the knowledge of the former.
It uses the computation power of the computers connected to the internet in solving complex mathematical problems.
Ex: Travelling Salesman, Satisfiability problem
EXRERIMENTAL EVIDENCE
Internet communication.
When user selects a URL
Actions at sender
Open a TCP connection to a web server
Issue a HTTP request over TCP connection
TCP message is carried via IP
Actions at receiver
Receive message through IP
Validate checksum at TCP
Validated pushed to HTTP
Not validated discard the packet
Theory To Solve Problem
Generate a large number of candidate solutions
Send the solutions to destination node
Test the candidate for their adequacy
If result is true, the solution is valid else drop
The result from each is combined to get solution
HOWTO TRICK OTHER COMPUTERS
Candidate Solution Can be tested in parallel ,an effective computer architecture for these problems is one that supports simultaneous evolution of many tests.
An example of such a machine is shown beside.
A single Parasite node coordinate the computation
occurring remotely in the internet protocol.
each of target node consist of
Arithmetic and Logic Unit(ALU)
Network Interface(NIF)
Single home parasite initiate the computation, directing them to test and tabulate the result.
CHECKSUM COMPUTATION
The checksum is a simple function performed by all web servers(in TCP), which allows a recipient to check if the message is corrupted during transmission.
Message is constructed in such a way that TCP checksum fails for all messages containing an invalid solution
a. Parasitic node breaks N bit message into 16-bit words as S1¦.Sk
b. K words are added together and oneâ„¢s-complement is done to get SUM
c. Checksum and its complement
d. Again receiver will break the received message and add
PROOF OF CONCEPT
N-P complete problem
problems for which no polynomial-time algorithm is known
SAT problem
SAT problem involves finding a solution to a Boolean
equation that satisfies a number of logical clauses
2-SAT PROBLEM
P=(x1 x2)^(x3 x4)^(x5 x6)^(x7 x8)^(x9 ^x10)^(x11 x12)^(x13^x14 )^(x15 x16)
HOW IT DIFFERS FROM OTHERS
Cluster computing
It is not hacking
ADVANTAGES
Theoretically gives chance to use vast computational power of the internet
Several large problem can be solved by engaging various web server physically located at different part of world
It does not comprise the security of target node it access only the part to server that have been made explicitly available for internet communication
DISADVANTAGES
Internet wide parasitic computing is only a theoretical consideration
Communication to computation ratio
Delayed Services
CONCLUSION
Blurring the distinction between computation and communication and drastically altering the current use of internet
Implementation offered above represents only proof of concepts it merely serves to implement idea behind parasitic computing.
TCP checksum provides computation at the cost of hundreds of machine cycles
To make model viable the computation “to-
communication ration must be large
REFERENCES
http://en.wikipediawiki/Parasitic_computing
http://nd.edu/~parasite/
http://en.wikipediawiki/2-satisfiability
http://hinduthehindu/2001/09/13/stories/08130001.htm
PARASITIC COMPUTING
During package transfer across the internet message can be corrupted. TCP contains a checksum that provides some data integrity of the message.
Sender compute checksum and transmits that with message. The receiver also compute the checksum and if does not agree with the senderâ„¢s then the message was corrupted and discarded.