Hovnanyan_Poghosyans.DVI


Mathematical Problems of Computer Science 40, 5{12, 2013.

M ethod of Local I nter change to I nvestigate Gossip

P r oblems

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

e-mail: williamhovnanyan@gmail.com, psuren@yandex.ru, povahagn@gmail.com

Abstract

In this paper the method of local interchange is introduced to investigate gossip
problems. This method is based on a repetitive use of permute higher and permute
lower operations, which map one gossip graph with n vertices to another by moving
only its edges without changing the labels of edges (the moments of corresponding
calls). Using this method we obtain minimum time gossip graphs in which no one hears
his own information (NOHO graphs) from gossip graphs based on KnÄodel graphs. The
value of minimal time is T = dlog ne. This method also allowed us to ¯nd an alternative
way of the proof that the number of minimal necessary calls in gossip schemes is 2n¡4,
n ¸ 4.

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 x. [4 ] 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 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 [5 ]{ [1 0 ], [1 3 ]{ [1 7 ].

A n o t h e r va r ia n t o f t h e 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 1 , 1 2 , 1 8 ].

In s e c t io n 2 we in t r o d u c e t h e m e t h o d o f local interchange, wh ic h is b a s e d o n a r e p e t it ive
u s e o f permute higher a n d permute lower o p e r a t io n s . Th e s e o p e r a t io n s lo c a lly a c t o n t h e
a d ja c e n t e d g e s t o a g ive n e d g e in a g o s s ip g r a p h ( a n o n -lo c a l interchange of two vertices from

5



6 Method of Local Interchange to Investigate Gossip Problems

some point onwards in a list of telephone calls is d e ¯ n e d in [4 ]) . In s e c t io n 3 t h e m e t h o d
o f local interchange is d e m o n s t r a t e d fo r t h e a lt e r n a t ive d e r iva t io n o f t h e m in im u m n u m b e r
o f c a lls in g o s s ip s c h e m e . A n o t h e r a p p lic a t io n o f local interchange is d e s c r ib e d in s e c t io n 4 ,
wh e r e t h e p r o c e d u r e fo r o b t a in in g m in im u m t im e g o s s ip g r a p h s in wh ic h n o o n e h e a r s h is
o wn in fo r m a t io n ( N OH O g r a p h s , [2 0 , 2 2 ]) fr o m g o s s ip g r a p h s b a s e d o n K n Äo d e l g r a p h s is
fo u n d . S in c e t h e m in im a l t im e o f g o s s ip g r a p h s is kn o wn [1 8 ], t h is p r o c e d u r e a llo we d u s t o
e s t a b lis h t h e va lu e o f m in im a l t im e fo r N OH O g r a p h s T = dlo g ne.

2 . Th e Me t h o d

A g o s s ip s c h e m e ( a s e qu e n c e o f c a lls b e t we e n n n o d e s ) c a n b e r e p r e s e n t e d b y a n u n d ir e c t e d
e d g e -la b e le d g r a p h G = ( V; E ) wit h jV ( G ) j = n ve r t ic e s . Th e ve r t ic e s a n d e d g e s o f G
r e p r e s e n t c o r r e s p o n d in g ly t h e n o d e s a n d t h e c a lls b e t we e n t h e p a ir s o f n o d e s o f a g o s s ip
s c h e m e . S u c h g r a p h s m a y h a ve m u lt ip le e d g e s , b u t n o t s e lf lo o p s . A n e d g e -la b e lin g o f G is a
m a p p in g tG : E ( G) ! Z+. Th e la b e l tG ( e ) o f a g ive n e d g e e 2 E ( G) r e p r e s e n t s t h e m o m e n t
o f t im e , wh e n t h e c o r r e s p o n d in g c a ll o c c u r s .

A s e qu e n c e L = ( v0; e1; v1; e2; v2; : : : ; ek; vk ) wit h ve r t ic e s vi 2 V ( G) fo r 0 · i · k a n d
e d g e s ei 2 E ( G) fo r 1 · i · k is c a lle d a wa lk o f le n g t h k fr o m a ve r t e x v0 t o a ve r t e x vk
in G, if e a c h e d g e ei jo in s t wo ve r t ic e s vi¡1 a n d vi fo r 1 · i · k. A wa lk, in wh ic h a ll t h e
ve r t ic e s a r e d is t in c t , is c a lle d a p a t h . If tG ( ei ) < tG ( ej ) fo r 1 · i < j · k, t h e n L is a n
a s c e n d in g p a t h fr o m v0 t o vk in G. Give n t wo ve r t ic e s u a n d v, if t h e r e is a n a s c e n d in g p a t h
fr o m u t o v, t h e n v r e c e ive s t h e in fo r m a t io n o f u.

N o t e t h a t t wo n o n -a d ja c e n t e d g e s c a n h a ve t h e s a m e la b e l. S in c e we c o n s id e r o n ly
( s t r ic t ly) a s c e n d in g p a t h s , t h e n s u c h e d g e s ( i.e . c a lls ) a r e in d e p e n d e n t , wh ic h m e a n s t h a t
d u r in g t h e c o n s id e r a t io n o f m in im a l n u m b e r o f c a lls t h e e d g e s wit h t h e s a m e la b e l c a n b e
r e o r d e r e d a r b it r a r ily b u t fo r a n y t1 < t2 a ll t h e e d g e s wit h t h e la b e l t1 a r e o r d e r e d b e fo r e
a n y o f t h e e d g e s wit h t h e la b e l t2. Th e r e fo r e , in t h is c a s e we c a n a s s u m e t h a t t h e r e a r e n o t
a n y t wo e d g e s e1 a n d e2 s u c h t h a t tG ( e1 ) = tG ( e2 ) .

D e n o t e t h e s e t o f e d g e s a d ja c e n t t o a g ive n ve r t e x v b y Ev ( G) . Give n a n e d g e e a n d o n e
o f it s t wo e n d p o in t s v, we c o n s id e r t h e fo llo win g t wo s u b s e t s o f t h e s e t Ev ( G ) :

½+v ( e; G) = fe0 2 Ev ( G ) jtG ( e0 ) ¸ tG ( e) g; ( 1 )
½¡v ( e; G ) = fe0 2 Ev ( G) jtG ( e0 ) · tG ( e) g: ( 2 )

S o m e t im e s we o m it t h e a r g u m e n t G in n o t a t io n s .

De¯nition 1: An identi¯cation of two vertices v1 and v2 [4] in a gossip graph G is a gossip
graph G0, which is de¯ned as follows: The edges between the vertices v1 and v2 are deleted
and these two vertices are replaced by a vertex u, whose set of incident edges is Eu ( G

0 ) =
Ev1 ( G) [ Ev2 ( G)

A n in t e r c h a n g e o f t wo ve r t ic e s in a c a llin g s c h e m e is d e ¯ n e d a s fo llo ws : s t a r t e d fr o m t h e
in d ic a t e d m o m e n t o f a t im e t o t h e e n d o f t h e c a llin g s c h e m e t wo ve r t ic e s ( a n d t h e e d g e s
a d ja c e n t t o t h e m ) a r e r e p la c e d b y e a c h o t h e r . In t h is p a p e r we d e ¯ n e t h e c o n c e p t o f lo c a l
in t e r c h a n g e , i.e . a n in t e r c h a n g e t h a t is d e ¯ n e d o n ly fo r a d ja c e n t ve r t ic e s .

De¯nition 2: 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



V. Hovnanyan, Su. Poghosyan,V. Poghosyan 7

follows:
Eu ( P

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

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

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) ; ( 5 )

and
Ev ( P

¡ ( e ) G) = ½+v ( e; G) [ ½¡u ( e; G) : ( 6 )

Th e o p e r a t o r s P + a n d P ¡ a r e c a lle d t h e operators of local interchange.

Lemma 1: The result of the action of the operators of local interchange on a complete gossip
graph is also a complete gossip graph.

A c t u a lly, if a c a ll b e t we e n t wo p a r t ic ip a n t s t a ke s p la c e a t t h e m o m e n t t0, s t a r t e d fr o m
t h a t p o in t t h e y b o t h h a ve t h e s a m e in fo r m a t io n a n d a r e e qu iva le n t . H e n c e , if we c h a n g e a ll
c a lls wh ic h t o o k p la c e a ft e r t h a t m o m e n t ( p e r m u t e h ig h e r ) o u r n e w g o s s ip s c h e m e wo u ld a ls o
b e c o m p le t e . A t t h e s a m e t im e , we c h a n g e d n e it h e r t h e n u m b e r o f e d g e s , n o r 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 . Th e s a m e a s s u m p t io n s c o u ld b e m a d e in c a s e o f
p e r m u t e lo we r o p e r a t io n .

L e t u s d e ¯ n e a n o p e r a t io n o n g o s s ip g r a p h s A+ = P + ( e1 ) P
+ ( e2 ) : : : P

+ ( ep ) ( A
¡ =

P ¡ ( e1 ) P
¡ ( e2 ) : : : P

¡ ( ep ) ) is t h e s e qu e n c e o f p e r m u t e h ig h e r ( lo we r ) o p e r a t io n s o n e d g e s ei,
i = 1 ; : : : ; p.

Lemma 2: The result of the operation A+ (A¡) does not depend on the order of the edges
ei.

P r oof. W it h o u t lo s s o f g e n e r a lit y we c a n o n ly c o n s id e r t h e p e r m u t e h ig h e r o p e r a t io n
A+ wit h p = 2 . A s s u m e t h a t tG ( e1 ) < tG ( e2 ) , wh e r e tG is e d g e -o r d e r in g o f g o s s ip g r a p h G.
Th e r e a r e t wo p o s s ib le c a s e s :

1 ) E d g e s e1 a n d e2 a r e a d ja c e n t . In t h is c a s e , if A
+ = P + ( e1 ) P

+ ( e2 ) , a ft e r P
+ ( e1 ) a ll t h e

e d g e s wh ic h a r e a d ja c e n t t o e1 ( in c lu d in g e2 ) will c h a n g e t h e ir e n d p o in t fr o m o n e e n d p o in t o f
e1 t o a n o t h e r a n d a ft e r P

+ ( e2 ) a ll t h e e d g e s fo r wh ic h tG ( e ) > tG ( e2 ) a ls o will b e p e r m u t e d .
If A+ = P + ( e2 ) P

+ ( e1 ) , t h e n a ft e r t h e ¯ r s t p h a s e o f A
+ a ll t h e e d g e s wit h tG ( e ) > tG ( e2 )

will b e p e r m u t e d a n d a ft e r t h e s e c o n d p h a s e a ll t h e e d g e s wh ic h a r e a d ja c e n t t o e1 a n d h a ve
tG ( e ) > tG ( e1 ) ( in c lu d in g e2 ) will a ls o b e p e r m u t e d . Th e s e o p e r a t io n s a r e d e m o n s t r a t e d in
Fig . 1 . It is o b vio u s t h a t t h e r e s u lt o f t h e s e t wo va r ia t io n s o f A+ is t h e s a m e .

2 ) E d g e s e1 a n d e2 a r e n o t a d ja c e n t . Th is is a s im p le r c a s e in wh ic h t h e o p e r a t io n P
+ ( e )

o n o n e o f t h e m d o e s n o t a ®e c t d ir e c t ly t h e o t h e r . S o , it is o b vio u s t h a t a ll t h e va r ia t io n s o f
A+ a r e e qu iva le n t .

S o , in t h is s e c t io n 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 a n d t h e ir m a in p r o p e r t ie s we r e
d e s c r ib e d . In t h e n e xt t wo s e c t io n we g ive s o m e a p p lic a t io n o f t h e o p e r a t io n s d e s c r ib e d in
t h is s e c t io n .



8 Method of Local Interchange to Investigate Gossip Problems

Fig. 1. Equivalence of di®erent variations of A+

3 . Min im u m Go s s ip Gr a p h s

T heor em 1: The minimum required number of calls in complete gossip schemes is 2 n ¡ 4 ,
n ¸ 4 .

P r oof. A s a lr e a d y m e n t io n e d in t h e in t r o d u c t io n 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 , 2 , 3 , 4 ] t h a t t h e m in im a l n u m b e r o f c a lls in g o s s ip s c h e m e s is 2 n ¡ 4 , wh e r e n is t h e
n u m b e r o f ve r t ic e s . In t h is s e c t io n we will p r o ve t h is s t a t e m e n t in a c o m p le c t ly n e w wa y,
wh ic h is b a s e d o n 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 .

L e t u s d e n o t e b y f ( n) t h e m in im u m n u m b e r o f e d g e s r e qu ir e d t o c o n s t r u c t a g o s s ip g r a p h
o n n ve r t ic e s . Th e r e a r e m a n y s o lu t io n s o f t h is p r o b le m t h a t g ive t h e n u m b e r o f e d g e s ( c a lls )
e qu a l t o 2 n ¡ 4 . Th e r e fo r e , f ( n) · 2 n ¡ 4 is va lid . S o , t h e im p o r t a n t p a r t is t o p r o ve t h a t
f ( n) ¸ 2 n ¡ 4 a ls o .

Co n s id e r a g o s s ip g r a p h wit h n ve r t ic e s a n d t h e n u m b e r o f e d g e s e qu a l t o f ( n) . Ou r g o a l
is t o p r o ve t h a t f ( n) ¸ f ( n ¡ 1 ) + 2 . A ft e r t h a t , t a kin g in t o a c c o u n t t h a t f ( 4 ) = 4 we will
g e t t h a t f ( n) ¸ 2 n ¡ 4 .

S u p p o s e we h a ve a g r a p h G wit h f ( n) c a lls . Th e r e a r e 3 p o s s ib le kin d s o f g r a p h s d e -
p e n d in g o n t h e r e p e t it io n o f in fo r m a t io n .

1 ) It c o n t a in s a c yc le . S u p p o s e a C = ( e1; e2; : : : ; ep ) is a c yc le wit h le n g t h p a n d t h e
e d g e s e1 a n d ep a r e a d ja c e n t t o t h e ve r t e x v ( s e e Fig . 2 ) .

