
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

Bounds on the ClientServer Incremental Computing
Chochin LIN Dawei WANG Tsansheng HSU
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E89A
No.5
pp.11981206 Publication Date: 2006/05/01
Online ISSN: 17451337
DOI: 10.1093/ietfec/e89a.5.1198
Print ISSN: 09168508 Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications) Category: Keyword: parallel and distributed computing, network computing, clientserver, Internet computing, incremental computing, lower and upper bounds,
Full Text: PDF(534KB)>>
Summary:
We discuss the problem of finding a dominant sequence for sending input data items from a lowend 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 sequencefinding problem is NPhard 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 sequencefinding 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.

