Bounds on the Client-Server Incremental Computing

Cho-chin LIN  Da-wei WANG  Tsan-sheng HSU  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E89-A   No.5   pp.1198-1206
Publication Date: 2006/05/01
Online ISSN: 1745-1337
DOI: 10.1093/ietfec/e89-a.5.1198
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
parallel and distributed computing,  network computing,  client-server,  Internet computing,  incremental computing,  lower and upper bounds,  

Full Text: PDF(534KB)>>
Buy this Article

We discuss the problem of finding a dominant sequence for sending input data items from a low-end client to a server for computational intensive tasks under the realistic assumption of unpredictable communication behavior. Under this assumption, the client has to send the input data items using a specified sequence to maximize the number of computations performed by the server at any time. The sequence-finding problem is NP-hard for the general case. In this paper, we address three fundamental and useful applications: the product of two polynomials, matrices multiplication and Fast Fourier Transform. We show that the sequence-finding problems of the three applications can be solved optimally in linear time. However, we also show counter examples to rule out any possibility of finding a dominant sequence for sparse cases of the three applications. Finally, a simulation is conducted to show the usefulness of our method.