Fig. 2. Cycle C in gossip graphs

Th e s im p le s t c a s e is if p = 2 . If t h is h o ld s , we c a n a p p ly a n o p e r a t io n o f t h e id e n t i¯ c a t io n
o f t wo ve r t ic e s c o n n e c t e d b y t h is m u lt ip le e d g e wh ic h is d e s c r ib e d in t h e s e c t io n a b o ve .
Ob vio u s ly, a ft e r t h is o p e r a t io n o n c o m p le t e g o s s ip g r a p h s , t h e o b t a in e d n e w g o s s ip g r a p h s
a r e a ls o c o m p le t e ( it d o e s n o t a ®e c t o n a s c e n d in g p a t h s b e t we e n t h e p a ir s o f ve r t ic e s ) . H e n c e ,
o u r n e w g r a p h G0 wit h n ¡ 1 ve r t ic e s h a s jE ( G0 ) j ¸ f ( n ¡ 1 ) e d g e s . On t h e o t h e r h a n d G0 is



V. Hovnanyan, Su. Poghosyan,V. Poghosyan 9

o b t a in e d fr o m G b y r e m o vin g t wo e d g e s a n d m e r g in g t wo ve r t ic e s , t h u s , jE ( G0 ) j = f ( n) ¡ 2 .
H e n c e , we o b t a in

