Task swapping networks in distributed systems

References

• G. Aggarwal, R. Motwani, and A. Zhu, The load rebalancing problem, Proceedings of the Fifteenth Annual ACM Symposium on Parallel Algorithms and Architectures, San Diego, CA, 2003, pp. 258–265.
   Google Scholar
• S.B. Akers and B. Krishnamurthy, A group-theoretic model for symmetric interconnection networks, IEEE Trans. Comput. 38 (1989), pp. 555–566.
   Web of Science ®Google Scholar
• N. Biggs, Algebraic Graph Theory, Cambridge University Press, Cambridge, 1974.
   Google Scholar
• A. Björner and F. Brenti, Combinatorics of Coxeter Groups, Springer, New York, NY, 2005.
   Google Scholar
• N.S. Bowen, C.N. Nikolaou, and A. Ghafoor, On the assignment problem of arbitrary process systems to heterogeneous distributed computer systems, Trans. Comput. 41 (1992), pp. 257–273.
   Web of Science ®Google Scholar
• R. Burkard, M. Dell'Amico, and S. Martello, Assignment Problems, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2009.
   Google Scholar
• L. Chen, C.L. Wang, and F.C.M. Lau, Process reassignment with reduced migration cost in grid load rebalancing, IEEE International Symposium on Parallel and Distributed Processing, IPDPS 2008, Miami, FL, 2008, pp. 1–13.
   Google Scholar
• Q. Chen, M. Hsu, U. Dayal, and M. Griss, Multi-agent cooperation, dynamic workflow and XML for e-commerce automation, Proceedings of the Fourth International Conference on Autonomous Agents, Barcelona, Spain, 2000, pp. 255–256.
   Google Scholar
• H. Choi, L. Brunet, and J. How, Consensus-based decentralized auctions for robust task allocation, IEEE Trans. Robot. 25 (2009), pp. 912–926.
   Web of Science ®Google Scholar
• R. Diestel, Graph Theory, 3rd ed., Springer, New York, NY, 2005.
   Google Scholar
• C. Du, X.H. Sun, and M. Wu, Dynamic scheduling with process migration, Proceedings of the Seventh IEEE International Symposium on Cluster Computing and the Grid, Rio de Janeiro, Brazil, 2007, pp. 92–99.
   Google Scholar
• H. El-Rewini and T.G. Lewis, Distributed and Parellel Computing, Manning Publications, Greenwich, CT, 1998.
   Google Scholar
• T. Enokido and M. Takizawa, Group communication protocol for autonomic computing, Proceedings of the 11th International Conference on Parallel and Distributed Systems, Fuduoka, Japan, 2005, pp. 443–447.
   Google Scholar
• C. Enyioha, D. Tarraf, L. Li, and J.C. Doyle, On the graph of trees, IEEE Multiconference on Systems and Control, St Petersburg, Russia, 2009, pp. 246–248.
   Google Scholar
• H. Eriksson, Computational and combinatorial aspects of Coxeter groups, Ph.D. thesis, KTH, Stockholm, Sweden, 1994.
   Google Scholar
• X. Feng, B. Chitturi, and H. Sudborough, Sorting circular permutations by bounded transpositions, Adv. Comput. Biol. 680 (2011), pp. 725–736.
   Web of Science ®Google Scholar
• F.S. Foundation, GNU C++ Library. Available at http://gcc.gnu.org/onlinedocs/libstdc++.
   Google Scholar
• J.B. Fraleigh, A First Course in Abstract Algebra, Addison-Wesley, Reading, MA, 1998.
   Google Scholar
• M. Gairing, B. Monien, and A. Woclaw, A faster combinatorial approximation algorithm for scheduling unrelated parallel machines, Theoret. Comput. Sci. 380 (2007), pp. 87–99.
   Web of Science ®Google Scholar
• A. Garsia, The Saga of Reduced Factorizations of Elements of the Symmetric Group, Publications du LaCIM 29, Université du Québec á Montréal, Montreal, QC, Canada 2002.
   Google Scholar
• Y. Gong, M. Nakamura, T. Matsumura, and K. Onaga, A distributed parallel genetic local search with tree-based migration on irregular network topologies, IEICE Trans. Fundam. Electron. Commun. Comput. Sci. E87-A (2004), pp. 1377–1385.
   Google Scholar
