New version page

Trading Processor Cycles for Communication

This preview shows page 1-2 out of 7 pages.

View Full Document
View Full Document

End of preview. Want to read all 7 pages?

Upload your study docs or become a GradeBuddy member to access this document.

View Full Document
Unformatted text preview:

Trading Processor Cycles for CommunicationArnab Paul∗Rahul Ray†Umakishore Ramachandran‡Georgia Tech Technical Report GIT-CERCS-04-05Abstract“Trade computation for communication whenever possi-ble” has been the conventional wisdom to save bandwidthand power in wireless domain. We glanced at the merg-ing trends of technology and the applications, and identi-fied a number of areas where the processor cycles can betraded for network bandwidth. These areas are - file trans-fer, shared document edits, remote authentication, and veri-fication of remotely available codes. We collect and presentsome of the theory-paradigms that have given birth to re-sults potentially usable towards saving bandwidth at thecost of computation. We hope to make a case for incorpo-rating the insights collected in this paper from various fieldsof complexity theory, into the design of network protocolsfor the future. In the penumbra of this over-arching goal,we also suggest how the engine of “Probabilistic Check-ing of Proofs” (PCP) can be used for remote authentica-tion purposes, resulting in much smaller network overheadand leading to very efficient usage of bandwidth and power.While this seems to be an interesting route, we then presentthe algorithmic challenges that need be solved and arguewhy such a theoretical cranking may be just as worth.1 IntroductionExchange of information between two (or multiple)parties can be effected in various modes. On one extreme,the entire information is generated at one site and thendisseminated to the rest of the group. In another extreme,every party (if possible) computes the information indepen-dent of the others and no one needs to go to the network.Real life, however, often presents scenarios situated in themiddle, i.e., when parties hold partial information and theyneed to both compute and communicate. In fact, manya times, it is possible that computation can be traded offwith communication and vice versa. It so turns out thatthe possibility of such a trade-off can be used to various∗College of Computing, Georgia Tech, [email protected]†Max-Planck-Institut fuer Informatik (MPII), [email protected]‡College of Computing, Georgia Tech, [email protected] to handle resource limitations more efficiently.In this paper we explore one direction for this trade-off, viz.trading computation for communication. First, we surveywhy and when this could be helpful. And next we willsuggest some theoretical techniques that, although awaitingcertain mathematical and algorithmic challenges to be met,could prove extremely helpful.Why Save Communication?Although modern wireless technology has advancedquite rapidly, it is yet to catch up with the remarkable speedof the CPUs that have been achieved. The primary obstaclebehind this lag is the presence of natural physical noisethat any wireless signal has to wade through, especiallyin the domain of long range transmission. Consequently,still now, for many wireless applications, bandwidth is amore priced resource than the processor. Moreover, ascomputing is becoming ubiquitous in nature, and moreand more pervasive applications are surfacing, there is aplethora of devices in the market that are small, wearable orhand-held, connected on wireless and operating on battery;for such devices power consumption is quite critical. Sadly,long range wireless transmission is extremely expensivecompared to on-chip computing as far as the currencyof energy is concerned. For example, according to anobservation made by Pottie and Kaiser, that dates backcouple of years, transmission of one bit over a long rangewireless is equivalent to few thousands of cycles in modernprocessors [10]. If the scenario has changed in next fewyears, it is only to the favor of processing power and speed.Where Can Communication be savedBandwidth and power are the two motivating factors be-hind conserving communication for mobile wireless sys-tems. There are numerous situations in which communica-tion can be saved by additional computation; here is a shortlist:• Compression while transferring files : This is the mostcommon scenario. Large files can be compressed, the1overhead is that of compression and decompressionand the gains are dependent upon the efficiency of thealgorithms used as well as the exact input.• Document Exchange: Consider two parties A and Bupdating a single document. They may hold slightlydifferent version of the same file; if A wants to knowthe contents of B’s document, it may be possible tosmartly compare their edits with a much lower com-munication overhead than transferring the whole file.• Remote Authentication: This is a scenario which isbecoming extremely commonplace given the applica-tion and technology trends. Remote users need to beauthenticated quite often, and the paradigm of pass-word based authentication is gradually being replacedby other authentication mechanisms, such as biomet-rics or key-stroke dynamics and so on. These authenti-cation keys are quite large in size and typically the ap-plications require authentication on a continual basis.Naive implementation of such systems therefore leadsto huge communication overhead resulting just fromthe act of authentication alone. While the large sizeand high entropy of such keys are quite desirable secu-rity features, they poses the bandwidth bottleneck. Itmay be possible to improve the bandwidth requirementof such schemes by carefully modifying the associatedverification protocol, which saves the bandwidth, yetat the same time, retains the benefits of a high-entropyauthentication token. A point to note here is that sim-ple cryptographic hashing of the key will not work.Because, typically, the biometric patterns generated bya person at different times and to different sensors arenot identical, rather close matches. However, a crypto-graphic hash function does not preserve such proxim-ities and therefore the distance between two patternscannot be obtained by comparing their hash digests.• Verification of Mobile Codes and Remote Compu-tations: Internet cookies are no strangers to any onenow. However, installing programs downloaded fromremote locations can be quite sensitive to the securityand privacy issues. It would be really nice if a remotecode came with a certification that it does not performharmful action. As of today, the only certificationattached to such a code is the trustworthiness of theparty from which it has been downloaded. However,a more convincing


Loading Unlocking...
Login

Join to view Trading Processor Cycles for Communication and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Trading Processor Cycles for Communication and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?