f ( n) ¸ f ( n ¡ 1 ) + 2 : ( 7 )
N o w c o n s id e r t h e c a s e o f p 6= 2 a n d a n o p e r a t io n A¡ = ( P ¡ ( e2 ) P ¡ ( e3 ) : : : P ¡ ( ep¡1 ) ) . A s

it is p r o ve d in t h e p r e vio u s s e c t io n t h e r e s u lt o f a p p lic a t io n o f t h is o p e r a t io n o n a c o m p le t e
g o s s ip g r a p h is a ls o a c o m p le t e g o s s ip g r a p h . In t h e r e s u lt t h e e d g e s e1 a n d ep will jo in a n d
fo r m a d o u b le -e d g e . Th u s , we c a m e t o t h e c a s e o f p = 2 . Fu r t h e r s t e p s a r e d e s c r ib e d a b o ve .

2 ) Th e r e a r e n o c yc le s ( N OH O g r a p h s ) . In t h is c a s e we c a n r e fe r t o [6 , 2 0 ], b u t le t u s
a ls o c o n s id e r t h is c a s e . L e t L1 = ( e1; e2; : : : ; en ) a n d L2 = ( l1; l2; : : : ; lm ) b e a s c e n d in g p a t h s
fr o m t h e ve r t e x v t o t h e ve r t e x u.