• Y. Gong, M. Nakamura, and S. Tamaki, Parallel genetic algorithms on line topology of heterogeneous computing resources, GECCO ’05, Proceedings of the 2005 Conference on Genetic and Evolutionary Computation, Washington, DC, 2005, pp. 1447–1454.
   Google Scholar
• A. Grigoriev, M. Sviridenko, and M. Uetz, Machine scheduling with resource dependent processing times, Math. Program. 110 (2007), pp. 209–228.
   Web of Science ®Google Scholar
• M. Griss, Q. Chen, G. Bolcer, R. Kessler, and L. Osterweil, Agents and workflow – an intimate connection, or just friends? Proceedings of the Technology of Object-Oriented Languages and Systems, 1999, pp. 558–562.
   Google Scholar
• W.J. Gutjahr, M. Hitz, and T.A. Mueck, Task assignment in Cayley interconnection topologies, Parallel Comput. 23 (1997), pp. 1429–1460.
   Web of Science ®Google Scholar
• M. Heydemann, Cayley graphs and interconnection networks, in Graph Symmetry: Algebraic Methods and Applications, G. Hahn and G. Sabidussi, eds., NATO ASI Series C: Mathematical and Physical Sciences, Kluwer Academic Publishers, Dordrecht, The Netherlands, 1997, pp. 167–224.
   Google Scholar
• Y.F. Hu, R.J. Blake, and D.R. Emerson, An optimal migration algorithm for dynamic load balancing, Concurrency Pract. Exp. 10 (1998), pp. 467–483.
   Web of Science ®Google Scholar
• T. Hungerford, Algebra, 2nd ed., Springer-Verlag, New York, NY, 1980.
   Google Scholar
• J. Irving and A. Rattan, Factorizations of permutations into star transpositions, Discrete Math. 309 (2009), pp. 1435–1442.
   Web of Science ®Google Scholar
• N. Jennings and M. Wooldridge, Software agents, IEE Rev. 42 (1996), pp. 17–20.
   Google Scholar
• M. Jerrum, The complexity of finding minimum-length generator sequences, Theoret. Comput. Sci. 36 (1985), pp. 265–289.
   Web of Science ®Google Scholar
• P. Kalinowski and R. Katarzyniak, Methods of task redistribution in multiagent systems, in Agent and Multi-Agent Systems: Technologies and Applications, P. Je¸drzejowicz, N.T. Nguyen, R.J. Howlet, L.C. Jain, eds., Lecture Notes in Computer Science, Springer, Berlin, Vol. 6070, 2010, pp. 72–81.
   Google Scholar
• D. Kim, Representations of task assignments in distributed systems using young tableaux and symmetric groups, preprint (2010). Available at arXiv.org arXiv:1012.1288 [cs.DC], http://arxiv.org/abs/1012.1288.
   Google Scholar
• D.E. Knuth, The Art of Computer Programming. Vol. 3: Sorting and Searching, Addison-Wesley Publishing Company, Reading, MA, 1973.
   Google Scholar
• L. Kramer, L. Barbulescu, and S. Smith, Searching alternate spaces to solve oversubscribed scheduling problems, Tech. Rep. CMU-RI-TR-08-12, Carnegie Mellon University, Pittsburgh, PA, 2008.
   Google Scholar
• S. Lakshmivarahan, J.S. Jwo, and S.K. Dhall, Symmetry in interconnection networks based on Cayley graphs of permutation groups: A survey, Parallel Comput. 19 (1993), pp. 361–407.
   Web of Science ®Google Scholar
• J. Lenstra, D. Shmoys, and É. Tardos, Approximation algorithms for scheduling unrelated parallel machines, Math. Program. 46 (1990), pp. 259–271.
   Web of Science ®Google Scholar
• A. Lihu and S. Holban, Top five most promising algorithms in scheduling, 5th International Symposium on Applied Computational Intelligence and Informatics, SACI 2009, IEEE, Timisoara, Romania, 2009, pp. 397–404.
   Google Scholar
• L. Liu and D. Shell, A distributable and computation-flexible assignment algorithm: From local task swapping to global optimality, 2012 Robotics: Science and Systems Conference (RSS), Sydney, Australia, 2012.
   Google Scholar
• G. Mackiw, Permutations as products of transpositions, Amer. Math. Monthly 102 (1995), pp. 438–440.
   Web of Science ®Google Scholar
