Digitized by the Internet Archive in 2013 http://archive.org/details/faulttolerantbro1029lies X{Cf UIUCDCS-R-80-1029 C.3 FAULT-TOLERANT BROADCAST GRAPHS by Arthur L. Liestman UILU-ENG 80 1728 NOV 191980 August 1980 UIUCDCS-R-80-1029 FAULT -TOLERANT BROADCAST GRAPHS by Arthur L. Liestman August 1980 DEPARTMENT OF COMPUTER SCIENCE UNIVERSITY OF ILLINOIS AT URB ANA-CHAMPAIGN URBANA, IL 61801 This project Is funded in part by NASA Grant NSG 1471. Page 1 1 Introduction * Consider a graph G = (V,E) which represents a communications network. The set V of vertices corresponds to the members of the network and the set E of edges corresponds to communication links connecting pairs of members. One member of the network has a message which is to be disseminated to all the other members. This is to be accomplished as quickly as possible by a series of calls over the network. The series of calls is constrained by the follow- ing: 1. each call requires one unit of time 2. any member may participate in at most one call per time unit 3. a member can only call an adjacent member This process is referred to as ( local ) broadcasting [Mitchell & Hedetniemi, 78]. In the event that a communications link fails the message may not be disseminated to all of the network members. By incorporating redundancy in the calling scheme the completion of the broadcast may be guaranteed in the presence of up to k faults. A _k fault-tolerant broadcast graph is a graph which admits such a scheme. This paper investigates these graphs and the trade off between the time allowed for broadcasting and the number of edges required in the graphs. 2 Definitions . Consider a graph G = (V,E) and a message originator, vertex u. The broadcast time of a vertex u, t(u), is the minimum time required to broadcast from u. The broadcast time of a graph G, t(G), is the maximum broadcast time of any vertex u in G. The notation [xj denotes the smallest integer larger than or equal to x, (x) denotes the largest integer smaller than or equal to x, and log n denotes log_ n. It is easily shown that for K ( the complete Page 2 graph on n vertices, t(K ) = [log nj and that for any connected graph on n vertices t(G) > [log nj . A minimal broadcast graph is a graph G with n ver- tices such that t(G) ■ [log nj but for every proper spanning subgraph G' of G, t(G') > [log a]. The broadcast function B(n) is the minimum number of edges in any minimal broadcast graph on n vertices. A minimum broadcast graph , rabg, is a broad- cast graph on n vertices having B(n) edges. The mbg's represent the cheapest possible communications networks in which broadcasting can be accomplished from any vertex in minimum time. The values of B(n) are determined for n=2 and n<15 [Farley, et al. , 79]. Values of B(n) are also known for n=16, 17 [Mitchell & Hedetniemi, 78]. A census of all mbg's for nt, (G). The k fault-tolerant broadcast function , B_ k (n), is the minimum number of edges in a minimal k fault-tolerant broadcast graph on n vertices. A k fault-tolerant minimal broadcast graph on n vertices with B» v (n) edges is called a Jc fault-tolerant minimum broadcast graph (kftmbg) on n vertices and the set of such graphs is denoted G~ k (n). T« k (n) denotes the time required for k fault-tolerant broadcast in a kftmbg on n vertices. The kftmbg' s represent the cheapest possible communications networks in which k fault- tolerant broadcasting can be accomplished from any vertex as fast as possible. It may be desirable to allow an increase in broadcast time in order to decrease the number of links required in the networks. G , (n) denotes the l , fc set of graphs G with the minimum number of edges such that t, (G) < T~ , (n) + i. These graphs represent the cheapest possible communications networks in which k fault-tolerant broadcasting can be accomplished in no more than i time units beyond the minimum time. T i,( n ) = ^n W^ n ^ + * * s t * ie ^^ me allowed for fault-tolerant broadcasting among the graphs in G k (n). B. t (n) is the number of edges of the graphs in G k (n). When describing a broadcast scheme for a graph G, a call between two adjacent vertices u and v at time t is represented by labelling the edge (u,v) with t. During a call the message may be transmitted in either direc- Page A tion or both directions. If u_ is the message originator and u. is another vertex of G, a sequence of edges (u-.u.), (u.,u 2 ), ..., (u..,u.) labelled t., t_, ..., t respectively with t. n-1, for i>0. 3 « B < u(n) > [((k+l)*n)/2j, for 1 > 0, < k < n-1. 4 * B i k^ * B l-1 k^ for 1>1 » ° < k < n ~ 1# ^ Thls f o llows from T ± k (n) = T Q k (n) + i.) 5. The only kftrabg for k=n-2 is K n since 1^ is the only n-1 edge-connected graph on n vertices. Lemma 3.1j T Q (n) > [log n] + k , for n-1 > k > 0. Page 5 Proof : Consider any k fault-tolerant broadcast scheme for a given graph G and a given message originator u. At least k+1 distinct calls must be made from u otherwise the edges used by the calls from u could all be destroyed with at most k faults and the message would never be disseminated. Any calling scheme must include provisions for all vertices to be notified beginning with the st k+1 call from u. This requires time of at least T_ n (n) after the first k calls. Thus T_ , (n) > T Q Q (n) + k. The lemma is obtained by substituting T Q Q (n) = [log n] [Farley, et al. , 79]. Lemma 3^: In a graph G on n vertices with a vertex of degree k+1, t^(G) > k+1 + [log (n-l)J , for k>0. Proof : Consider any k fault-tolerant broadcast scheme for such a graph G with message originator u. , a vertex of degree k+1. Each of the edges incident with u must be used in the calling scheme and must be labelled with distinct values. The largest such value can be no smaller than k+1. Consider the ver- tex u_ which is called last by u. . From this vertex there must be a calling path to each of u~, u,, ..., u . Any scheme for disseminating the information from u to u~, u,, ..., u requires at least [log (n-l)J time units. Thus t k (G) > k + 1 + [log (n-1)]. Lemma 3.3: If T . (n) = [log nj + k for some k with < k < n-1 and n * 2 J +1 for some j > 1 then B Q k (n) > [(k+2)n/2j. Proof : Consider a k+1 edge-connected graph G with e edges where [(k+l)n/2J < e < [(k+2)n/2j. G has at least one vertex of degree k+1 and hence (from Lemma 3.2) t,(G) > [log (n-1)] + k + 1. By assumption T Q fc (n) = [log n] + k. If n*2^+l then [log (n-1) J + 1 > [log n] and hence t fc (G) > T Q k (n). Thus no such Page 6 G can be in G Q k (n) and B Q k (n) > [(k+2)n/2J. Theorem 3.1: t,(C ) = n , n>3 (where C denotes a cycle of n vertices) In' n Proof: First show that t.(C )3. Consider the cycle C for n>3. Label In' n the message originator 1 and continue to label the vertices in a clockwise direction around the cycle with 2, 3, ..., n. Label the edges as follows: (i,i+l) is labelled i for 23. In To show that n time units are required consider the cycle with vertices labelled as before. Assume that there exists a calling scheme which completes the broadcast in less than n calls. Consider the edges (1,2) and (n,l). One of these must be labelled 1 indicating that the call is made first. Without loss of generality let (1,2) be labelled 1. Consider the two paths from ver- tex 1 to vertex 2. The second path which is currently unlabelled cannot begin until time 2. This path is n-1 edges long and cannot be labelled in order to complete the call before time n. Therefore the broadcast can not be done in time < n. Thus t.(C )=n for n>3. In' Page 7 4 Time Required for Fault- tolerant Broadcasting . In general the exact time required for k fault-tolerant broadcasting on n vertices is not known. The values are determined here for k = 1, 2. Theorem 4.1; T (n) = [log nj + 1 for n>3. Proof ; T_ . (n) > [log nj + 1 from Lemma 3.1. Consider the following calling scheme on K : n Label the message originator 1 and continue labelling the vertices clockwise Z y Jj •••} n. • At time only the message originator (vertex 1) is informed. At time t>0 each informed vertex m calls vertex m+2 . This portion of the scheme creates a tree of calls including each vertex by time [log nj . All vertices with even labels are reached through vertex 2 and the edge labelled 1. Thus the path to any even numbered vertex is disjoint from the path to any odd numbered vertex. At time [log nj + 1 each even numbered vertex calls Page 8 its clockwise neighbor completing 2 calling paths to each vertex 2, 3, . . . , n. Th us T (n) = [log n] + 1 for n>3, Theorem 4.2: T (n) = [log n] + 2 for n>5 and n*2 -1. Proof : T ~(n) > [log nj + 2 from Lemma 3.1. Consider the following calling schemes for 3 cases: If n=2i for some integer i>3 consider a graph K . Label the message ori- ginator 1 and continue to label the vertices clockwise with the values 2, 3, . n, At time only the message originator (vertex 1) is informed. At time 1 vertex 1 calls vertex 4. At time 2 vertex 1 calls vertex 3 and vertex 4 calls vertex 2. ... ii. At time t>3 each informed vertex m calls vertex This portion of the scheme creates a tree of calls including each vertex Page 9 by time [ log nj : All vertices with even labels are reached through vertex 4 and the edge labelled 1. Similarly the vertices m=«4j+3 are reached through vertex 3 and the edge from 1 to 3. Thus the paths to any even vertex and its two odd neighbors are disjoint. At time [log n] + 1 each even numbered vertex calls its counterclockwise neighbor. At time [log nj + 2 each even numbered vertex calls it clockwise neighbor. The last calls complete 3 edge disjoint calling paths to each vertex 2, 3, . .., n. An even numbered vertex receives the message by its own path in the tree and from each of its odd neighbors. An odd numbered vertex receives the message by its own path in the tree, from its clockwise even neighbor, and from the next odd vertex counterclockwise. Consider the case n=4i+3 for some integer i>0 and n*2^-l. Label K as before. At time only the message originator (vertex 1) is informed. Page 10 At time t>l each informed vertex m calls vertex m+2 with the following exceptions: At time [log nj vertex 1 calls vertex n, vertex n-2^ 8 J calls no one, and vertex n _ 2 [log n]-l +2 callg yertex 2 [log n]-l +1- This portion of the scheme creates a tree of calls including each vertex by time [ log nj : ^ 11 10" 7 6 All vertices with even labels are reached through vertex 2 and the edge labelled 1. With the exception of vertex n which is reached directly from 1, the vertices ra=4j+3 are reached through vertex 3 and the edge from 1 to 3. Thus the paths to any even vertex and its two odd neighbors (ignoring vertex 1) are disjoint. At time [log n] + 1 each even numbered vertex calls It counterclockwise neighbor (ignoring vertex 1). At time [log n] + 2 each even numbered vertex calls its clockwise neighbor. These last calls complete 3 disjoint calling paths to each vertex 2, 3, ..., n. An even vertex receives the message through its own path in the tree and from each of Its neighbors. An odd vertex receives the message through its Page 11 own path in the tree, from its clockwise even neighbor, and from the next odd vertex counterclockwise. Now consider the case n=4i+l for some integer i>0. Label the vertices of K as before except that the message originator is labelled rather than 1. At time only the message originator (vertex 0) is informed. At time 1 vertex calls vertex 3. At time 2 vertex calls vertex 2 and vertex 3 calls vertex 5. At time t>2 each informed vertex m calls vertex mf2 t - 1 . This portion of the scheme creates a tree of calls including each vertex by time [log nj : 8 7 All vertices with odd labels are reached through vertex 3 and the edge labelled All vertices m=4j+2 are reached through vertex 2. The paths to any odd vertex and its two even neighbors (ignoring vertex 0) are disjoint. At time [log nj + 1 each even numbered vertex calls its counterclockwise neighbor (ignoring vertex 0). At time [log nj + 2 each even numbered vertex calls Page 12 its clockwise neighbor (ignoring vertex 0). These last calls complete 3 disjoint calling paths to each vertex 2, 3, ..., n. An odd vertex receives the message through its own path in the tree and from each of its even neighbors. An even vertex receives the message through its own path in the tree, from its counterclockwise odd neighbor, and from the next even vertex clockwise. The above calling schemes show that T ft «(n) ■ [log n] + 2 for n>5 and * 2i i n* -1. The following proof is based on an idea from [Richards, 80]. Theore m 4.3; T Q 2 (n) = [log n] + 3 for n=2 i -l, i>3. Proof : Assume T »(n) = [log nj + 2. In order to create three calling paths to each vertex by time [log n] + 2 there must be at least one calling path to every vertex by time [log nj . In order to accomplish this with 2 -1 vertices it is easy to see that at each time unit between 1 and [log nj every informed vertex must call an uninformed vertex except that one vertex is idle at time [ log nj . Thus there is exactly one calling path to each vertex at time [log nj . Since each member must receive calls at times [log nj + 1 and [log nj + 2 the message originator can not participate in any call after time [log nj . Since there must be three calling paths to each vertex at least one of these paths for each vertex must begin from the message originator at time 3 or later. In fact the first call in the path must be labelled 3, 4, ..., or [log nj since the message originator can not call after [log nj . At time time [log nj at most 2L J -°8 n J~ z _i vertices can have such a path. Thus at time [log nj + 2 at most 2^ ° J-4 vertices can have such a path. Therefore it is Page 13 impossible to complete 3 calling paths to each vertex by time [log nj + 2. Thus T Q 2 (n) > [log n ] + 3. The following scheme on K shows that T„ ~(n) - [log n] + 3: Label the n u, z L J message originator 1 and continue labelling the vertices clockwise 2, 3, . .., n. At time only the message originator (vertex 1) is informed. At time t>l each informed vertex m calls vertex m+2 except that vertex n is not called at time [log nj. At time [log nj + 1 vertex 1 calls vertex n. This portion of the scheme creates a tree of calls including each vertex by time [log nj + 1: 15 / 3 \/"W 5 io 6 6 7 9 8 All vertices with even labels are reached through vertex 2 and the edge labelled 1. With the exception of vertex n which is reached directly from n, the vertices m=4j+3 are reached through vertex 3 and the edge from 1 to 3. Thus the paths to any even vertex and it two odd neighbors (ignoring vertex 1) are disjoint. Page 14 At time [log nj + 2 each even numbered vertex calls Its counterclockwise neighbor (ignoring vertex 1). At time [log nj + 3 each even numbered vertex calls its clockwise neighbor. These last calls complete three disjoint calling paths to each vertex 2, 3, . .., n. An even vertex receives the message through its own path in the tree and from each of its neighbors. An odd vertex receives the message through its own path, from its clockwise even neighbor, and from the next odd vertex counterclockwise. 5 Fault-tolerant Broadcasting on Graphs With Fewer Edges . Consider the class of graphs G (n) with i>0. These graphs on n ver- l , K. tices are those with the fewest edges which allow k fault-tolerant broadcast in time T (n)+i. In constructing a network for broadcasting, these graphs represent the sparsest networks which guarantee k fault-tolerant broadcasting in the given time. Theorem 5.1: Given k,n with n-2>k>0, for some i>0 G (n)=C(k+l,n) . 1 ,K P roof : Consider G, a member of C(k+l,n). G is a k+1 edge-connected graph on n vertices. Let vertex u. of G be the message originator. Consider vertex u„ of G. There are k+1 edge-disjoint paths from u. to u~ [Harary, 69]. All of these paths are of length •••i P k+1 such that length of pj < length of p 2 < ... < length of P k+1 . Label p. from u. to u~ with 1, 2, ..., length of p.. Label p ? from u. to u« with 2, 3, ..., length of p 2 +i. Continue labelling each of the paths until pk+1 is Page 15 labelled with k+1, k+2, ..., length of p, +k. The highest label used is length of p, + . + k < n+k-1. Consider the k+1 edge-disjoint paths from u. to u-. Label these as above beginning with n+k instead of 1. Continue until k+1 edge-disjoint paths from u. to each of the other n-1 vertices have been labelled. The largest label necessary in this scheme is <(n+k-l) (n-1) = 2 n +kn-2n-k+l. So G is in G 2^ _ 2 , . k (n). Thus for large enough i, G ,(n) contains C(k+l,n). Let G be a member of G k (n). If G is not in C(k+l,n) for large i then G is either not k+1 edge-connected or has more edges than the members of C(k+l,n). G must be k+1 edge-connected if it is a member of G , (n). For i , K large i the members of C(k+l,n) are in G (n) so B ,(n) = [(k+l)*n/2j. Thus both of the possibilities for G are ruled out and G (n) - C(k+l,n) for large 1 , R enough i. Theorem 5.2: G. (n) = {K } for i>0. i ,n-2 n Proof: Follows from Observation 5. Theorem 5.3: G n (n) ■ {all trees on n vertices} for i>n-[log nj-l. 1 jU Proof : Consider the set of all trees on n vertices. Clearly there are no other 1 edge-connected graphs on n vertices with < n-1 edges. Thus if a tree T is a member of G n (n) for some i, the set contains only trees. I ,u A fault-tolerant broadcast scheme is easily constructed for any tree T. Each edge need only be used once in any such scheme so t.(T) < n-1 for all trees T on n vertices. T o^* ^ log n J + i from Lemma 3.1. Thus if i > n-[log nj-l then G n (n) = {all trees on n vertices}. I I u Page 16 Theorem 5.4; G (n) - {C } for i>n-[log nj-l. Proof: t.(C ) ■ n. T. . (n) > flog n] + 1 + i from Lemma 3.1. C is the smal- lest 2 edge-connected graph on n vertices. If 1 * n-[log nj-l then T (n) > i > l n so G, . (n) = {C }. 1,1 n 6 The Graphs In G. , (n ) . i»_ No general method is known for determining elements of the set G. ,(n). l , fc These sets have been determined for i>0, 00 1=0 1>1 n=5 1=0 k-0 A » • 1=0 1>1 1=0 k-1 A M 4 4 1>1 1>1 n=6 i=0 o -# O oo i>0 k-2 EI i>0 1=0 1>1 Page 18 7 Summary * The set of graphs G_ k (n) represent the cheapest possible communications networks of n members which allow k fault-tolerant broadcasting from any member in minimum time. As i increases the graphs in G (n) represent I ,K. cheaper networks which guarantee k fault-tolerant broadcasting from any member in no more than i time units beyond the minimum time. No general method to construct these graphs is known. For small values of i, k, and n the sets of graphs G (n) have been determined and presented here. The set of graphs 1 , K. G_ (n) contains only K for all n>2. The sets G. , (n) for large i are (J,n— I n 1 ,k known to contain only the minimum k+1 edge-connected graphs on n vertices. No further increase in i will result in a cheaper network in which k fault- tolerant broadcasting can be guaranteed from every member. The value of T~ k.(h), the time required for k fault-tolerant broadcasting in any graph on n vertices, is not known in general. T~ n(n) = [log nj [Far- ley, et al. , 79], T Q ^n) = [log n] + 1 for n>2, T Q 2 (n) = [log n] + 2 for n>5 and n*2 -1, and T_ _(n) = [log nj + 3 for n>5 and n=2 -1. For other appropri- U, L ate values of n,k T k (n) > [log nj + k. B k (n), the number of edges of the graphs in G. k (n), represents the cost of the network. Various bounds on B k (n) are known. Exact values of B (n) are known for small values of i, k, and n and for the following i ,k cases : 1. 1=0, k=0, n=2 : ', j>0. [Farley, et al. , 79] 2. i>0, k=n-2, n>2. 3. large 1, k