GREEDY ASSIGNMENT PROBLEM FOR CONTINUOUS DISTRIBUTEDCLIENTSYSTEM

Abstract

In this paper, we investigate the problem of effectively assigning clients to servers for maximizingtheinteractivity of Distributed modified Algorithm (DIA) . We focus on continuous DIAs that changes their states not only in response to user operations but also due to the passing of time. We analyze the minimumachievable interaction time for DIAs to preserve consistency and provide fairness among clients, and formulatethe client assignment problem as a combinatorial optimization problem. We prove that this problemis NPcomplete. Three heuristic assignment algorithms are proposed and their approximation ratios are theoreticallyanalyzed. Three heuristic assignment algorithms are performance of the algorithms is also experimentallyevaluated using real Internet latency data. Greedy Assignment and Distributed-Modify Assignment algorithms generally produce near optimal interactivity and significantly reduce the interaction time between clientscompared to the intuitive algorithm that assigns each client to its nearest server. They produce near optimal interactivity and significantly reduce the interaction time between clients.