• D.S. Miloj´ičić, F. Douglis, Y. Paindaveine, R. Wheeler, and S. Zhou, Process migration, ACM Comput. Surv. 32 (2000), pp. 241–299.
   Google Scholar
• D. Neuenschwander, On the representation of permutations as products of transpositions, Elem. Math. 56 (2001), pp. 1–3.
   Google Scholar
• H.S. Nwana, Software agents: An overview, Knowl. Eng. Rev. 11 (1996), pp. 205–244.
   Web of Science ®Google Scholar
• I. Pak, Reduced decompositions of permutations in terms of star transpositions, generalized Catalan numbers and k-ARY trees, Discrete Math. 204 (1999), pp. 329–335.
   Web of Science ®Google Scholar
• S. Ramakrishnan, I.H. Cho, and L.A. Dunning, A close look at task assignment in distributed systems, INFOCOM ’91, IEEE, Bal Harbour, FL, 1991, pp. 806–812.
   Google Scholar
• J. Robinson, S.H. Russ, B. Heckel, and B. Flachs, A task migration implementation of the message-passing interface, Proceedings of the 5th IEEE International Symposium on High Performance Distributed Computing, Syracuse, NY, 1996, pp. 61–68.
   Google Scholar
• J.E. Rowe, M.D. Vose, and A.H. Wright, Group properties of crossover and mutation, Evol. Comput. 10 (2002), pp. 151–184.
   PubMed Web of Science ®Google Scholar
• K.G. Shin and M.S. Chen, On the number of acceptable task assignments in distributed computing systems, IEEE Trans. Comput. 39 (1990), pp. 99–110.
   Web of Science ®Google Scholar
• D. Shmoys and É. Tardos, An approximation algorithm for the generalized assignment problem, Math. Program. 62 (1993), pp. 461–474.
   Web of Science ®Google Scholar
• L. Stacho and I. Vrt'o, Bisection width of transposition graphs, Discrete Appl. Math. 84 (1998), pp. 221–235.
   Google Scholar
• K.P. Sycara, Multiagent systems, AI Mag. 19 (1998), pp. 79–92.
   Web of Science ®Google Scholar
• A.S. Tanenbaum, Distributed Operating Systems, Prentice Hall, Upper Saddle River, NJ, 1995.
   Google Scholar
• B.E. Tenner, The combinatorics of reduced decompositions, Ph.D. thesis, MIT, Cambridge, 2006.
   Google Scholar
• M. Tompkins, Optimization techniques for task allocation and scheduling in distributed multi-agent operations, Ph.D. thesis, Massachusetts Institute of Technology, 2003.
   Google Scholar
• J. Vokřínek, A. Komenda, and M. Pěchouček, Abstract architecture for task-oriented multi-agent problem solving, IEEE Trans. Syst. Man Cybern. C, Appl. Rev. 41 (2011), pp. 31–40.
   Web of Science ®Google Scholar
• M.M. Zavlanos and G.J. Pappas, Distributed formation control with permutation symmetries, Proceedings of the 46th IEEE Conference on Decision and Control, New Orleans, LA, 2007, pp. 2894–2899.
   Google Scholar
• M.M. Zavlanos, L. Spesivtsev, and G.J. Pappas, A distributed auction algorithm for the assignment problem, Proceedings of 47th IEEE Conference on Decision and Control, Cancún, QR, s, pp. 1212–1217.
   Google Scholar
• H.L. Zhang, C.H.C. Leung, and G.K. Raikundalia, Classification of intelligent agent network topologies and a new topological description language for agent networks, in Intelligent Information Processing III, Z. Shi, K. Shimoharar, and D. Feng, eds., Springer, New York, 2006, Vol. 228, pp. 21–31.
   Google Scholar
• X. Zheng and S. Koenig, K-swaps: Cooperative negotiation for solving task-allocation problems, Proceedings of the 21st International Joint Conference on Artificial Intelligence, Pasadena, CA, 2009, pp. 373–378.
   Google Scholar
• H. Zhu and Z. Sun, New classes of interconnection topology structures and their properties, Wuhan Univ. J. Nat. Sci. 1 (1996), pp. 371–385.
   Google Scholar
• Q. Zhu, Topologies of agents interactions in knowledge intensive multi-agent systems for networked information services, Adv. Eng. Inf. 20 (2006), pp. 31–45.
   Web of Science ®Google Scholar