L e t u s d e ¯ n e t h e o p e r a t io n s

A¡e = ( P
¡ ( e2 ) P

¡ ( e3 ) : : : P
¡ ( en¡1 ) ) ( 8 )

a n d
A¡l = ( P

¡ ( l2 ) P
¡ ( l3 ) : : : P

¡ ( lm¡1 ) ) ( 9 )

o n g o s s ip g r a p h . A ft e r a p p lic a t io n o f t h e s e o p e r a t io n s we will o b t a in a t e t r a g o n wh ic h
in vo lve s t h e ve r t ic e s u a n d v a n d t h e e d g e s e1; l1; en; lm. Th e n we c h o o s e t h e g r e a t e s t fr o m
t h e p a ir e1; l1 a n d a p p ly o p e r a t io n " p e r m u t e lo we r " o n it . W e will o b t a in a t r ia n g le t h a t is
a ls o a c yc le ( c a s e 1 ) . Th is p r o c e s s is d e m o n s t r a t e d in Fig . 3 .

Fig. 3. Ascending paths in gossip graphs

3 ) Th e r e a r e n o d u p lic a t e s o f in fo r m a t io n ( N OD U P g r a p h s ) . In t h is c a s e t h e r e is e xa c t ly
o n e a s c e n d in g p a t h b e t we e n a n y p a ir o f ve r t ic e s . It h a s b e e n s h o wn in [2 1 ], t h a t in t h is c a s e
f 0 ( n) = 2 :2 5 n ¡ 6 , n = 4 k, k ¸ 2 , wh e r e f 0 ( n) is t h i m in im u m n u m b e r o f e d g e s o f N OD U P
g r a p h a n d it c o in c id e s wit h 2 n ¡ 4 o n ly wh e n n = 8 . S o , if it is a N OD U P g r a p h , it a lwa ys
h a s m o r e e d g e s t h a n 2 n ¡ 4 a n d t h e o n ly e xc e p t io n is t h e c a s e wh e n n = 8 . Ca s e o f n = 4
wa s n o t c o n s id e r e d in [2 1 ], b u t in t h is c a s e f ( n) a n d f 0 ( n) a ls o c o in c id e .

