رنگ‌آمیزی گروندی خود‌ تثبیت‌کننده با استفاده از نظریه بازی‌ها و یافتار مرتب‌سازی

نوع مقاله: مقاله پژوهشی

نویسندگان

دانشگاه تهران

چکیده

خرابی گذرا در سیستم‌های توزیع‌شده در شرایط مختلفی مانند خرابی پردازه‌ها و حمله‌های امنیتی رخ می‌دهد. یک الگوریتم خود تثبیت‌کننده با شروع از هر حالت دلخواه، در زمان متناهی به حالت قانونی می‌رسد و در مقابل خرابی گذرا مقاوم است. در این مقاله، نخست، برای مسئلۀ رنگ‌آمیزی گروندی، اولین الگوریتم قطعی خود تثبیت‌کننده مبتنی بر نظریه بازی‌ها را ارائه می‌کنیم. در این الگوریتم، که از قابلیت اجرا روی شبکه‌های ناشناس برخوردار است، برای کاهش تعداد رنگ‌های مصرفی، از یافتارهای مرتب‌سازی استفاده می‌کنیم. با به‌کارگیری تعادل نش، ثابت می‌کنیم که الگوریتم روی شبح مرکزی با پیچیدگی زمانی O(m) به رنگ‌آمیزی گروندی همگرا می‌شود که در آن m تعداد یال‌های شبکه است. نتایج شبیه‌سازی روی شبکه‌های مستقل از مقیاس، شبکه‌های تصادفی و شبکه‌های دنیای کوچک حاکی از آن است که به‌کارگیری یافتارهای مرتب‌سازی نسبت به عدم استفاده از آن‌ها موجب کاهش تعداد رنگ‌ها تا 18% و بهبود سرعت همگرایی به جواب تا 5% می‌گردد.

کلیدواژه‌ها


[1]

N. A. Lynch, “Distributed Algorithms, Morgan Kaufmann,” 1996.##

[2]

L. Wang and R. Ranjan, “Processing distributed internet of things data in clouds,” IEEE Cloud Computing, vol. 2, pp.     76–80, 2015.##

[3]

D. Peleg, “Distributed Computing: A Locality-Sensitive Approach,” SIAM, 2000.##

[4]

N. Guellati and H. Kheddouci, “A survey on self-stabilizing algorithms for independence, domination, coloring, and matching in graphs,” Journal of Parallel and Distributed Computing, vol. 70, pp. 406–415, 2010.##

[5]

L. H. Yen, J. Y. Huang, and V. Turau, “Designing self-stabilizing systems using game theory,” ACM Trans. Auton. Adapt. Syst., vol. 11, pp. 1–27, 2016.##

[6]

L. H. Yen and Z. L. Chen, “Game-theoretic approach to self-stabilizing distributed formation of minimal multi-dominating sets,” IEEE Trans. Parallel Distrib. Syst., vol. 25, pp.         3201–3210, 2014.##

[7]

E. W. Dijkstra, “Self-stabilizing systems in spite of distributed control,” Communications of the ACM, vol. 17, pp. 643–644, 1974.##

[8]

S. Devismes and C. Johnen, “Silent self-stabilizing BFS tree algorithms revisited,” Journal of Parallel and Distributed Computing, vol. 97, pp. 11–23, 2016.##

[9]

J. Cohen, J. Lefèvre, K. Maâmra, L. Pilard and D. Sohier, “A self-stabilizing algorithm for maximal matching in anonymous networks,” Parallel Processing Letters, vol. 26, pp. 49–59, 2016.##

[10]

Y. Fu and X. Xiaoping, “Self-stabilized distributed network distance prediction,” IEEE/ACM Transactions on Networking, vol. 25, pp. 451–464, 2017.##

[11]

L. Blin and S. Tixeuil, “Compact deterministic self-stabilizing leader election on a ring,” Distributed Computing, vol. 1998, pp. 1-28, 2017.##

[12]

A. K. Datta, S. Devismes, and L. L. Larmore, “Self-stabilizing silent disjunction in an anonymous network,” Theoretical Computer Science, vol. 665, pp. 51–72, 2017.##

[13]

J. Behnamian, “Graph colouring-based algorithm to parallel jobs scheduling on parallel factories,” International Journal of Computer Integrated Manufacturing, vol. 29, pp. 622–635, 2015.##

[14]

B. Yüceoğlu, G. Şahin and S. P. van Hoesel, “A column generation based algorithm for the robust graph coloring problem,” Discrete Applied Mathematics, vol. 217, pp.340–352, 2017.##

[15]

C. Zhao, X. Xu, Z. Gao, and L. Huang, “A coloring-based cluster resource allocation for ultra dense network,” in IEEE International Conference on Signal Processing, Communications and Computing, Hong Kong, pp. 1-5, 2016.##

