D:\FINAL_TEX\...\Viliam.DVI


Mathematical Problems of Computer Science 42, 43{53, 2014.

Fault-toler ant Gossip Gr aphs B ased on Wheel Gr aphs

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, psuren55@yandex.ru, povahagn@gmail.com

Abstract

The gossip problem (telephone problem) is an information dissemination problem
where each of n nodes of a communication network has a unique piece of information
that must be transmitted to all the other nodes using two-way communications (tele-
phone calls) between the pairs of nodes. Upon a call between the given two nodes, they
exchange the whole information known to them at that moment. In this paper, we
investigate the k-fault-tolerant gossip problem, which is a generalization of the gossip
problem, where at most k arbitrary faults of calls are allowed. The problem is to ¯nd
the minimal number of calls ¿ (n; k) needed to guarantee the spread of whole infor-
mation. We constructed a k-fault-tolerant gossip scheme (sequences of calls) to ¯nd
the upper bounds of ¿ (n; k), which improves the previously known results for some
particular small values of n and k.

Keywords: Gossip, Information dissemination, Fault-tolerant gossiping.

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 . [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 ( 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 t h e s e qu e n c e o f c a lls
wit h a 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 ( s e e e .g . [5 ]{ [1 0 ],
[1 2 ]{ [1 7 ]) .

On e o f t h e n a t u r a l g e n e r a liz a t io n s o f t h is p r o b le m is t h e k-fa u lt -t o le r a n t g o s s ip p r o b le m ,
wh ic h a s s u m e s t h a t s o m e o f t h e c a lls in t h e c a ll s e qu e n c e c a n fa il ( d o n o t t a ke p la c e ) [1 3 ]-
[1 6 ]. Th e n o d e s c a n n o t c h a n g e t h e s e qu e n c e o f t h e ir fu t u r e c a lls d e p e n d in g o n t h e c u r r e n t
fa ile d c a lls . H e r e t h e a im is t o ¯ n d a m in im a l g o s s ip s c h e m e , wh ic h g u a r a n t e e s t h e fu ll
e xc h a n g e o f t h e in fo r m a t io n in t h e c a s e o f a t m o s t k a r b it r a r y fa ils , r e g a r d le s s o f wh ic h t h e
c a lls fa ile d . Th e g o s s ip s c h e m e s , wh ic h p r o vid e k-fa u lt -t o le r a n c e , a r e c a lle d k-fa u lt -t o le r a n t

4 3



4 4 Fault-tolerant Gossip Graphs Based on Wheel Graphs

g o s s ip s c h e m e s . D e n o t e t h e m in im a l n u m b e r o f c a lls in t h e k-fa u lt -t o le r a n t m in im a l g o s s ip
s c h e m e b y ¿ ( n; k ) .

B e r m a n a n d H a wr ylyc z [1 4 ] o b t a in e d t h e lo we r a n d u p p e r b o u n d s fo r ¿ ( n; k ) :
»µ

k + 4

2

¶
( n ¡ 1 )

¼
¡ 2

§p
n
¨

+ 1 · ¿ ( n; k ) ·
¹µ

k +
3

2

¶
( n ¡ 1 )

º
; ( 1 )

fo r k · n ¡ 2 , a n d
»µ

k + 3

2

¶
( n ¡ 1 )

¼
¡ 2

§p
n
¨
· ¿ ( n; k ) ·

¹µ
k +

3

2

¶
( n ¡ 1 )

º
; ( 2 )

fo r k ¸ n ¡ 2 .
H a d d e d , R o y a n d S c h a ®e r [1 5 ] p r o ve d a ft e r wa r d s t h a t

¿ ( n; k ) ·
µ

k

2
+ 2 p

¶µ
n ¡ 1 + n ¡ 1

2 p ¡ 1 + 2
p

¶
; ( 3 )

wh e r e p is a n y in t e g e r b e t we e n 1 a n d lo g 2 n in c lu s ive . B y c h o o s in g p a p p r o p r ia t e ly, t h is r e s u lt
im p r o ve s t h e u p p e r b o u n d s o b t a in e d b y B e r m a n a n d H a wr ylyc z fo r a lm o s t a ll k. P a r t ic u la r ly,

b y c h o o s in g p =
h

log2 n
2

i
, t h e fo llo win g b o u n d is o b t a in e d : ¿ ( n; k ) · nk

2
+ O ( k

p
n + n lo g 2 n) .

Fo r t h e s p e c ia l c a s e n = 2 p fo r s o m e in t e g e r p, H a d d a d , R o y, a n d S c h a ®e r [1 5 ] a ls o s h o we d
t h a t

¿ ( n; k ) · m in
½µ»

k + 1

lo g 2 n

¼
+ 1

¶
n lo g 2 n

2
;

µ¹
k + 1

lo g 2 n

º
+ 1

¶
n lo g 2 n

2
+ ( ( k + 1 ) m o d lo g 2 n) ( 2 n ¡ 4 )

¾
: ( 4 )

Th u s , ¿ ( n; k ) · nk
2

+ O ( n lo g 2 n) , wh e n n is a p o we r o f 2 .
L a t e r o n , H o u a n d S h ig e n o [1 3 ] s h o we d t h a t

¹
n ( k + 2 )

2

º
· ¿ ( n; k ) · n( n ¡ 1 )

2
+

»
nk

2

¼
: ( 5 )

S o , it h o ld s t h a t nk
2

+ ­( n) · ¿ ( n; k ) · nk
2

+ O ( n2 ) . Th e s e b o u n d s im p r o ve t h e p r e vio u s
b o u n d s fo r s m a ll n a n d s u ± c ie n t ly la r g e k.

R e c e n t ly, H a s u n u m a a n d N a g a m o c h i [1 6 ] s h o we d t h a t

¿ ( n; k ) ·
½

n log2 n
2

+ nk
2

; if n is a p o we r o f 2
2 n blo g 2 nc + n

§
k¡1
2

¨
; o t h e r wis e ,

( 6 )

a n d »
3 n ¡ 5

2

¼
+

»
1

2

µ
nk +

¹
n + 1

2

º
¡ blo g 2 nc

¶¼
· ¿ ( n; k ) : ( 7 )

Fr o m t h e ir r e s u lt s , it h o ld s t h a t ¿ ( n; k ) · nk
2

+ O ( n lo g 2 n) . P a r t ic u la r ly, t h e ir u p p e r b o u n d
im p r o ve s t h e u p p e r b o u n d b y H o u a n d S h ig e n o fo r a ll n ¸ 1 3 . Th e y a ls o im p r o ve t h e u p p e r
b o u n d b y H a d d a d et al. b y s h o win g t h a t t h e fa c t o r ( k= 2 + 2 p ) in t h e ir u p p e r b o u n d c a n b e
r e p la c e d wit h a s m a lle r fa c t o r ( k=2 + p) :

¿ ( n; k ) ·
µ

k

2
+ p

¶µ
n ¡ 1 + n ¡ 1

2 p ¡ 1 + 2
p

¶
; ( 8 )



V. Hovnanyan, S. Poghosyan and V. Poghosyan 4 5

wh e r e p is a n y in t e g e r b e t we e n 1 a n d lo g 2 n.
In t h is p a p e r , we c o n s t r u c t a k-fa u lt -t o le r a n t g o s s ip s c h e m e b a s e d o n W h e e l g r a p h s ,

wh ic h im p r o ve s t h e p r e vio u s ly kn o wn r e s u lt s o n t h e u p p e r b o u n d fo r t h e n u m b e r o f c a lls in
c a s e o f s m a ll n a n d k. Th e o b t a in e d e xp r e s s io n s fo r g e n e r a l n a n d k a r e ( s e e Th e o r e m 2 ) a s
fo llo ws :

¿ ( n; k ) · 2
3

nk + O ( n) ( 9 )

2 . P r e lim in a r ie s

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 t h e 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 P = ( 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 P 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 d i®e r 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) t h e 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 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.

De¯nition 1: The communication between two vertices of G is called k-failure safe if an
ascending path between them remains, even if arbitrary k edges of G are deleted (the corre-
sponding calls fail). The graph G is called a k-fault-tolerant gossip graph if the communica-
tion between all the pairs of its vertices is k-failure safe.

Fr o m t h e Me n g e r t h e o r e m [2 2 ] it fo llo ws t h a t a k-fa u lt -t o le r a n t g o s s ip g r a p h is a g r a p h
wh o s e e d g e s a r e la b e le d in s u c h a wa y t h a t t h e r e a r e a t le a s t k + 1 e d g e -d is jo in t a s c e n d in g
p a t h s b e t fwe e n t wo a r b it r a r y ve r t ic e s . A 0 -fa u lt -t o le r a n t g o s s ip g r a p h is s im p ly c a lle d a
g o s s ip g r a p h .

To d e s c r ib e t h e c o n s t r u c t io n o f k-fa u lt -t o le r a n t g o s s ip g r a p h s ( s c h e m e s ) , we u s e s o m e
im p o r t a n t d e ¯ n it io n s a n d p r o p o s it io n s g ive n in t h e wo r ks [1 5 ], [1 6 ]. In o r d e r t o s im p lify t h e
d is c u s s io n fo r e d g e -d is jo in t p a t h s , we o ft e n o m it t h e ve r t ic e s ( o r e d g e s ) in t h e d e s c r ip t io n o f
a p a t h if t h e r e is n o c o n fu s io n .

De¯nition 2: L et P = ( e1; e2; : : : ; ek ) be a path with edges ei 2 E ( G) for 1 · i · k in a
labeled graph G. If P is divided into s+1 subpaths P (1) = ( e1; : : : ; ep1 ) , P

(2) = ( ep1+1; : : : ; ep2 ) ,
: : : , P (s+1) = ( eps+1; : : : ; ek ) , then we write P = P

(1) ¯ P (2) ¯ ¢ ¢ ¢ ¯ P (s+1), where ¯ is the
concatenation operation on two paths for which the last vertex of one path is the ¯rst vertex
of the other. If P = P (1) ¯ P (2) ¯ ¢ ¢ ¢ ¯ P (s+1) such that P (j) is an ascending path for
1 · j · s + 1 and P (j) ¯ P (j+1) is not an ascending path for 1 · j · s, then P is an s-folded
ascending path in G. F or an s-folded ascending path P , the folded number of P is de¯ned to
be s.



4 6 Fault-tolerant Gossip Graphs Based on Wheel Graphs

De¯nition 3: Consider two graphs G1 = ( V; E1 ) and G2 = ( V; E2 ) with the same set of
vertices V and labeled edge sets E1 and E2, respectively. The edge sum of these graphs is
the graph G1 + G2 = G = ( V; E ) with E = E1 [ E2, whose edges e 2 E are labeled by the
following rules:

tG ( e) =

(
tG1 ( e ) ; if e 2 E1;
tG2 ( e ) + m a x

e02E1
tG1 ( e

0 ) ; if e 2 E2: ( 1 0 )

The edge sum G1 + G2 +¢ ¢ ¢+ Gh of h identical graphs ( G1 = G2 = ¢ ¢ ¢ = Gh ´ G ) is denoted
by hG. E ach set E ( Gi ) in hG is denoted by Ei ( hG ) , i.e., E ( hG ) =

S
1·i·h Ei ( hG) . Note

that the labels of the edges in Ei ( hG ) are greater than the corresponding edges in E ( G) by
( i ¡ 1 ) £ m a x

e2E(G)
tG ( e) . Given a subset of edges A µ E ( G) , denote its copy in the set Ei ( hG )

by Ai. B y this analogy, a path P in G as a subset of E ( G) has a copy in Ei ( hG ) , which we
denote by Pi.

L e t P = P (1) ¯ P (2) ¯ ¢ ¢ ¢ ¯ P (s+1) b e a n s-fo ld e d a s c e n d in g p a t h fr o m a ve r t e x u t o a
ve r t e x v in G, wh e r e P (j) is a n a s c e n d in g s u b p a t h fo r 1 · j · s + 1 . Th e n , Pi is a ls o a n
s-fo ld e d a s c e n d in g p a t h a n d Pi = P

(1)
i ¯ P

(2)
i ¯ ¢ ¢ ¢ ¯ P

(s+1)
i fo r 1 · i · h. N o w c o n s id e r

t h e p a t h P ( k ) = P
(1)
k ¯ P

(2)
k+1 ¯ ¢ ¢ ¢ ¯ P

(s+1)
k+s in hG. Th e n , P ( k ) is a n a s c e n d in g p a t h fr o m u

t o v fo r 1 · k · h ¡ s s u c h t h a t P ( k ) a n d P ( k 0 ) a r e e d g e -d is jo in t if k 6= k 0. Th u s , b a s e d
o n P , we c a n c o n s t r u c t ( h ¡ s) e d g e -d is jo in t a s c e n d in g p a t h s fr o m u t o v in hG. S im ila r ly,
b a s e d o n a n o t h e r s-fo ld e d a s c e n d in g p a t h P 0 fr o m u t o v, we c a n c o n s t r u c t ( h ¡ s) e d g e -
d is jo in t a s c e n d in g p a t h s P 0 ( k ) fr o m u t o v fo r 1 · k · h ¡ s. If P a n d P 0 a r e e d g e -d is jo in t ,
t h e n a ll t h e p a t h s P ( 1 ) ; : : : ; P ( h ¡ s) a n d P 0 ( 1 ) ; : : : ; P 0 ( h ¡ s) a r e p a ir wis e e d g e -d is jo in t b y
c o n s t r u c t io n . Th e r e fo r e , t h e fo llo win g le m m a h o ld s ( s e e [1 5 , 1 6 ]) .

Lemma 1: L et u and v be vertices in a labeled graph G. If there are p edge-disjoint s-folded
ascending paths from u to v in G, then there are p ( h ¡ s) edge-disjoint ascending paths from
u to v in hG for any integer h ¸ s.

Fr o m t h is le m m a , if t h e r e a r e p e d g e -d is jo in t s-fo ld e d a s c e n d in g p a t h s fr o m u t o v in G, t h e n

t h e r e a r e k + 1 e d g e -d is jo in t a s c e n d in g p a t h s fr o m u t o v in
³
s + dk+1

p
e
´

G.

Th u s , t h e fo llo win g c o r o lla r y is o b t a in e d ( s e e [1 5 ]) .

Cor ollar y 1: L et G be a graph with n vertices and m edges. If there are p edge-disjoint
s-folded ascending paths between every pair of vertices in a labeled graph G, then ¿ ( n; k ) ·³
s + dk+1

p
e
´

m.

In o r d e r t o im p r o ve t h is e s t im a t io n o f t h e u p p e r b o u n d , a s t r o n g e r p r o p o s it io n is fo r m u la t e d
a n d p r o ve d in [1 6 ].

T heor em 1: L et G be a labeled graph with n vertices. Suppose that

² E ( G) can be decomposed into l subsets F (0); F (1); : : : ; F (l¡1) such that for any two edges
e 2 F (i) and e 0 2 F (j), tG ( e ) < tG ( e 0 ) if i < j,

² for any two vertices u and v, there are p edge-disjoint paths from u to v such that the
sum of their folded numbers is at most q, and the last edges of ri paths are in F

(i) for
0 · i · l ¡ 1 .



V. Hovnanyan, S. Poghosyan and V. Poghosyan 4 7

Then, the minimal number of edges in a k-fault-tolerant gossip graph is bounded

¿ ( n; k ) · » ( n; k ) ; ( 1 1 )

with » ( n; k ) de¯ned by the expression

» ( n; k ) =
X

0·i·w
jF (i m od l)j; ( 1 2 )

where w is an integer satisfying

X

0·i·w
ri m od l ¸ k + q + 1 : ( 1 3 )

D u r in g t h e p r o o f, t h e g r a p h eG = hG + G 0 wit h h = bw
l
c a n d G 0 = ( V; [0·i·w¡hlF (i) ) is

c o n s t r u c t e d , a n d s h o we d t h a t it is a k-fa u lt -t o le r a n t g o s s ip g r a p h . Th e n u m b e r o f e d g e s o f
t h is g r a p h is jE ( eG ) j =

P
0·i·w jF (i m od l)j.

In t h e n e xt s e c t io n we c o n s t r u c t a la b e le d W h e e l g r a p h a n d a p p ly Th e o r e m 1 t o im p r o ve
t h e kn o wn e s t im a t io n s o f t h e u p p e r b o u n d s fo r ¿ ( n; k ) .

3 . Fa u lt -t o le r a n t Go s s ip Gr a p h s B a s e d o n W h e e l Gr a p h

Co n s id e r a wh e e l g r a p h G = ( V; E ) wit h a n o d d n u m b e r o f ve r t ic e s n, wh o s e ve r t ic e s a n d
e d g e s a r e la b e le d b y t h e fo llo win g r u le s : t h e la b e l o f t h e c e n t r a l ve r t e x is u, t h e r e m a in in g
ve r t ic e s ( wh ic h a r e lo c a t e d o n t h e c ir c le ) a r e la b e le d c o n s e qu e n t ly v1; v

0
1; v2; v

0
2; : : : ; vk; v

0
k,

wh e r e n = 2 k + 1 . S in c e t h e p e r io d ic b o u n d a r y c o n d it io n s a r e a s s u m e d , we id e n t ify t h e
ve r t ic e s vi§k ´ vi a n d v0i§k ´ v0i fo r i = 1 ; 2 ; : : : ; k. Th e s e t o f e d g e s c o n s is t s o f t h r e e s u b s e t s

E ( G ) = F (0) [ F (1) [ F (2) ( 1 4 )

wit h

F (0) = f ( vi; v0i ) : tG ( ( vi; v0i ) ) = 1 ; i = 1 ; 2 ; : : : ; kg ; ( 1 5 )
F (1a) = f ( v0i; u ) : tG ( ( v0i; u ) ) = 2 ; i = 1 ; 2 ; : : : ; kg ; ( 1 6 )
F (1b) = f ( vi; u ) : tG ( ( vi; u ) ) = 3 ; i = 1 ; 2 ; : : : ; kg ; ( 1 7 )
F (1) = F (1a) [ F (1b); ( 1 8 )
F (2) = f ( v0i; vi+1 ) : tG ( ( v0i; vi+1 ) ) = 4 ; i = 1 ; 2 ; : : : ; kg : ( 1 9 )



4 8 Fault-tolerant Gossip Graphs Based on Wheel Graphs

Fig. 1. Wheel graph for odd n (here n=11).

Fig. 2. The illustration of two arbitrary ¯xed vertices in the wheel graph.



V. Hovnanyan, S. Poghosyan and V. Poghosyan 4 9

Fig . 1 illu s t r a t e s t h e wh e e l g r a p h G fo r n = 1 1 ve r t ic e s . Th e n we a p p ly Th e o r e m 1 t o
t h is g r a p h . Fo r a ll p a ir s o f ve r t ic e s in G, we ¯ r s t c o n s t r u c t 3 e d g e -d is jo in t fo ld e d p a t h s fr o m
t h e ¯ r s t ve r t e x t o t h e s e c o n d o n e . Fo r i; j = 1 ; 2 ; : : : ; k a n d j 6= i; i ¡ 1 ; i + 1 ; i + 2 ( s e e Fig .
2 fo r illu s t r a t io n ) we h a ve

² fr o m vi t o u

{ vi
3¡! u

{ vi
1¡! v0i

2¡! u
{ vi

4¡! v0i¡1
2¡! u

² fo r m u t o v0i

{ u
2¡! v0i

{ u
3¡! vi

1¡! v0i
{ u

3¡! vi+1
4¡! v0i

² fr o m vi t o vj

{ vi
3¡! u 2¡! v0j¡1

4¡! vj
{ vi

1¡! v0i
2¡! u 3¡! vj+1

4¡! v0j
1¡! vj

{ vi
4¡! v0i¡1

2¡! u 3¡! vj

² fo r m vi t o v0j

{ vi
3¡! u 2¡! v0j

{ vi
1¡! v0i

2¡! u 3¡! vj
1¡! v0j

{ vi
4¡! v0i¡1

2¡! u 3¡! vj+1
4¡! v0j

² fr o m v0i t o vj

{ v0i
2¡! u 3¡! vj+1

4¡! v0j
1¡! vj

{ v0i
1¡! vi

3¡! u 2¡! v0j¡1
4¡! vj

{ v0i
4¡! vi+1

1¡! v0i+1
2¡! u 3¡! vj

² fr o m v0i t o v0j

{ v0i
2¡! u 3¡! vj

1¡! v0j
{ v0i

1¡! vi
3¡! u 2¡! v0j

{ v0i
4¡! vi+1

1¡! v0i+1
2¡! u 3¡! vj+1

4¡! v0j



5 0 Fault-tolerant Gossip Graphs Based on Wheel Graphs

Th e e d g e -d is jo in t fo ld e d p a t h s fo r j = i; i ¡ 1 ; i + 1 ; i + 2 a r e s h o r t e r ; t h e y h a ve le s s o r e qu a l
fo ld e d n u m b e r s a n d a r e e a s ie r t o c o n s t r u c t . Th e r e fo r e , t h e y a r e n o t p r e s e n t e d h e r e in o r d e r
t o a vo id a n a r t i¯ c ia l g r o wt h o f t h e t e xt . Fin a lly, we h a ve

jF (0)j = ( n ¡ 1 ) = 2 ; jF (1)j = n ¡ 1 ; jF (2)j = ( n ¡ 1 ) =2 ; ( 2 0 )
p = 3 ; r0 = r1 = r2 = 1 ; q = 3 ; ( 2 1 )

fr o m wh ic h we o b t a in w ¸ k + 3 a n d
k+3X

i=0

jF (i m od 3)j =

8
<
:

2
3
( n ¡ 1 ) k + 5

2
( n ¡ 1 ) ; if ( k m o d 3 ) = 0

2
3
( n ¡ 1 ) ( k ¡ 1 ) + 7

2
( n ¡ 1 ) ; if ( k m o d 3 ) = 1

2
3
( n ¡ 1 ) ( k ¡ 2 ) + 4 ( n ¡ 1 ) ; if ( k m o d 3 ) = 2

( 2 2 )

Fo r e ve n n, we m o d ify t h e wh e e l g r a p h b y a d d in g a n e w ve r t e x u0 a n d t r a n s fo r m in g t h e
e d g e s e t t o t h e fo llo win g e xp r e s s io n

E ( G ) = F (0) [ F (1) [ F (2) ( 2 3 )

Fig. 3. Wheel graph for odd n (here n=12).

wit h

F (0) = f( vi; v0i ) : tG ( ( vi; v0i ) ) = 1 ; i = 1 ; 2 ; : : : ; kg ; ( 2 4 )
F (1a) = f( v0i; u ) : tG ( ( v0i; u ) ) = 2 ; i = 1 ; 2 ; : : : ; kg ; ( 2 5 )

ea = ( u; u
0 ) ; tG ( ea ) = 3 ; ( 2 6 )

F (1b) = f( vi; u0 ) : tG ( ( vi; u0 ) ) = 4 ; i = 1 ; 2 ; : : : ; kg ; ( 2 7 )
eb = ( u; u

0 ) ; tG ( eb ) = 5 ; ( 2 8 )

F (1) = F (1a) [ F (1b) [ fea; ebg; ( 2 9 )
F (2) = f( v0i; vi+1 ) : tG ( ( v0i; vi+1 ) ) = 6 ; i = 1 ; 2 ; : : : ; kg : ( 3 0 )



V. Hovnanyan, S. Poghosyan and V. Poghosyan 5 1

H e r e t h e ve r t ic e s u a n d u0 a r e c o n n e c t e d b y t wo e d g e s ea a n d eb. Th e g r a p h G fo r n = 1 2
ve r t ic e s is s h o wn in Fig . 3 . Co n s t r u c t in g t h e e d g e -d is jo in t fo ld e d p a t h s , o n e o b t a in s

jF (0)j = ( n ¡ 2 ) = 2 ; jF (1)j = n; jF (2)j = ( n ¡ 2 ) = 2 ; ( 3 1 )
p = 3 ; r0 = r1 = r2 = 1 ; q = 3 ; ( 3 2 )

wh ic h r e s u lt s w ¸ k + 3 a n d

k+3X

i=0

jF (i m od 3)j =

8
<
:

1
3
( 2 n ¡ 1 ) k + 5

2
n ¡ 4 ; if ( k m o d 3 ) = 0

1
3
( 2 n ¡ 1 ) ( k ¡ 1 ) + 7

2
n ¡ 5 ; if ( k m o d 3 ) = 1

1
3
( 2 n ¡ 1 ) ( k ¡ 2 ) + 4 n ¡ 5 ; if ( k m o d 3 ) = 2

( 3 3 )

Fr o m E q. ( 2 2 ) fo r o d d n a n d E q. ( 3 3 ) fo r e ve n n t h e fo llo win g t h e o r e m h o ld s .

T heor em 2: In k fault-tolerant gossip schemes the upper bound of ¿ ( n; k ) minimum needed
calls satis¯es the following condition:

¿ ( n; k ) · 2
3

nk + O ( n) : ( 3 4 )

4 . S p e c ia l Ca s e s : k = 1 ; 2

Fin a lly, we c o n s id e r t h e s p e c ia l c a s e s wh e n k = 1 a n d k = 2 . In t h e s e c a s e s t h e c o n s t r u c t io n
o f t h e k fa u lt -t o le r a n t g r a p h b e c o m e s s im p le r . W e p r e s e n t it h e r e , wit h o u t c o n s id e r in g t h e
d e t a ils :

¿ ( n; 1 ) · 2 n ¡ 3 +
jn

2

k
; ¿ ( n; 2 ) · 2 n ¡ 3 + n: ( 3 5 )

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 t h e 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 , wit h in t h e
fr a m e wo r k 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 c a d e m i-
c ia n . 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 a t 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 athematics, 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 ournal on Algebraic D iscrete M eth-
ods, 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 " , Canadian
M athematical B ulletin., 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 Archief voor W iskunde 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 ournal on D iscrete M athemat-
ics, vo l. 1 , p p . 1 0 9 -1 2 0 , 1 9 8 8 .



5 2 Fault-tolerant Gossip Graphs Based on Wheel Graphs

[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 ] 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 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 iscrete M athematics, 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 ournal

on Algebraic D iscrete M ethods, 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 ournal on Algebraic D iscrete M ethods, 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 ecture Notes in Computer Science, vo l. 6 9 8 6 , p p . 2 0 3 -2 1 4 , 2 0 1 1 .
[1 7 ] S . M. H e d e t n ie m i, S . T. H e d e t n ie m i a n d 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 8 ] 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 .

[1 9 ] 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 0 ] 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 1 ] 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 2 ] K . Me n g e r , \ Zu r a llg e m e in e n K u r ve n t h e o r ie " , F und. M ath. vo l. 1 0 , p p . 9 6 { 1 1 5 , 1 9 2 7 .

Submitted 25.08.2014, accepted 27.11.2014.

Wheel ·ñ³ýÝ»ñÇ íñ³ ÑÇÙÝí³Í k-Ñáõë³ÉÇáõÃÛ³Ùµ gossip ·ñ³ýÝ»ñ

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

²Ù÷á÷áõÙ

Gossip ËݹÇñÁ (Ñ»é³ËáëÝ»ñÇ ËݹÇñÁ) ÇÝýáñÙ³ódzÛÇ ï³ñ³ÍÙ³Ý ËݹÇñ ¿, áñï»Õ
ѳÕáñ¹³ÏóáõÃÛ³Ý ó³ÝóÇ n ѳݷáõÛóÝ»ñÇó Ûáõñ³ù³ÝãÛáõñÁ ïÇñ³å»ïáõÙ ¿ áñ¨¿ »½³ÏÇ
ÇÝýáñÙ³ódzÛÇ, áñÁ å»ïù ¿ ÷á˳ÝóíÇ µáÉáñ Ùݳó³Í ѳݷáõÛóÝ»ñÇÝ` û·ï³·áñÍ»Éáí
ѳݷáõÛóÝ»ñÇ ½áõÛ·»ñÇ ÙÇç¨ »ñÏÏáÕÙ³ÝÇ Ñ³Õáñ¹³ÏóáõÃÛáõÝÁ: îñí³Í »ñÏáõ ѳݷáõÛóÝ»ñÇ
ÙÇç¨ ½³Ý·Ç Å³Ù³Ý³Ï ¹ñ³Ýù ÷á˳ݳÏáõÙ »Ý ³Û¹ å³ÑÇÝ Çñ»Ýó ѳÛïÝÇ áÕç



V. Hovnanyan, S. Poghosyan and V. Poghosyan 5 3

ÇÝýáñÙ³ódzÝ: ²Ûë Ñá¹í³ÍáõÙ Ù»Ýù ¹Çï³ñÏáõÙ »Ýù k Ñáõë³ÉÇáõÃÛ³Ùµ gossip ËݹÇñÁ,
áñÁ ÁݹѳÝáõñ gossip ËݹñÇ ÁݹѳÝñ³óáõÙÝ ¿, »ñµ ÃáõÛɳïñí³Í »Ý ½³Ý·»ñÇ
³Ù»Ý³ß³ïÁ k å³ï³Ñ³Ï³Ý ˳÷³ÝáõÙÝ»ñ: ÊݹÇñÁ ϳ۳ÝáõÙ ¿ ½³Ý·»ñÇ ³ÛÝ
¿ ( n; k ) Ýí³½³·áõÛÝ ù³Ý³ÏÁ ·ïÝ»Éáõ Ù»ç, áñÇ ¹»åùáõ٠ϳå³ÑáííÇ ÇÝýáñÙ³ódzÛÇ
³ÙµáÕç³Ï³Ý ï³ñ³ÍáõÙÁ: Ø»Ýù ݳ˳·Í»É »Ýù k Ñáõë³ÉÇáõÃÛ³Ùµ íóñ³Ï³ÛáõÝ gos-
sip ë˻ٳ (½³Ý·»ñÇ Ñ³çáñ¹³Ï³ÝáõÃÛáõÝ), áñå»ë½Ç ·ïÝ»Ýù ¿ ( n; k ) -Ç Ñ³Ù³ñ í»ñÇÝ
ë³ÑÙ³ÝÝ»ñ, áñáÝù ϵ³ñ»É³í»Ý ݳËáñ¹ ³ñ¹ÛáõÝùÝ»ñÁ n-Ç ¨ k-Ç áñáß³ÏÇ ÷áùñ
³ñÅ»ùÝ»ñÇ ¹»åùáõÙ:

k-òîëåðàíòíûå gossip ãðàôû îñíîâàííûå íà wheel ãðàôîâ
Â.Îâíàíÿí, Ñ. Ïîãîñÿí è Â. Ïîãîñÿí

Àííîòàöèÿ

Ïðîáëåìîé gossip (ïðîáëåìîé òåëåôîíîâ) ÿâëÿåòñÿ ïðîáëåìà ðàñïðîñòðàíåíèÿ
èíôîðìàöèè, ãäå êàæäûé èç n óçëîâ ñåòè ñâÿçè èìååò óíèêàëüíûé ôðàãìåíò
èíôîðìàöèè, êîòîðûé äîëæåí áûòü ïåðåäàí âñåì îñòàëüíûåì óçëàì ñ ïîìîùüþ
äâóñòîðîííåé ñâÿçè (òåëåôîííûå çâîíêè) ìåæäó ïàðàìè óçëîâ. Ïîñëå âûçîâà
ìåæäó äàííûìè äâóìÿ óçëàìè, îíè îáìåíèâàþòñÿ âñåé èíôîðìàöèåé, èçâåñòíîé
èì â äàííûé ìîìåíò.  ýòîé ñòàòüå, ìû èññëåäóåì k-îòêàçîóñòîé÷èâóþ gos-
sip ïðîáëåìó, êîòîðàÿ ÿâëÿåòñÿ îáîáùåíèåì çàäà÷è gossip, ãäå íàèáîëåå k
ïðîèçâîëüíûõ ñáîéíûõ âûçîâîâ ðàçðåøåíû. Ïðîáëåìà â òîì, ÷òîáû íàéòè
ìèíèìàëüíîå êîëè÷åñòâî çâîíêîâ ¿ ( n; k ) , íåîáõîäèìûõ äëÿ îáåñïå÷åíèÿ ïîëíîãî
ðàñïðîñòðàíåíèÿ èíôîðìàöèè. Ìû ïîñòðîèëè k-îòêàçîóñòîé÷èâóþ gossip ñõåìó
(ïîñëåäîâàòåëüíîñòè âûçîâîâ) ñ öåëüþ íàéòè âåðõíèå ãðàíèöû ¿ ( n; k ) , êîòîðàÿ
óëó÷øàåò ðàíåå èçâåñòíûå ðåçóëüòàòû äëÿ íåêîòîðûõ ìàëûõ çíà÷åíèé n è k.