In t h e n e xt s e c t io n o t h e r a p p lic a t io n s o f lo c a l in t e r c h a n g e o p e r a t io n s a r e d e s c r ib e d .

4 . N OH O Gr a p h s B a s e d o n K n Äo d e l Gr a p h s

In [1 9 ] it is m e n t io n e d t h a t t h e m in im u m t im e n e e d e d t o c o m p le t e g o s s ip in g is dlo g ne. In
[2 2 ] a p r o b le m o f ¯ n d in g m in im u m t im e o f g o s s ip in g in c a s e o f N OH O g r a p h s ( p r o b le m 2 6 )
is r a is e d . In t h is s e c t io n we will s h o w a n e w m e t h o d o f c o n s t r u c t io n o f N OH O g r a p h s wit h
m in im u m g o s s ip in g t im e b y a p p lyin g a n o p e r a t io n o f lo c a l in t e r c h a n g e o n K n Äo d e l g r a p h s
( [7 ]) .



1 0 Method of Local Interchange to Investigate Gossip Problems

De¯nition 3: The K nÄodel graph on n ¸ 2 vertices (n even) and of degree ¢ ¸ 1 is denoted
by W¢ ;n. The vertices of W¢ ;n are the pairs ( i; j ) with i = 1 ; 2 and 0 · j · n=2 ¡ 1 . F or
every j, 0 · j · n= 2 ¡ 1 and l = 1 ; : : : ; ¢ , there is an edge with the label l between the vertex
( 1 ; j ) and ( 2 ; ( j + 2 l¡1 ¡ 1 ) m o d n= 2 ) .

