Title:

Wheel գրաֆների վրա հիմնված k-հուսալիությամբ gossip գրաֆներ ; k- толерантные gossip графы основанные на wheel графов

Author:

Հովնանյան Վիլյամ ; Պողոսյան Սուրեն ; Պողոսյան Վահագն ; Овнанян Вильям ; Погосян Сурен ; Погосян Ваагн

Type:

Հոդված

Abstract:

Gossip խնդիրը (հեռախոսների խնդիրը) ինֆորմացիայի տարածման խնդիր է, որտեղ հաղորդակցության ցանցի n հանգույցներից յուրաքանչյուրը տիրապետում է որևէ եզակի ինֆորմացիայի, որը պետք է փոխանցվի բոլոր մնացած հանգույցներին' օգտագործելով հանգույցների զույգերի միջև երկկողմանի հաղորդակցությունը: Տրված երկու հանգույցների միջև զանգի ժամանակ դրանք փոխանակում են այդ պահին իրենց հայտնի ողջ ինֆորմացիան: Այս հոդվածում մենք դիտարկում ենք k հուսալիությամբ gossip խնդիրը, որը ընդհանուր gossip խնդրի ընդհանրացումն է, երբ թույլատրված են զանգերի ամենաշատը k պատահական խափանումներ: Խնդիրը կայանում է զանգերի այն т (n, k) նվազագույն քանակը գտնելու մեջ, որի դեպքում կապահովվի ինֆորմացիայիամբողջական տարածումը: Մենք նախագծել ենք k հուսալիությամբ վթարակայուն gossipսխեմա (զանգերի հաջորդականություն), որպեսզի գտնենք т (n, k)-ի համար վերինսահմաններ, որոնք կբարելավեն նախորդ արդյունքները n-ի և k-ի որոշակի փոքրարժեքների դեպքում:
; Проблемой gossip (проблемой телефонов) является проблема распространения информации, где каждый из n узлов сети связи имеет уникальный фрагмент информации, который должен быть передан всем остальныем узлам с помощью двусторонней связи (телефонные звонки) между парами узлов. После вызова между данными двумя узлами, они обмениваются всей информацией, известной им в данный момент. В этой статье, мы исследуем k-отказоустойчивую gossip проблему, которая является обобщением задачи gossip, где наиболее k произвольных сбойных вызовов разрешены. Проблема в том, чтобы найти минимальное количество звонков т (n, k), необходимых для обеспечения полного распространения информации. М ы построили k-отказоустойчивую gossip схему (последовательности вызовов) с целью найти верхние границы т (n, k ), которая улучшает ранее известные результаты для некоторых малых значений n и k.