IPRI - www.ipri.kiev.ua -  IPRI - www.ipri.kiev.ua -
Title (journal) Data Rec., Storage & Processing. — 2010. — Vol. 12, N 2.
Pages 37-44
PDF, full text
Title (article) Combinatorial Optimization Algorithm for Logical Interlink Structure of Decentralized System
Authors Krayevoy A.S., Tymoshenko Y.О.
Kiev, Ukraine
Annotation A formal mathematical model of a problem for optimization of logical interlink structure of decentralized system is proposed. It is shown that optimization yields structures which are effective in regard to resources spent on logical operations in a predetermined network environment. Typical restrictions allowing to assure scalability and high robustness of the system under inhomogeneous load are discussed. Es92 timation of problem complexity is performed, and genetics algorithm of finding on approximate solution is proposed. Fig.: 1. Refs: 12 titles.
Key words decentralized computing system, overlay network, spectral graph theory, quasihomogeneous networks, graph Laplacian, genetic algorithm.
References 1. Тимошенко Ю. Огляд і класифікація програмно-апаратних засобів побудови розподіленихобчислювальних систем / Ю. Тимошенко, А. Краєвий // Наукові вісті НТУУ «КПІ». — 2006. — № 2 (46) — С. 37–49.
2. Aberer K. Multifaceted Simultaneous Load Balancing in DHT-based P2P Systems: A New Game with Old Balls and Bins / K. Aberer, A. Datta, M. Hauswirth // Self-* Properties in Complex Information Systems. — Amer. Math. Soc, 2005.
3. Schlosser M. HyperCuP — Hypercubes, Ontologies and Efficient Search on P2P Networks / M. Schlosser, M. Sintek, S. Decker, W. Nejdl // LNCS. — 2002. — Vol. 2530. –– Р. 112–124.
4. Load Balancing in Dynamic Structured Peer-to-Peer Systems / [S. Surana, B. Godfrey, K. Lakshminarayanan et al] // Perform. Eval. — 2006. — Vol. 63. — Р. 217–240.
5. Краевой А., Тимошенко Ю. Виртуальные топологии симметричных распределенных вычислительных систем // Труды III международной конференции «Параллельные вычисления и задачи управления» РАСО’2006 памяти И.В. Прангишвили. — М.: Институт проблем управления им. В.А.Трапезникова РАН, 2006.
6. Bassalygo L.A. Asymptotically Optimal Switching Circuits / L.A. Bassalygo // Problems Inform. Transmission. — 1981. — Vol. 17. –– P. 206–211.
7. Chung F.R.K. Graham R.L. Maximum Сuts and Quasi-Random Graphs // Random Graphs. – Frieze A. Luczak T. eds. — New York: John Wiley and Sons, 1992.— Р. 23–34.
8. Alon N. Routing Permutations on Graphs via Matchings / N. Alon, F.R.K. Chung, R.L. Graham // SI AM J. Disc. Math. — 1994. — Vol. 7. –– Р. 513–530.
9. Краевой А. Подходы в оценке устойчивости сетевых структур // Тезисы 26-й научн.-техн. конф. «Моделювання». — Луганск, 2007. — С. 40–42.
10. Chung F.R.K. On Concentrators, Superconcentrators, Generalizes, and Nonblocking Networks // Bell Systems Tech. J. — 1978. — Vol. 58. –– Р. 1765–1777.
11. Chung F. Spectral Graph Theory / F. Chung // Providence: American Mathematical Society, 1994.
12. Sleijpen G.L.G. der H.A.V. A Jacobi–Davidson Iteration Method for Linear Eigenvalue Problems // SIAM Rev. — 2000.— Vol. 42. —P. 267–293.
Файлы 2009-2-4.pdf