Fr o m t h e d e ¯ n it io n it fo llo ws t h a t t h is g r a p h is c o n n e c t e d o n ly if ¢ ¸ 2 . W e will c o n s id e r
t h e K n Äo d e l g r a p h s wit h ¢ = dlo g 2 ne.

Fig. 4. Gossip graph based on KnÄodel graph

In [1 8 ] it wa s s h o wn t h a t t h e c o m b in a t io n o f t wo K n Äo d e l g r a p h s wit h ¢ 1 = dlo g 2 ne
a n d ¢ 2 = 1 is a c o m p le t e g o s s ip g r a p h ( s e e Fig . 4 ) . L e t u s d e ¯ n e t h e o p e r a t io n A

¡
l =

fP ¡ ( e ) jtG ( e ) < tG ( l ) g a s a n o p e r a t io n o f p e r m u t a t io n o f a ll e d g e s t h a t h a ve lo we r we ig h t
va lu e ( o r la b e l) t h e n l. A ft e r a p p lic a t io n o f A¡2 o n K n Äo d e l g r a p h s a ll e d g e s wit h la b e l 1 will
b e p e r m u t e d ( s e e Fig . 5 ) .

Fig. 5. NOHO graph based on KnÄodel graph

Lemma 3: The result of application of A¡2 on complete gossip graph based on K nÄodel graph
is a NOHO gossip graph with minimum gossiping time T = dlo g 2 ne.

P r oof. W it h o u t lo s s o f g e n e r a lit y we c a n c o n s id e r o n ly t h e p e r m u t a t io n o f a n e d g e t h a t
c o n n e c t s ve r t ic e s ( 1 ; 0 ) a n d ( 2 ; 0 ) . Th is e d g e h a s t wo a d ja c e n t e d g e s wit h la b e l 2 , h e n c e ,
a ft e r A¡2 it will c h a n g e it s p o s it io n t wic e . S o , a ft e r t h is o p e r a t io n t h e ve r t ic e s t h a t c o n n e c t
t h is e d g e a r e ( 2 ; 1 ) a n d ( 1 ; n=2 ¡ 1 ) . Th e s e ve r t ic e s we r e n o t c o n n e c t e d in o u r in it ia l g r a p h
( a c c o r d in g t o t h e d e ¯ n it io n o f K n Äo d e l g r a p h ) , h e n c e , a ft e r A¡2 t h e r e will b e n o d u p lic a t e
e d g e s . On t h e o t h e r h a n d , h e r e we a p p ly a n in ve r s e o p e r a t io n o f t h e o p e r a t io n d e s c r ib e d
in t h e p r e vio u s s e c t io n o f c a s e 2 . R e a lly, a ft e r p e r m u t a t io n o f t h is e d g e t h e ve r t ic e s ( 1 ; 0 ) ,
( 2 ; 0 ) , ( 2 ; 1 ) a n d ( 1 ; n=2 ¡ 1 ) a n d e d g e s wit h la b e ls tG ( e1 ) = 1 , tG ( e2 ) = 2 , tG ( e3 ) = 2 a n d
tG ( e4 ) = dlo g 2 ne will fo r m a t e t r a g o n wh ic h is n o t a c yc le . Th u s , we e xc lu d e t h e p o s s ib ilit y
o f e xis t e n c e o f c yc le s a ft e r t h is o p e r a t io n . H e n c e , a ft e r a p p lic a t io n o f A¡2 we o b t a in a N OH O
g r a p h wh ic h is e qu iva le n t t o o u r in it ia l c o m p le t e g o s s ip g r a p h .