[16]

S. Basloom, A. Nazar, G. Aldabbagh, M. Abdullah, and N. Dimitriou, “Resource allocation using graph coloring for dense cellular networks,” in International Conference on Computing, Networking and Communications, Kauai, pp. 1-5, 2016.##

[17]

L. Barenboim, M. Elkin, S. Pettie, and J. Schneider, “The locality of distributed symmetry breaking,” Journal of the ACM (JACM), vol. 63, 2016. doi: 10.1145/2903137##

[18]

A. S. Sairam, S. Roy, and R. Sahay, “Coloring networks for attacker identification and response,” Security and Communication Networks, vol. 8, pp. 751–768, 2015.##

[19]

B. L. Hartnell and C. M. Mynhardt, "Independent protection in graphs," Discrete Mathematics, vol. 335, pp. 100–109, 2014.##

[20]

M. Gradinariu and S. Tixeuil, “Self-stabilizing vertex coloring of arbitrary graphs,” in International conference on Principles of Distributed Systems, Paris, pp. 55-70, 2000.##

[21]

A. Mansouri and M. S. Bouhlel, “Efficient self-stabilizing grundy coloring algorithms,” in 2016 Future Technologies Conference FTC 2016, San Francisco, pp. 199-205, 2016.##

[22]

P. N. Panagopoulou and P. G. Spirakis, “A game theoretic approach for efficient graph coloring,” in International Symposium on Algorithms and Computation, Berlin, pp. 183-195, 2008.##

[23]

I. Chatzigiannakis, C. Koninis, P. N. Panagopoulou, and P. G. Spirakis, “Distributed game-theoretic vertex coloring,” in International Conference On Principles Of Distributed Systems, Tozeur, pp. 103-118, 2010.##

[24]

A. R´enyi. and P. Erdos, “On random graphs,” Publ. Math. Debr., vol. 6, pp. 290–297, 1959.##

[25]

D. J. Watts and S. H. Strogatz, “Collective dynamics of ‘small-world’ networks,” Nature, vol. 393, pp. 440–442, 1998.##

[26]

A.-L. Barabási and R. Albert, “Emergence of scaling in random networks,” Science, vol. 286, pp. 509–512, 1999.##

[27]

D. J. A. Welsh and M. B. Powell, “An upper bound for the chromatic number of a graph and its application to timetabling problems,” The Computer Journal, vol. 10, pp. 85–86, 1967.##

[28]

S. T. Hedetniemi, D. P. Jacobs, and P. K. Srimani, “Linear time self-stabilizing colorings,” Information Processing Letters, vol. 87, pp. 251–255, 2003.##

[29]

W. Goddard, S. T. Hedetniemi, D. P. Jacobs, and P. K. Srimani, “Self-stabilizing algorithm for orderings and colorings,” Int. J. Found. Comput. Sci., vol. 16, pp. 19–36, 2005.##

[30]

S. Bernard, S. Devismes, M. G. Potop-Butucaru, and S. Tixeuil, “Optimal deterministic self-stabilizing vertex coloring in unidirectional anonymous networks,” in IEEE International Symposium on Parallel & Distributed Processing, New York, pp. 1-8, 2009.##

[31]

S. Bernard, S. Devismes, K. Paroux, M. Potop-Butucaru, and S. Tixeuil, “Probabilistic self-stabilizing vertex coloring in unidirectional anonymous networks,” in International Conference on Distributed Computing and Networking, Kolkata, pp.167-177, 2010.##

[32]

A. Kosowski and Ł. Kuszner, “Self-stabilizing algorithms for graph coloring with improved performance guarantees,” in Artificial Intelligence and Soft Computing, London, pp.    1150-1159, 2006.##

[33]

W. Hasenplaugh, T. Kaler, T. B. Schardl, and C. E. Leiserson, “Ordering heuristics for parallel graph coloring,” in Proceedings of the 26th ACM Symposium on Parallelism in Algorithms and Architectures , Prague, pp. 166-177, 2014.##

[34]

C. A. Christen and S. M. Selkow, “Some perfect coloring properties of graphs,” Journal of Combinatorial Theory, Series B, vol. 27, pp. 49–59, 1979.##

[35]

V. Bilò, A. Fanelli, M. Flammini, and L. Moscardelli, “Graphical congestion games,” Algorithmica, vol. 61, pp.    274–297, 2011.##

[36]

D. Monderer and L. S. Shapley, “Potential games,” Games and Economic Behavior, vol. 14, pp. 124–143, 1996.##

[37]

J. C. Miller and A. Hagberg, “Efficient generation of networks with given expected degrees,” in International Workshop on Algorithms and Models for the Web-Graph, Atlanta, pp.     115-126, 2011.##