IPRI - www.ipri.kiev.ua -  IPRI - www.ipri.kiev.ua -
Раздел [RUS]
Регистрация, хранение и обраб. данных. — 2009. — Т. 11, № 2.
[UKR]
Реєстрація, зберігання і оброб. даних. — 2009. — Т. 11, № 2.
[ENG]
Data Rec., Storage & Processing. — 2009. — Vol. 11, N 2.
Страницы 37-44
PDF, full text
Заглавие [RUS]
Алгоритм комбинаторной оптимизации структуры логических связей децентрализованной системы
[UKR]
Алгоритм комбінаторної оптимізації структури логічних зв’язків децентралізованої системи
[ENG]
Combinatorial Optimization Algorithm for Logical Interlink Structure of Decentralized System
Авторы [RUS]
А. С. Краевой, Ю. А. Тимошенко
[UKR]
Краєвий А.С., Тимошенко Ю.О.
[ENG]
Krayevoy A.S., Tymoshenko Y.О.
Kiev, Ukraine
Аннотация [RUS]
Предложена формальная математическая модель задачи оптимизации структуры логических связей децентрализованной системы. Показано, что оптимизация позволяет получить структуры, эффективные с точки зрения затрат на реализацию логических операций в заданном сетевом окружении. Рассмотрены типичные ограничения, позволяющие гарантировать масштабируемость и высокие показатели устойчивости системы при неоднородной нагрузке. Проведена оценка сложности задачи и предложен генетический алгоритм нахождения приближенного решения.
[UKR]
Запропоновано формальну математичну модель задачі оптимізації структури логічних зв’язків децентралізованої системи. Показано, що оптимізація дозволяє отримати структури, які будуть ефективними з точку зору витрат на реалізацію логічних операцій у заданому мережевому середовищі. Розглянуто типові обмеження, які дозволяють гарантувати можливість масштабування та забезпечення високих показників стабільності роботи системи при нерівномірному завантаженні. Проведено оцінку складності задачі та запропоновано генетичний алгоритм знаходження наближеного розв’язку. Іл.: 1. Бібліогр.: 12 найм.
[ENG]
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.
Ключевые слова [RUS]
децентрализованные вычислительные системы, оверлейная сеть, спектральная теория графов, квазиоднородные сети, Лапласиан графа, генетический алгоритм.
[UKR]
децентралізовані обчислювальні системи, оверлейна мережа, спектральна теорія графів, квазіоднорідні мережі, Лапласіан графа, генетичний алгоритм.
[ENG]
decentralized computing system, overlay network, spectral graph theory, quasihomogeneous networks, graph Laplacian, genetic algorithm.
Ссылки 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