V. Hovnanyan, Su. Poghosyan,V. Poghosyan 1 1

Th is m e t h o d s o f lo c a l in t e r c h a n g e a ls o h a ve s o m e o t h e r a p p lic a t io n s , wh ic h a llo we d u s
t o in ve s t ig a t e m a n y va r ia t io n s o f b r o a d c a s t p r o b le m a n d im p r o ve s o m e kn o wn p a r a m e t e r s
c o n c e r n in g t h e b r o a d c a s t s c h e m e s , b u t it is n o t t h e s u b je c t o f t h is p a p e r .

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 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.

Refer ences

[1 ] 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 ath., vo l. 2 , p p . 1 9 1 -1 9 3 ,
1 9 7 2 .

[2 ] 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 . Alg. D isc. M ath., vo l. 2 , p p . 1 3 -1 8 ,
1 9 8 1 .

[3 ] 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 " , Canad.
M ath B ull., vo l. 1 5 , p p . 4 4 7 -4 5 0 , 1 9 7 2 .

[4 ] T. Tijd e m a n , \ On a t e le p h o n e p r o b le m " , Nieuw Arch. W isk., vo l. 3 , p p . 1 8 8 -1 9 2 , 1 9 7 1 .
[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 . D isc. M ath, 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 . Alg. D isc. M eth.,

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 ( 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 iscr. M ath., 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 ] 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 . Acoust. Soc. Amer.,
vo l. 2 2 , p p . 7 2 5 -7 3 0 , 1 9 5 0 .

[1 2 ] 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 iscr. M ath., vo l. 1 3 , p p . 9 5 , 1 9 7 5 .
[1 3 ] 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 4 ] 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 . Alg.

D isc. M eth., vo l. 7 , p p . 1 3 -1 7 , 1 9 8 7 .
[1 5 ] 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 . Alg. D isc. M eth., vo l. 8 , p p . 4 3 9 -4 4 5 , 1 9 8 7 .
[1 6 ] 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 NCS 6 9 8 6 , p p . 2 0 3 -2 1 4 , 2 0 1 1 .
[1 7 ] 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 " , NE TW OR K S, vo l. 2 7 , p p . 2 9 3 -3 0 7 , 1 9 9 6 .
[1 8 ] 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 9 ] H e d e t n ie m i, H e d e t n ie m i a n d L is 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 2 Method of Local Interchange to Investigate Gossip Problems

[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 Go s s ip p r o b le m " , p a r t I, D isc. M ath. 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 isc. M ath., vo l 4 0 2 -3 , p p . 2 8 5 -3 1 0 , 1 9 8 2 .

[2 1 ] 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 2 ] P . Fr a ig n ia u d , A .L . L ie s t m a n , 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 4 , p p . 5 0 7 -5 2 4 , 1 9 9 3 .

Submitted 02.09.2013, accepted 18.10.2013.

Gossip ËݹÇñÝ»ñÇ Ñ»ï³½áïáõÙÁ \ ÈáÏ³É ÷á˳ݳÏÙ³Ý \
Ù»Ãá¹Ç ÙÇçáóáí

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

²Ù÷á÷áõÙ

