D:\sbornik\...\Final.DVI


Mathematical Problems of Computer Science 41, 15{22, 2014.

M ethod of Local I nter change for the I nvestigation of

Gossip P r oblems: par t 2

V ilya m H . H o vn a n ya n , S u r e n S . P o g h o s ya n a n d V a h a g n S . P o g h o s ya n

Institute for Informatics and Automation Problems of NAS RA

williamhovnanyan@gmail.com, psuren55@yandex.ru, povahagn@gmail.com

Abstract

The method of construction of Gossip graphs providing a full information exchange
with minimal number of calls in minimum time is described. The basis for the graphs
of the presented class is the subgraph of canonical form obtained from NOHO graphs
by applying the operation of local interchange on them developed by us in [19].

Keywords: Graphs, Networks, Telephone problem, Gossip problem.

1 . In t r o d u c t io n

Go s s ip in g is o n e o f t h e b a s ic p r o b le m s o f in fo r m a t io n d is s e m in a t io n in c o m m u n ic a t io n n e t -
wo r ks . Th e g o s s ip p r o b le m ( a ls o kn o wn a s a t e le p h o n e p r o b le m ) is a t t r ib u t e d t o A . B o yd ( s e e
e .g . [1 ] fo r r e vie w) , a lt h o u g h t o t h e b e s t kn o wle d g e o f t h e r e vie we r s , it wa s ¯ r s t fo r m u la t e d
b y R . Ch e s t e r s a n d S . S ilve r m a n ( U n iv. o f W it wa t e r s r a n d , u n p u b lis h e d , 1 9 7 0 ) . Co n s id e r a
s e t o f n p e r s o n s ( n o d e s ) e a c h o f wh ic h in it ia lly kn o ws s o m e u n iqu e p ie c e o f in fo r m a t io n t h a t
is u n kn o wn t o t h e o t h e r s , a n d t h e y c a n m a ke a s e qu e n c e o f t e le p h o n e c a lls t o s p r e a d t h e in -
fo r m a t io n . D u r in g a c a ll b e t we e n t h e g ive n t wo n o d e s , t h e y e xc h a n g e t h e wh o le in fo r m a t io n
kn o wn t o t h e m a t t h a t m o m e n t . Th e p r o b le m is t o ¯ n d a s e qu e n c e o f c a lls wit h m in im u m
le n g t h ( m in im a l g o s s ip s c h e m e ) , b y wh ic h a ll t h e n o d e s will kn o w a ll p ie c e s o f a in fo r m a t io n
( c o m p le t e g o s s ip in g ) . It h a s b e e n s h o wn in n u m e r o u s wo r ks [1 ]{ [4 ] t h a t t h e m in im a l n u m b e r
o f c a lls is 2 n ¡ 4 wh e n n ¸ 4 a n d 1 , 3 fo r n = 2 ; 3 , r e s p e c t ive ly. S in c e t h e n m a n y va r ia t io n s
o f g o s s ip p r o b le m h a ve b e e n in t r o d u c e d a n d in ve s t ig a t e d ( s e e e .g . [5 ]{ [1 5 ]) .

A n o t h e r va r ia n t o f Go s s ip p r o b le m c a n b e fo r m u la t e d b y c o n s id e r in g t h e m in im u m
a m o u n t o f t im e r e qu ir e d t o c o m p le t e g o s s ip in g a m o n g n p e r s o n s , wh e r e t h e c a lls b e t we e n
t h e n o n -o ve r la p p in g p a ir s o f n o d e s c a n t a ke p la c e s im u lt a n e o u s ly a n d e a c h c a ll r e qu ir e s o n e
u n it o f t im e ( [1 6 ]{ [1 8 ]) .

Ob vio u s ly, t h e g o s s ip p r o b le m c a n b e e a s ily m o d e le d a s a g r a p h , wh o s e ve r t ic e s r e p r e s e n t
p e o p le in g o s s ip s c h e m e a n d e d g e s r e p r e s e n t c a lls b e t we e n t h e m ( e a c h o f t h e m h a s we ig h t
wh ic h r e p r e s e n t s t h e m o m e n t wh e n c o m m u n ic a t io n t o o k p la c e ) . S o t h e g r a p h is c a lle d a
c o m p le t e g o s s ip g r a p h if t h e r e a r e a s c e n d in g p a t h s b e t we e n a ll p a ir s o f ve r t ic e s o f t h is g r a p h .

In t h is p a p e r we c o n t in u e t o c o n s id e r t h e m e t h o d s o f lo c a l in t e r c h a n g e o n g o s s ip g r a p h s
wh ic h a r e p a r t ic u la r c a s e s o f o p e r a t io n s d e ¯ n e d in [1 ] a n d a r e d e ¯ n e d a n d d e s c r ib e d in [1 9 ].
In s e c t io n 2 we p r e s e n t a n e w u s e c a s e o f t h e s e o p e r a t io n s c o n c e r n in g t h e m a xim u m n u m b e r

1 5



1 6 Method of Local Interchange for the Investigation of Gossip Problems: part 2

o f ve r t ic e s in m in im u m g o s s ip s c h e m e s wit h a m in im u m g o s s ip in g t im e , a ls o d e s c r ib e t h e
va r ia t io n s o f g o s s ip s c h e m e d e p e n d in g o n t h e s iz e o f b a s is .

2 . Ma xim u m n u m b e r o f ve r t ic e s in m in im u m g o s s ip g r a p h wit h m in im u m
g o s s ip in g t im e

In t h is s e c t io n we a r e g o in g t o in t r o d u c e a n e w u s e c a s e o f o p e r a t io n s o f lo c a l in t e r c h a n g e
wh ic h a r e d e s c r ib e d in [1 9 ]. It h e lp s u s t o c o n s t r u c t a g o s s ip s c h e m e wit h a m in im u m n u m b e r
o f e d g e s a n d m in im u m g o s s ip in g t im e ( w.l.o .g . m in im u m g o s s ip s c h e m e / g r a p h ) . P a r t ic u la r ly,
we will u s e t h e m t o o b t a in a c a n o n ic a l fo r m o f b a s is fo r m in im u m g o s s ip s c h e m e .

In [2 0 ] t h e c la s s o f N OH O g r a p h s wa s d e s c r ib e d , wh ic h we r e g o s s ip g r a p h s wit h n ve r t ic e s
a n d 2 n ¡ 4 c a lls , wh e r e n o o n e fr o m t h e p a r t ic ip a n t s o f g o s s ip p r o c e s s lis t e n s t o it s o wn
in fo r m a t io n . Th e m in im u m g o s s ip g r a p h s b a s e d o n N OH O g r a p h s we r e c o n s t r u c t e d ¯ r s t
in [2 0 ]. In [2 1 ], t h is p r o b le m wa s c o n s id e r e d a n d a wr o n g in fe r e n c e wa s m a d e a b o u t t h e
s t r u c t u r e o f t h e m in im u m g o s s ip s c h e m e . A c c o r d in g t o it , a ll m in im u m g o s s ip s c h e m e s
c o n s is t o f a c u b e a n d e ig h t m in im u m b r o a d c a s t t r e e s a t t a c h e d t o it s c o r n e r p o in t s . L a t e r in
[8 ], t h is s t a t e m e n t wa s n e g a t e d a n d it wa s s h o wn t h a t it wa s t h e o n ly p a r t ic u la r c a s e o f t h e
s t r u c t u r e o f m in im u m g o s s ip g r a p h s . In g e n e r a l, t h e in n e r ke r n e l o f t h e g o s s ip g r a p h wit h
2 n ¡ 4 c a lls , wh ic h we r e p r e s e n t e d in [8 ] a s a p o s e t o f t h e e d g e s o f g r a p h a n d r e p r e s e n t s t h e ir
r e la t io n s ( la t e r a l g r a p h ) , c o u ld b e is o m o r p h ic t o c u b e , " t wis t e d " c u b e a n d p-g r id -ke r n e l. In
t h e c u r r e n t s e c t io n we a r e g o in g t o p r e s e n t d i®e r e n t wa ys o f c o n s t r u c t io n o f t h e m in im u m
g o s s ip s c h e m e s . In [2 1 ] a n d [8 ] it wa s s h o wn t h a t t h e t im e r e qu ir e d t o p e r fo r m g o s s ip in g
wit h m in im u m n u m b e r o f c a lls a n d m in im u m t im e ( in o t h e r wo r d s - wit h m in im u m n u m b e r
o f r o u n d s ) is a t le a s t 2 dlo g 2 ne ¡ 3 . Th e m e t h o d s t h a t a llo w t o c o n s t r u c t m in im u m g o s s ip
s c h e m e s we r e a ls o c o n s id e r e d t h a t h a ve a n u n d e r lyin g b a s is ( a m in im u m g o s s ip g r a p h ) fo r
g o s s ip in g , a n d n e w ve r t ic e s p a r t ic ip a t e in g o s s ip in g b y fo r m in g t h e a t t a c h e d t r e e s wh ic h a r e
c o n n e c t e d t o b a s is . It is o b vio u s , t h a t if t h e b a s is h a s a m in im u m n u m b e r o f e d g e s , t h e n t h e
fu ll g r a p h a ls o wo u ld h a ve t h e s a m e . H e n c e , t h e m a in p r o b le m h e r e is t o p e r fo r m g o s s ip in g
in m in im u m t im e . In o t h e r wo r d s , t h e t im e in wh ic h t h e b a s is p e r fo r m s g o s s ip in g s h o u ld
b e m in im a l a n d t h e c o r r e s p o n d in g a t t a c h e d t r e e s s h o u ld n o t a ®e c t it . S o , o u r g o a l is t o
c o n s t r u c t s u c h g o s s ip s c h e m e s wit h va r ie t y o f s iz e o f t h e b a s is .

A s wa s m e n t io n e d a b o ve , we will s t a r t fr o m t h e a p p lic a t io n o f o p e r a t io n A+ d e ¯ n e d in
[1 9 ] o n t h e N OH O g r a p h s . H e r e a r e s o m e d e ¯ n it io n s fr o m [1 9 ].

De¯nition 1: The permute higher operation P + ( e) on a selected edge e 2 E ( G) connecting
vertices u and v is called a modi¯cation of G, which moves the edges of G adjacent to e as
follows:

Eu ( P
+ ( e ) G) = ½¡u ( e; G) [ ½+v ( e; G) ; ( 1 )

and

Ev ( P
+ ( e ) G) = ½¡v ( e; G) [ ½+u ( e; G) : ( 2 )

Correspondingly, the permute lower operation P ¡ ( e ) moves the edges of G adjacent to e as
follows:

Eu ( P
¡ ( e ) G) = ½+u ( e; G) [ ½¡v ( e; G) ; ( 3 )

and

Ev ( P
¡ ( e ) G) = ½+v ( e; G) [ ½¡u ( e; G) : ( 4 )



V. Hovnanyan, Su. Poghosyan and V. Poghosyan 1 7

De¯nition 2: L et us de¯ne an operation on gossip graphs A+ ( e1; e2; : : : ; ep ) =
( P + ( e1 ) P

+ ( e2 ) : : : P
+ ( ep ) ) (A

¡ ( e1; e2; : : : ; ep ) = ( P
¡ ( e1 ) P

¡ ( e2 ) : : : P
¡ ( ep ) ) ) is the sequence

of permute higher (lower) operations on edges ei, i = 1 ; : : : ; p.

Fig. 1. NOHO graph.

A p p lic a t io n o f o p e r a t io n s A+ ( e1; e2; : : : ; ep ) a n d A
+ ( e01; e

0
2; : : : ; e

0
p ) o n N OH O g r a p h s ( Fig .

1 ) g ive s a s n e w " c a n o n ic a l" fo r m o f m in im u m g o s s ip g r a p h , wh ic h is a m o r e c o n ve n ie n t fo r m
o f b a s is ( Fig 2 ) . H e r e p = 3 a n d t h e e d g e s e1; e2; e3 ( e

0
1; e

0
2; e

0
3 ) a r e h ig h lig h t e d in r e d .

Fig. 2. Minimum gossip graph in \canonical" form.

A ft e r t h is t r a n s fo r m a t io n t h e o b t a in e d g r a p h will b e u s e d a s a b a s is wit h s iz e k = n0=2 ,
wh e r e n0 is t h e n u m b e r o f ve r t ic e s o f t h e b a s is . N o w c o n s id e r t h e n e w s e t o f ve r t ic e s wit h
t h e s a m e s iz e t h a t c o m m u n ic a t e s wit h t h e g ive n s e t b y in c o m in g a n d o u t g o in g c a lls . L e t t h e
n u m b e r o f r o u n d s b y wh ic h s u c h a c o m m u n ic a t io n t a ke s p la c e b e d e n o t e d b y r. Ob vio u s ly,
t h e n u m b e r o f r o u n d s t o p e r fo r m g o s s ip in g will b e a t le a s t 2 r + k. Th is e s t im a t e will b e
r e a c h e d o n ly if t h e a t t a c h e d t r e e s wo u ld n o t a ®e c t g o s s ip in g p r o c e s s o f b a s is . It m e a n s ,
t h a t t h e p r o c e s s o f in vo lvin g n e w ve r t ic e s in g o s s ip in g s h o u ld b e in p a r a lle l wit h t h e m a in
g o s s ip in g p r o c e s s o f t h e b a s is . H e n c e , we h a ve t o m o d ify t h e fo r m o f t h e b a s is s u c h t h a t
we c o u ld m a ke in -c a lls a n d o u t -c a lls wit h t h e a t t a c h e d t r e e s in p r o c e s s o f g o s s ip in g o f t h e
b a s is . Fo r t h a t , we s h o u ld r e o r d e r t h e c a lls o f b a s is , in s u c h a wa y t h a t it will b e p o s s ib le t o
m a ke s u c h in -c a lls a n d o u t -c a lls . In o t h e r wo r d s t h e c a lls b e t we e n t wo p a r t s o f g o s s ip s c h e m e
s h o u ld h a ve a n in c r e a s in g a n d d e c r e a s in g o r d e r . A n a d d it io n a l n o t e is t h a t d e p e n d in g o n r
t h e n u m b e r o f a t t a c h e d ve r t ic e s in c r e a s e s e xp o n e n t ia lly. S u c h g o s s ip in g p r o c e s s fo r n = 2 4
is d e m o n s t r a t e d in Fig . 3 , wh e r e r = 2 a n d k = 3 .



1 8 Method of Local Interchange for the Investigation of Gossip Problems: part 2

Fig. 3. Minimum gossip graph (n = 24; k = 3; r = 2).

Ob vio u s ly, t h e n u m b e r o f r o u n d s r e qu ir e d t o p e r fo r m g o s s ip in g is T 0 = 2 r + k wh ic h
c o in c id e s wit h t h e m in im u m p o s s ib le n u m b e r o f r o u n d s fo r s o m e va lu e s o f n, b u t t h is s c h e m e
is n o t t h e o n ly p o s s ib le o n e t o p e r fo r m g o s s ip in g in m in im u m t im e . B y c h a n g in g t h e s iz e
o f t h e b a s is ( k ) a n d n u m b e r o f r o u n d s o f t h e " b a t c h " c a lls ( r ) a n e w m in im u m g o s s ip in g
s c h e m e will b e o b t a in e d ( s e e Fig . 4 ) .

Fig. 4. Minimum gossip graph (n = 24; k = 7; r = 0).

Fr o m t h e s e e xa m p le s it is o b vio u s t h a t in e a c h r o u n d n e w ve r t ic e s a r e in c lu d e d in c o m -
m u n ic a t io n , b u t t h e n u m b e r o f t h e s e ve r t ic e s is lim it e d . S o , t a kin g t h e s e in t o a c c o u n t t h e
fo llo win g le m m a c o u ld b e fo r m u la t e d .

Lemma 1: The number of vertices in minimum gossip graph with the size of basis k and
the number of rounds of the "batch" calls r is limited by the following estimates:

n · 2 k=2+r+1; if k is even, ( 5 )

n · 3 £ 2 (k¡1)=2+r; if k is odd. ( 6 )



V. Hovnanyan, Su. Poghosyan and V. Poghosyan 1 9

P r oof. To p r o ve t h e s e e s t im a t e s le t u s c o n s id e r t h e p r o c e s s o f g o s s ip in g m o r e d e t a ile d .
Th e n u m b e r o f ve r t ic e s t h a t c o u ld b e in vo lve d in g o s s ip in g c o n s is t s o f t wo c o m p o n e n t s n1
a n d n2, wh e r e n1 is t h e n u m b e r o f ve r t ic e s wh ic h a r e in vo lve d in g o s s ip in g p r o c e s s d u e t o
" b a t c h " c a lls a n d n2 is t h e a m o u n t o f ve r t ic e s in vo lve d in g o s s ip in g t h r o u g h t h e a t t a c h e d
t r e e s . Th e d e p e n d e n c y b e t we e n t h e n u m b e r o f r o u n d s o f t h e " b a t c h " c a lls r a n d t h e n1
n u m b e r o f ve r t ic e s is o b vio u s - n1 · 2 r £ 2 k. On t h e o t h e r s id e , it is e a s y t o n o t e t h a t t h e

n u m b e r o f ve r t ic e s in vo lve d in t h e a t t a c h e d t r e e s is n2 · 2 r £ ( 2
dk2 e¡1P

i=2
( k ¡ 2 i ) 2 i¡2 ) a n d it

a ls o d e p e n d s o n r in e xp o n e n t ia l r u le . A lt o g e t h e r , b y c o n s id e r in g t h a t n = n1 + n2 fo r t h e
n u m b e r o f ve r t ic e s o f t h e m in im u m g o s s ip g r a p h we g e t t h e fo llo win g e s t im a t e :

n · 2 r ( 2 k + 2
dk2 e¡1X

i=2

( k ¡ 2 i ) 2 i¡2 ) : ( 7 )

S o , fr o m t h is e xp r e s s io n t h e e s t im a t e s m e n t io n e d in le m m a im m e d ia t e ly fo llo w.
H o we ve r , in c a s e o f e ve n k it is p o s s ib le b y c h a n g in g t h e s t r u c t u r e a n d g o s s ip in g t im e o f

b a s is t o r e a c h m o r e ve r t ic e s in vo lve d in g o s s ip in g . Th e e xa m p le g ive n in Fig . 5 d e m o n s t r a t e s
t h is fo r k = 8 . A c c o r d in g t o le m m a t h e n u m b e r o f ve r t ic e s in t h is c a s e is n · 3 2 , b u t we
in c r e a s e t h e n u m b e r o f r o u n d s o f b a s is b y o n e a n d c h a n g e t h e d ir e c t io n o f t h e " m id d le "
c a lls a n d it g ive s u s t h e o p p o r t u n it y t o in vo lve 8 n e w ve r t ic e s in g o s s ip in g . In fa c t , o u r
m o d ī c a t io n h a s c h a n g e d t h e s t r u c t u r e o f t h e s t a n d a r d p-g r id -ke r n e l t o o n e o f it 's lin e a r
e xt e n s io n ( s e e . [8 ]) a n d t h e n u m b e r o f n e w ve r t ic e s in vo lve d in g o s s ip in g p r o c e s s a ft e r t h is

m o d ī c a t io n is 2
k
2
+r¡1.

Fig. 5. Minimum gossip graph (n = 40; k = 8; r = 0).

N o w le t u s c o n s id e r t h e n u m b e r o f r o u n d s wh ic h a r e n e c e s s a r y t o p e r fo r m g o s s ip in g
wit h m in im u m n u m b e r o f c a lls . L e t it b e d e n o t e d b y T . A s it wa s a lr e a d y m e n t io n e d
T = 2 dlo g 2 ne ¡ 3 . Ou r g o a l is t o s h o w t h e d e p e n d e n c y b e t we e n T a n d n d e p e n d in g o n t h e
c o n s t r u c t io n o f g o s s ip in g s c h e m e . In o t h e r wo r d s , we o ®e r t h e m e t h o d o f c o n s t r u c t io n o f



2 0 Method of Local Interchange for the Investigation of Gossip Problems: part 2

m in im u m g o s s ip g r a p h s fo r t h e p a r t ic u la r va lu e s o f n, wh e r e t h e va lu e s o f k a n d r c a n va r y.
L e t T 0 b e t h e m in im u m n u m b e r o f r o u n d s o f t h e g o s s ip s c h e m e wit h 2 n ¡ 4 c a lls , t h e s iz e o f
t h e b a s is k a n d t h e n u m b e r o f r o u n d s o f " b a t c h " c a lls r.

T heor em 1: In gossiping scheme with the size of the basis k and the number of rounds of
the "batch" calls r the number of rounds necessary to complete gossiping among n nodes is:

T 0 = 2 dlo g 2 ne ¡ 2 ; if k is even, ( 8 )

T 0 = 2
»
lo g 2

n

3

¼
+ 1 ; if k is odd. ( 9 )

P r oof. In c a s e o f e ve n k we h a ve n · 2 k2 +r+1 = 2 T
0

2
+1, s in c e T 0 = 2 r + k, it fo llo ws t h a t

wh e n n h a s t h e fo r m a s a b o ve t h e n T 0 = 2 dlo g 2 ne ¡ 2 . W h e n k is o d d n · 3 £ 2
k¡1

2
+r =

3 £ 2 T
0¡1
2 , h e n c e T 0 = 2

l
lo g 2

n
3

m
+ 1 . Mo r e o ve r , b y c o n s id e r in g t h e " e xt e n d e d " va lu e s o f n

o b t a in e d a ft e r m o d i¯ c a t io n d e s c r ib e d a b o ve ( wh e n it is e ve n ) we h a ve n · 2 k2 +r¡1 + 2 k2 +r¡1.
S in c e , h e r e T 0 = k + 1 + 2 r a n d T 0 = 2

l
lo g 2

n
5

m
+ 3 fo llo ws im m e d ia t e ly. It is o b vio u s , t h a t

fo r s o m e va lu e s o f n T 0 c o in c id e s wit h m in im u m p o s s ib le n u m b e r o f r o u n d s 2 dlo g 2 ne ¡ 3 .
H e n c e , in t h e s e r a n g e s o f n t h e va lu e s o f k a n d r c a n va r y a n d g ive d i®e r e n t c o n s t r u c t io n
o p t io n s o f m in im u m g o s s ip g r a p h s . In Fig . 6 s o m e o f t h e s e r a n g e s a r e d e m o n s t r a t e d , t h e
c o n s t r u c t io n is m in im u m in t h e h ig h lig h t e d r a n g e s .

Fig. 6. Ranges in which the construction is minimal

3 . Co n c lu s io n

A s a c o n c lu s io n we c a n s a y, t h a t in t h is p a p e r t h e m e t h o d o f c o n s t r u c t io n o f m in im u m g o s s ip
g r a p h s wa s p r e s e n t e d , b a s e d o n " c a n o n ic a l" fo r m b a s is g r a p h wit h s iz e k, wh ic h is in t u r n
o b t a in e d fr o m N OH O g r a p h s b y a p p lyin g o p e r a t io n s o f lo c a l in t e r c h a n g e .

A s s u m in g t h a t t h e c a lls b e t we e n n o n -o ve r la p p in g p a ir s o f n o d e s c a n t a ke p la c e s im u lt a -
n e o u s ly, t h e m in im u m a m o u n t o f t im e T ( n) r e qu ir e d t o c o m p le t e g o s s ip in g is dlo g 2 ne fo r
e ve n n a n d dlo g 2 ne + 1 fo r o d d n. S o , o u r fu r t h e r s t u d ie s c o n c e r n t o t h e " r e ve r s e " p r o b le m
o f ¯ n d in g t h e m in im u m n u m b e r o f c a lls o f a g o s s ip s c h e m e wit h t im e ( r o u n d s ) T ( n) .

W e a ls o ¯ n d it in t e r e s t in g t o u s e t h e o p e r a t io n s o f lo c a l in t e r c h a n g e in fa u lt -t o le r a n t
b r o a d c a s t s c h e m e s wh e n a t m o s t k lin e fa u lt s a r e p o s s ib le in t h e c o m m u n ic a t io n p r o c e s s ( s e e
[2 4 , 2 5 ]) . It c a n b e a va lu a b le t o o l in o r d e r t o d e t e r m in e m o r e t ie e s t im a t e s fo r Bk ( n) - t h e
n u m b e r o f m in im u m n e c e s s a r y lin e s t o p e r fo r m k-fa u lt -t o le r a n t b r o a d c a s t in g .

A c kn o wle d g e m e n t s

Th is wo r k wa s s u p p o r t e d b y S t a t e Co m m it t e e o f S c ie n c e ( S CS ) ME S R A , in t h e fr a m e o f t h e
r e s e a r c h p r o je c t N o S CS 1 3 -1 B 1 7 0 . Th e a u t h o r s a r e g r a t e fu l t o A ka d . Y u .H . S h o u ko u r ia n
fo r im p o r t a n t d is c u s s io n s a n d c r it ic a l r e m a r ks o n a ll s t a g e s o f t h e wo r k.



V. Hovnanyan, Su. Poghosyan and V. Poghosyan 2 1

Refer ences

[1 ] T. Tijd e m a n , \ On a t e le p h o n e p r o b le m " , Nieuw Archief voor W iskunde, vo l. 3 , p p .
1 8 8 -1 9 2 , 1 9 7 1 .

[2 ] B .B a ke r a n d R .S h o s t a k, \ Go s s ip s a n d t e le p h o n e s " , D iscrete M athematics, vo l. 2 , p p .
1 9 1 -1 9 3 , 1 9 7 2 .

[3 ] R .T. B u m b y, \ A p r o b le m wit h t e le p h o n e s " , SIAM J ournal on Algebraic D iscrete M eth-
ods, vo l. 2 , p p . 1 3 -1 8 , 1 9 8 1 .

[4 ] A . H a jn a l, E .C. Miln e r a n d E . S z e m e r e d i, \ A c u r e fo r t h e t e le p h o n e d is e a s e " , Canadian
M athematical B ulletin., vo l. 1 5 , p p . 4 4 7 -4 5 0 , 1 9 7 2 .

[5 ] A . S e r e s s , \ Qu ic k g o s s ip in g b y c o n fe r e n c e c a lls " , SIAM J ournal on D iscrete M athemat-
ics, vo l. 1 , p p . 1 0 9 -1 2 0 , 1 9 8 8 .

[6 ] D .B . W e s t , \ Go s s ip in g wit h o u t d u p lic a t e t r a n s m is s io n s " , SIAM J ournal on Algebraic
D iscrete M ethods, vo l. 3 , p p . 4 1 8 -4 1 9 , 1 9 8 2 .

[7 ] G. Fe r t in a n d A . R e s p a u d , " A s u r ve y o n K n Äo d e l g r a p h s " , D iscrete Applied M athematics,
vo l. 1 3 7 , n o . 2 , p p . 1 7 3 -1 9 5 , 2 0 0 3 .

[8 ] R . L a b a h n , \ K e r n e ls o f m in im u m s iz e g o s s ip s c h e m e s " , D iscrete M athematics, vo l. 1 4 3 ,
p p . 9 9 -1 3 9 , 1 9 9 5 .

[9 ] R . L a b a h n , \ S o m e m in im u m g o s s ip g r a p h s " , Networks, vo l. 2 3 , p p . 3 3 3 -3 4 1 , 1 9 9 3 .
[1 0 ] G. Fe r t in a n d R . L a b a h n , \ Co m p o u n d in g o f g o s s ip g r a p h s " , Networks, vo l. 3 6 , p p .

1 2 6 -1 3 7 , 2 0 0 0 .
[1 1 ] Z. H o a n d M. S h ig e n o , \ N e w b o u n d s o n t h e m in im u m n u m b e r o f c a lls in fa ilu r e -t o le r a n t

Go s s ip in g " , Networks, vo l. 5 3 , p p . 3 5 -3 8 , 2 0 0 9 .
[1 2 ] K . A . B e r m a n a n d M. H a wr ylyc z , \ Te le p h o n e p r o b le m s wit h fa ilu r e s " , SIAM J ournal

on Algebraic D iscrete M ethods, vo l. 7 , p p . 1 3 -1 7 , 1 9 8 7 .
[1 3 ] R .W . H a d d a d , S . R o y a n d A .A . S c h a ®e r , \ On g o s s ip in g wit h fa u lt y t e le p h o n e lin e s " ,

SIAM J ournal on Algebraic D iscrete M ethods, vo l. 8 , p p . 4 3 9 -4 4 5 , 1 9 8 7 .
[1 4 ] T. H a s u n a m a a n d H . N a g a m o c h i, \ Im p r o ve d b o u n d s fo r m in im u m fa u lt -t o le r a n t g o s s ip

g r a p h s " , L ecture Notes in Computer Science, vo l. 6 9 8 6 , p p . 2 0 3 -2 1 4 , 2 0 1 1 .
[1 5 ] V . H . H o vn a n ya n , H . E . N a h a p e t ya n , S u . S . P o g h o s ya n a n d V .S . P o g h o s ya n , \ Tig h t e r

u p p e r b o u n d s fo r t h e m in im u m n u m b e r o f c a lls a n d r ig o r o u s m in im a l t im e in fa u lt -
t o le r a n t g o s s ip s c h e m e s " , a r X iv:1 3 0 4 .5 6 3 3 .

[1 6 ] A . B a ve la s , \ Co m m u n ic a t io n p a t t e r n in t a s k-o r ie n t e d g r o u p s " , J ournal of the Acoustical
Society of America vo l. 2 2 , p p . 7 2 5 { 7 3 0 , 1 9 5 0 .

[1 7 ] W . K n o d e l, \ N e w g o s s ip s a n d t e le p h o n e s " , D iscrete M athematics, vo l. 1 3 , p p . 9 5 , 1 9 7 5 .
[1 8 ] S . M. H e d e t n ie m i, S . T. H e d e t n ie m i, A . L . L ie s t m a n , \ A s u r ve y o f g o s s ip in g a n d b r o a d -

c a s t in g in c o m m u n ic a t io n n e t wo r ks " , Networks, vo l. 1 8 , p p . 3 1 9 -3 4 9 , 1 9 8 8 .
[1 9 ] V . H . H o vn a n ya n , S u . S . P o g h o s ya n a n d V . S . P o g h o s ya n , \ Me t h o d o f lo c a l in t e r c h a n g e

t o in ve s t ig a t e Go s s ip p r o b le m s " , Transactions of IIAP of NAS R A, M athematical P rob-
lems of Computer Science, vo l. 4 0 , p p . 5 -1 2 , 2 0 1 3 .

[2 0 ] D . B . W e s t , \ A c la s s o f s o lu t io n s t o t h e g o s s ip p r o b le m " , p a r t I, D iscrete M athematics,
vo l. 3 9 , n o . 3 , p p . 3 0 7 -3 2 6 , 1 9 8 2 ; p a r t II, D isc. M ath., vo l. 4 0 , n o . 1 , p p . 8 7 { 1 1 3 , 1 9 8 2 ;
p a r t III, D iscrete M athematics, vo l. 4 0 , n o . 2 -3 , p p . 2 8 5 -3 1 0 , 1 9 8 2 .

[2 1 ] J. N ie m in e n , \ Tim e a n d c a ll lim it e d t e le p h o n e p r o b le m s " , IE E E Transactions on Cir-
cuits and Systems, vo l. 3 4 , p p . 1 1 2 9 -1 1 3 1 , 1 9 8 7 .

[2 2 ] A . S e r e s s , \ Qu ic k Go s s ip in g wit h o u t d u p lic a t e t r a n s m is s io n s " , Graphs and Combina-
torics, vo l. 2 , p p . 3 6 3 { 3 8 1 , 1 9 8 6 .

[2 3 ] P . Fr a ig n ia u d , A . L . L ie s t m a n a n d D . S o it e a u , \ Op e n p r o b le m s " , P arallel P rocessing
L etters, vo l. 3 , n o . 4 , p p . 5 0 7 -5 2 4 , 1 9 9 3 .



2 2 Method of Local Interchange for the Investigation of Gossip Problems: part 2

[2 4 ] A . P e lc , \ Fa u lt -t o le r a n t b r o a d c a s t in g a n d g o s s ip in g in c o m m u n ic a t io n n e t wo r ks " , Net-
works, vo l. 2 8 , p p . 1 4 3 { 1 5 6 , 1 9 9 6 .

[2 5 ] R . A h ls we d e , L . Ga r g a n o , H . S . H a r o u t u n ia n a n d L . H . K h a c h a t r ia n , \ Fa u lt -t o le r a n t
m in im u m b r o a d c a s t n e t wo r ks " , Networks, vo l. 2 7 , p p . 2 9 3 { 3 0 7 , 1 9 9 6 .

Submitted 20.12.2013, accepted 05.03.2014.

Gossip ËݹÇñÝ»ñÇ Ñ»ï³½áïáõÙÁ “ÈáÏ³É ÷á˳ݳÏٳݔ
Ù»Ãá¹Ç ÙÇçáóáí. Ù³ë 2

ì. ÐáíݳÝÛ³Ý, ê. äáÕáëÛ³Ý ¨ ì. äáÕáëÛ³Ý

²Ù÷á÷áõÙ

Üϳñ³·ñí³Í ¿ ÙÇÝÇÙ³É ½³Ý·»ñáí ÙÇÝÇÙ³É Å³Ù³Ý³ÏáõÙ ÇÝýáñÙ³óÇáÝ ÉñÇí
÷á˳ݳÏáõÙ ³å³ÑáíáÕ Gossip ·ñ³ýÝ»ñÇ áñáß³ÏÇ ¹³ëÇ Ï³éáõóÙ³Ý »Õ³Ý³Ï:
Ü»ñϳ۳óíáÕ ¹³ëÇ ·ñ³ýÝ»ñÇ Ñ³Ù³ñ, áñå»ë µ³½³ÛÇÝ »Ýó·ñ³ý »Ý ѳݹÇë³ó»É
NOHO ·ñ³ýÝ»ñÇ íñ³ [19]-áõÙ Ù»ñ ÏáÕÙÇó Ùß³Ïí³Í “ÈáÏ³É ÷á˳ݳÏٳݔ Ù»Ãá¹Ç
ÙÇçáóáí ϳÝáÝÇÏ ï»ëùÇ µ»ñí³Í »Ýó·ñ³ýÝ»ñÁ:

Èññëåäîâàíèå Gossip çàäà÷ ìåòîäîì
”Ëîêàëüíîãî îáìåíà”: ÷àñòü 2

Â.Îâíàíÿí, Ñ. Ïîãîñÿí è Â. Ïîãîñÿí

Àííîòàöèÿ

Îïèñàí ìåòîä ïîñòðîåíèÿ îïðåäåëåííîãî êëàññà Gossip ãðàôîâ, îáåñïå÷èâàþùèõ
ïîëíûé èíôîðìàöèîíûé îáìåí ñ ïîìîùüþ ìèíèìàëüíîãî ÷èñëà çâîíêîâ çà
ìèíèìàëüíîå âðåìÿ. Äëÿ ïðåäñòàâëåííîãî êëàññà ãðàôîâ, áàçîâûìè ïîäãðàôàìè
ÿâëÿþòñÿ ãðàôû êàíîíè÷åñêîãî âèäà, ïîëó÷åííûå ïóòåì ïðåîáðàçîâàíèÿ NOHO
ãðàôîâ ñ ïîìîùüþ ðàçðàáîòàííîãî â [19] íàìè ìåòîäà Ëîêàëüíîãî îáìåíà.