Researches On Probing-based Task Assignment

Task assignment is a classical problem in computer science. Its many sub-problems still remain unresolved. Research on these problems is very valuable in both theory and application.This dissertation focuses on task assignment of (N, m) distributed systems and distributed server systems. The main innovative contributions of this dissertation include:Defines (N, m) distributed system model. Some previous researches have presented the concept on (N, m) distributed systems, but not complete. This dissertation analyzes the aspects of (N, m) distributed systems in detail, including reward/penalty dependency, homogeneous / heterogeneous and task choosing policies, these aspects are very helpful for describing the model accurately.Proposes two task assignment algorithms for (N, m) distributed systems. There are two classes of task assignment algorithms for (N, m) distributed systems, namely, dynamic algorithms and searching algorithms. Previous researches focuse on dynamic algorithms, and they have an important limitation, that is, the reward rate of optima r* is no less than 0.5. These two algorithms presented in this dissertation fall into these two classes respectively, both of them overcome limitation of r*.Get correctness proof of given algorithms. The first algorithm is proved to be correct by Markov chain. For the second algorithm, Markov chain is not applicable. Using divide-and-conquer and maximum finding, we develope a more simple and practical method and partly prove the algorithm. Furthermore, this method is expected to be applied on more generalized situations. Two assistant algorithms are also presented and analyzed.Analyze performance of given algorithms. We point out that the first algorithm is more efficiency than previous algorithms on the basis of experiments. We also point out that the second algorithm has the lowest time complexity in the same class of algorithms.Define distributed server system model. This dissertation analyzes many aspects of distributed server systems, especially long-tail distribution of task length. Many algorithms are applicable for this model, including random, round-robin, central-queue and TAGS. Under the requirement of server-level fairness, this dissertation presents performance computation equations for some algorithms. Expansion limitation of TAGS is also pointed out on the basis of some experiments.Integrating TAGS and central-queue, this dissertation presents three enhanced algorithms that fall into two classes. Performance of the former two algorithms is analyzed. For the last algorithm, this dissertation compares it with other algorithms through simulation.Present a parameter setting algorithm that is helpful for both TAGS and our algorithms.