²Ûë Ñá¹í³ÍáõÙ Ýϳñ³·ñí³Í »Ý ÉáÏ³É ÷á˳ݳÏÙ³Ý Ù»Ãá¹Á ¨ Ýñ³ ÏÇñ³éáõÃÛáõÝÝ»ñÁ
gossip ËݹÇñÝ»ñÇ Ñ»ï³½áïÙ³Ý Ñ³Ù³ñ: ²Ûë Ù»Ãá¹Á ÑÇÙÝí³Í ¿ ï»Õ³÷áË»É
³í»ÉÇ Ù»Í»ñÁ ¨ ï»Õ³÷áË»É ³í»ÉÇ ÷áùñ»ñÁ ·áñÍáÕáõÃÛáõÝÝ»ñÇ µ³½Ù³ÏÇ ÏÇñ³éÙ³Ý
íñ³, áñáÝù ³ñï³å³ïÏ»ñáõÙ »Ý ÙÇ n ·³·³Ã³ÝÇ gossip ·ñ³ýÁ Ù»Ï áõñÇßÇ íñ³`
ï»Õ³÷áË»Éáí ÙdzÛÝ ÏáÕ»ñÁ, ã÷áË»Éáí ÏáÕ»ñÇ ÝÇß»ñÁ (ѳٳå³ï³ëË³Ý ½³Ý·»ñÇ
ųٳݳÏÝ»ñÁ): ú·ï³·áñÍ»Éáí ³Ûë Ù»Ãá¹Á` KnÄodel ·ñ³ýÝ»ñÇ ÑÇÙ³Ý íñ³ Ù»Ýù
ëï³ó»É »Ýù ÙÇÝÇÙ³É Å³Ù³Ý³Ï³ÛÇÝ NOHO gossip ·ñ³ýÝ»ñ (áã áù »ñµ»ù ãÇ ÉëáõÙ Çñ
ÇÝýáñÙ³ódzÝ): êï³óí³Í ÙÇÝÇÙ³É Å³Ù³Ý³ÏÇ ×ß·ñÇï ³ñÅ»ùÝ ¿` T = dlo g ne: ²Ûë
Ù»Ãá¹Ç ÙÇçáóáí ïñí»É ¿ gossip ë˻ٳݻñÇ ÙÇÝÇÙ³É ³ÝÑñ³Å»ßï ½³Ý·»ñÇ ù³Ý³ÏÇ
µ³Ý³Ó¨Ç ( 2 n ¡ 4 ; n ¸ 4 ) ¨ë ÙÇ Ýáñ ³ñï³ÍáõÙ:

Èññëåäîâàíèå Gossip ïðîáëåì ïðè ïîìîùè ìåòîäà
”Ëîêàëüíûõ ïåðåñòàíîâîê”
Â. Îâíàíÿí, Ñ. Ïîãîñÿí è Â. Ïîãîñÿí

Àííîòàöèÿ

 ýòîé ñòàòüå ââåäåí ìåòîä ëîêàëüíûõ ïåðåñòàíîâîê äëÿ èçó÷åíèÿ gossip
çàäà÷. Ýòîò ìåòîä îñíîâàí íà ìíîãîêðàòíîì ïðèìåíåíèè îïåðàöèé ïåðåñòàâèòü
áîëåå ñòàðøèå è ïåðåñòàâèòü ìåíåå ìëàäøèå, êîòîðûå îòîáðàæàþò îäèí ãðàô
ñ n âåðøèíàìè íà äðóãîé, ïåðåìåùàÿ òîëüêî ðåáðà, íå ìåíÿÿ èõ ìåòîê (âðåìÿ
ñîîòâåòñòâóþùåãî çâîíêà). Èñïîëüçóÿ ýòîò ìåòîä, íà îñíîâå KnÄodel ãðàôîâ,
ìû ïîëó÷èëè ìèíèìàëüíî âðåìåííûå NOHO gossip ãðàôû (íèêòî íèêîãäà íå
óñëûøèò ñâîþ èíôîðìàöèþ). Òî÷íîå çíà÷åíèå ïîëó÷åííîãî ìèíèìàëüíîãî
âðåìåíè T = dlo g ne. Ñ ïîìîùüþ ýòîãî ìåòîäà ïîëó÷åíî åùå îäíî íîâîå
äîêàçàòåëüñòâî ôîðìóëû ( 2 n ¡ 4 ; n ¸ 4 ) äëÿ ìèíèìàëüíîãî íåîáõîäèìîãî
êîëè÷åñòâà çâîíêîâ gossip ñõåì.