IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, VOL. 8, NO. 5, MAY 1997
`
`449
`
`Optimal Polling in Communication Networks
`
`Adele A. Rescigno
`
`Abstract—Polling is the process in which an issuing node of a communication network (polling station) broadcasts a query to every
`other node in the network and waits to receive a unique response from each of them. Polling can be thought of as a combination of
`broadcasting and gathering and finds wide applications in the control of distributed systems. In this paper, we consider the problem
`of polling in minimum time. We give a general lower bound on the minimum number of time units to accomplish polling in any
`network and we present optimal polling algorithms for several classes of graphs, including hypercubes and recursively
`decomposable Cayley graphs.
`
`Index Terms—Communication networks, polling, spanning trees, hypercubes, Cayley graphs.
`
`—————————— F ——————————
`
`B
`
`1 INTRODUCTION
`ROADCASTING in a communication network is the proc-
`ess of information dissemination in which a message is
`routed from a special node, called the originator, to every
`other node in the network. Scattering is the process in
`which the originator wishes to route a different message to
`each of the other nodes in the network. Gathering is the
`inverse process of scattering, that is, every node has its own
`unique message that must be routed to a specified node
`called the destination. Polling combines both broadcasting
`and gathering for a specified node, called the polling station.
`The polling station broadcasts a query to every other node
`in the network and waits to receive a unique response from
`each of them.
`In this paper, we study the time complexity of optimal
`polling algorithms in communication networks.
`Polling finds wide applications in the control of distrib-
`uted systems. In computer networks, it is a technique fre-
`quently used for terminal handling [31]. Furthermore, there
`are a number of situations in distributed databases man-
`agement where polling occurs: Reconfiguration after a fail-
`ure or a service restoration [30], updating of replicated
`copies of an object and maintenance of consistency [14], and
`locking to synchronize reading and writing operations [8].
`More recently, polling was proposed as a technique for
`condition monitoring in active databases [11]. Even though
`traditional DBMSs are passive, there is a large class of non-
`traditional applications, such as process control, threat as-
`sessment and analysis, air traffic control, Computer Inte-
`grated Manufacturing, and cooperative problem solving,
`that need to react (often subject to time constraints) to a
`variety of conditions that change the state of the database.
`In this context, polling is used to detect whether any of the
`conditions become true.
`While the related problem of broadcasting in intercon-
`nection network has received considerable attention in the
`
`¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥
`
`• The author is with the Dipartimento di Informatica ed Applicazioni, Uni-
`versità di Salerno, 84081 Baronissi (SA), Italy.
` E-mail: rescigno@dia.unisa.it.
`Manuscript received 13 Oct. 1994.
`For information on obtaining reprints of this article, please send e-mail to:
`transpds@computer.org, and reference IEEECS Log Number D95232.
`
`past few years (see [23], [16], [22]), the problem of deter-
`mining the time complexity of polling algorithms seems to
`have escaped the attention of the researchers in the area.
`For results on problems similar to polling see [12], [33] and
`references quoted therein. As we will see, the problem of
`polling in minimum time, besides its practical interest re-
`called above, poses some new interesting challenges in the
`area of information dissemination in communication net-
`works. It is the purpose of this paper to initiate a detailed
`study of this problem. We will first provide a general lower
`bound on the minimum number of time units to perform
`polling in any network. The lower bound is expressed in
`terms of the diameter of the network, the minimum node
`degree and the number of nodes of the network. Subse-
`quently, we will give optimal time polling algorithms for
`several classes of interconnection networks.
`A common approach to implement communication algo-
`rithms on interconnection networks is to embed a spanning
`tree with special properties on those networks. The root of
`the tree corresponds to the origin of the messages and the
`links of the embedded tree are used for message transmis-
`sions. Following this approach, we show that the lower
`bound on the polling time can be reached provided that the
`graph G contains a particular spanning tree rooted at the
`polling station u, called Polling Tree PTu(G). We do so by
`presenting a polling algorithm that requires the minimum
`number of time units when using PTu(G). In particular, the
`time our polling algorithm requires when u is the polling
`station is two if D(u) = 1, and is max{ Ø(N - 1)/d(u)ø + 2,
`2D(u)} if D(u) ‡ 2; here D(u) and d(u) represent the maxi-
`mum distance from u and the degree of u in G, respectively,
`and N is the number of nodes in G. Moreover, we show that
`members of a large class of graphs used for interconnection
`networks in parallel computers contain Polling Trees, thus
`admitting optimal polling algorithms: In particular, hyper-
`cubes and recursively decomposable Cayley graphs contain
`Polling Trees.
`It should be pointed out that the naive approach to per-
`form polling by first broadcasting the query and then gath-
`ering the responses sums up to a poor polling algorithm.
`Indeed, to broadcast from a node u in G under the model
`
`1045-9219/97/$10.00 © 1997 IEEE
`
`APPL-1037 / IPR2018-00395
`Apple v. Uniloc / Page 1 of 13
`
`

`

`450
`
`IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, VOL. 8, NO. 5, MAY 1997
`
`but only one response can be returned on a link dur-
`ing a communication step.
`Conditions 1–4 characterize the communication model
`known as All Ports—Full Duplex. This model has been
`widely studied since it seems well to reflect hardware char-
`acteristics (see [23], [16], [25] and references quoted therein
`for more on these questions). In fact, it represents the
`maximal communication capability that a loosely coupled
`multiprocessor could possibly have.
`Constraint 5 forbids the concatenation of responses of
`different nodes into a unique message; this is usually as-
`sumed to avoid the propagation of messages of growing
`(and variable) length inside the network that would con-
`tradict hypothesis 5) (for more on these questions see [4],
`[5], [7], [17]). The problem of polling in trees using a differ-
`ent model has been considered in [13].
`The polling time of a node u in a graph G, denoted by Pu(G),
`is the minimum number of time units required to complete
`the polling in graph G if u ˛ V is the polling station. The
`polling time of a graph G, denoted by P(G), is the maximum
`polling time Pu(G) for any polling station u in G. In the fol-
`lowing, we will denote by Q the query that u sends to every
`other node in G and by Rx the response that a node x ˛ V \ {u}
`must transmit to u.
`
`3 THE LOWER BOUND
`In this section, we present a lower bound on the polling
`time of a graph G. We first introduce the basic terminology
`and notation. Given a graph G = (V, E) and a node u ˛ V,
`let us denote by d(u) the degree of u in G, by dist(u, v) the
`distance between two nodes u and v, and by D(u ) =
`maxv˛Vdist(u, v). As usual, d(G) = minu˛Vd(u) and D(G) =
`maxu˛VD(u) denote the minimum degree in G and the di-
`ameter of G, respectively. Let N(u) = {v|dist(u, v) = 1} be the
`set of neighbors of u in G.
`Given a tree Tr rooted in r ˛ V(Tr), let depth(x), for x ˛
`V(Tr), denote the length of the path from the root r to the
`0 5
`2
`7
`=
`. We will call
`˛max
`node x and height T
`depth x
`2
`7
`r
`x V Tr
`main subtrees of Tr the subtrees of Tr rooted at the sons of its
`root r. Let us denote by Nz the number of descendants of
`z ˛ V(Tr) in Tr. A descendant of z is assumed to be different
`from z itself.
`THEOREM 1. Let G = (V, E) be a graph and let N = |V|. The
`polling time Pu(G) of a node u ˛ V in G is
`2
`
`0 5
`
`if D u
`0 5
`0 5
`B
`
`D u if D u
`
`=
`‡
`
`
`
`1,
`
`
`
`2.
`
`max
`
`=
`
`0
`
`N
`
`5
`1
`
`/
`
`0 5
`d u
`
`-
`
`+
`
`
`
`2 2,
`
`%&K ’K
`
`0
`P G
`u
`
`5
`
`‡
`
`PROOF. It is obvious that Pu(G) ‡ 2 (actually, equal to 2) if
`D(u) = 1. Assume now that D(u) ‡ 2.
`Let us first notice that the query Q must reach each
`node in G, and, in particular, a node w at distance
`D(u) from u. Since the response Rw must go back to u,
`it easily follows that Pu(G) ‡ 2D(u).
`
`we use (all ports-full duplex) requires at least a number of
`time units equal to the maximum distance D(u) from u in G.
`Furthermore, during the gathering of the responses to the
`destination u, node u can receive the responses only
`through its neighbors; in particular, there exists at least a
`neighbor that must transmit at least Ø(N - 1)/d(u)ø re-
`sponses to u, and at least one of the responses is at distance
`D(u) from u. Since in our communication model just one
`response can go through a link at a time, the gathering re-
`quires at least max{Ø(N - 1)/d(u)ø, D(u)} time units. This
`implies that to perform polling by first broadcasting and
`then gathering requires time D(u) + max{Ø (N - 1)/d(u)ø,
`n
`-2
`+
`1 , if n > 4,
`D(u)}. In particular, this would give an n
`n
`time units polling algorithm for the n-dimensional hyper-
`0
`5
`-
`3
`1
`n
`+
`!
`, if n > 2, time units polling algo-
`cube, a
`2
`+
`,1
` if n > 2, time
`rithm for the n-star graph, and a cn
`1
`units polling algorithm for the n-pancake graph.1 Compar-
`ing the above quantities with our results presented in Theo-
`rem 3 and Corollary 5, and Theorem 4 and Corollary 6, re-
`spectively, we can conclude that our polling algorithm has
`a significantly better performance than the naive algorithm.
`Indeed, our polling algorithm takes advantage of the possi-
`bility of sending responses before the broadcasting process
`is completed.
`The rest of the paper is organized as follows. The com-
`munication model is defined in Section 2. In Section 3, we
`establish a lower bound on the polling time of any graph,
`and, in Section 4, we give a tree-based polling algorithm
`that achieves the lower bound when a Polling Tree is used.
`Finally, Section 5 is devoted to the construction of Polling
`Trees for hypercubes and recursively decomposable Cayley
`graphs, respectively.
`A list of the main symbols used in this paper along with
`their definitions is given in the Appendix.
`
`11
`--
`nn
`
`--!
`nn
`
`2 COMMUNICATION MODEL
`The network is modeled by a connected graph G = (V, E)
`with the vertices corresponding to nodes (processors) and
`the edges corresponding to communication links. In the
`following, the terms node and vertex will be used inter-
`changeably, as well as the terms link and edge.
`The polling is accomplished according to the following
`constraints:
`1) only adjacent nodes can communicate,
`2) each node can use all its links during a communica-
`tion step,
`3) messages between adjacent nodes can travel the con-
`necting link in both directions during a communica-
`tion step,
`4) each communication, that is the transmission of a
`message between adjacent nodes, requires one unit of
`time,
`5) responses can be accumulated at any internal node,
`
`1. See [19] for the value of the constant c that appears in the lower bound
`on the diameter of the n-pancake graph.
`
`APPL-1037 / IPR2018-00395
`Apple v. Uniloc / Page 2 of 13
`
`

`

`RESCIGNO: OPTIMAL POLLING IN COMMUNICATION NETWORKS
`
`451
`
`We will show now that Pu(G) ‡ Ø(N - 1)/d(u)ø + 2.
`Notice that the response of each neighbor x ˛ N(u) of
`the polling station u reaches u at time ‡ 2; further-
`more, the response of a node whose distance from u is
`‡ 2 can reach u only at time unit t > 3. Since there ex-
`ists at least a neighbor of u that will forward to u at
`0 5
`- -1
`d u
`least N
` responses (except for its own response),
`0 5
`d u
`we get that
`0
`5
`P G
`u
`
`+
`
`2.
`
`" ##
`
`-
`1
`0 5
`u
`
`N d
`
`(cid:31)
`
`+
`
`3
`
`=
`
`" ###
`
`0 5
`- -
`1
`d u
`0 5
`d u
`
`N
`
`(cid:31)
`
`‡
`
`ⵧ
`
`REMARK 1. If D(u) = 1, that is u is directly connected to every
`node in G, then PTu(G) has (N - 1) main subtrees, each
`consisting of one node.
`EXAMPLE 1. Given the graph G in Fig. 1a, a Polling Tree of G
`rooted at node 4 is showed in Fig. 1b; notice that D(4)
`= 3 and d(4) = 2, then condition 1 of Definition 1 must
`be satisfied. A Polling Tree of G rooted at node 5 is
`showed in Fig. 1c; notice that D(5) = 4 and d(5) = 3,
`then condition 2 of Definition 1 must be satisfied.
`
`Fig. 1. (a) Graph G on N = 14 nodes; (b) Polling Tree of G rooted at 4;
`(c) Polling Tree of G rooted at 5.
`
`Let Tu(G) be any spanning tree of G rooted at u. We shall
`first describe an easy polling algorithm using Tu(G). Subse-
`quently, we shall prove the optimality of the algorithm if
`the used spanning tree is a PTu(G), in case it exists for G.
`Assume that each node knows the graph topology, the
`identity of polling station u,2 and that each node x con-
`structs by itself a same spanning tree Tu(G) rooted at u; this
`will be the case if the procedure which constructs Tu(G) is
`identical at all the nodes. The procedure performed by each
`node x in a polling execution, using Tu(G), is as follows.
`Node x waits until receiving the query from its parent in
`Tu(G); then it sends its response to the parent and delivers
`the query to its sons in Tu(G). When x receives responses
`from its sons, it sends them, one at a time, to its parent.
`Therefore, the query travels from the polling station u to the
`leaves in Tu(G), while each response propagates from any
`node to u along the edges of Tu(G). We will denote by
`POLLING(Tu(G)) the polling algorithm that uses the span-
`ning tree Tu(G). The algorithm is shown in Fig. 2.
`The correctness of algorithm POLLING(Tu(G)), i.e., the
`respect of the constraints of our communication model, is
`obvious from the above description.
`We now derive some useful results related to the algo-
`rithm POLLING(Tu(G)). In the following, we will say that a
`response is delayed at a node x if the difference between its
`
`2. Notice that this is not a restriction since a node can know u’s identity
`after receiving the query.
`
`By the definition of polling time of a graph G, the fol-
`lowing corollary is immediate.
`COROLLARY 1. Let G = (V, E) be a graph and let N = |V|. The
`polling time P(G) of G is
`2
`
`max
`
`=
`
`0
`
`N
`
`5
`1
`
`-
`
`/
`
`d
`
`0
`G
`
`5
`
`+
`
`
`
`2 2,
`
`0
`
`if D G
`0
`5
`0
`B
`
`D G if D G
`
`5
`5
`
`=
`‡
`
`
`
`1,
`
`
`
`2.
`
`%&K ’K
`
`0
`P G
`
`5
`
`‡
`
`There are classes of graphs for which above lower bound
`can be easily matched, the easy proof of the following cor-
`ollary is left to the reader.
`COROLLARY 2. The polling time of
`1) the complete graph is 2;
`2) the path on N vertices is 2(N - 1);
`3) the cycle on N vertices is 2ºN/2ß;
` n1 £
`‡
`4) the complete multipartite graph K
`,
`,
`2
`k
`nk
`… £ nk, is Ø(n1 + … + nk - 1)/(n1 + … + nk-1)ø + 2; in
`particular, for the complete bipartite graph Kn,m, m £ n,
`is Ø(n + m - 1)/mø + 2.
`
`,
`
`K
`,
`
`n
`1
`
`4 POLLING ALGORITHM
`In this section, we give a sufficient condition for any graph
`G to admit an optimal time polling algorithm. The condi-
`tion is based on the existence of a particular spanning tree
`of G, that we will call Polling Tree, defined below. Subse-
`quently, we will show that a large class of graphs contains
`Polling Trees.
`DEFINITION 1. We call Polling Tree of G rooted at u, PTu(G),
`any rooted spanning tree of G with root u having d(u)
`main subtrees, Tr = (V(Tr), E(Tr)) for r ˛ N(u), where each
`Tr has the following properties:
`if 2D(u) > Ø(N - 1)/d(u)ø + 2 then
`1.1) height(Tr) £ D(u) - 1;
`1.2) there are at most two nodes in Tr at depth 艎, for each
`艎 £ height(Tr) - 1; there is exactly one node at depth
`艎 = height(Tr);
`otherwise
`2.1) |V(Tr)| ˛ {Ø(N - 1)/d(u)ø, º(N - 1)/d(u)ß};
`2.2) there are at least two nodes at each depth 艎 £
`height(Tr) - ar, where
`2
`7
`1
`if V T
`2
`7
`if V T
`
`=
`
`„
`
`0
`0
`
`N
`
`N
`
`5
`1
`5
`1
`
`/
`
`/
`
`0 5
`d u
`0 5
`d u
`
`-
`
`-
`
`,
`
`.
`
`r r
`
`2
`
`%&K ’K
`
`=
`
`a
`r
`
`APPL-1037 / IPR2018-00395
`Apple v. Uniloc / Page 3 of 13
`
`

`

`452
`
`IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, VOL. 8, NO. 5, MAY 1997
`
`Now we analyze the time required by the polling algo-
`rithm POLLING(Tu(G)) when Tu(G) = PTu(G) and we prove
`that it matches the lower bound given in Theorem 1.
`THEOREM 2. The algorithm POLLING(PTu(G)) requires two
`units of time if D(u) = 1, and max{Ø(N - 1)/d(u )ø + 2,
`2D(u)} units of time if D(u) ‡ 2.
`
`POLLING(Tu(G))
`forfor x ˛ V dodo in parallel
`in parallel
`
`ifif Q is received thenthen, in the next
`step, send Q to all the sons in Tu(G)
`and send Rx to the parent in Tu(G);
`
`whilewhile there are responses of descen-
`dants dodo send a response to the par-
`ent in Tu(G).
`
`endforendfor
`
`Fig. 2. Polling algorithm using Tu(G).
`
`departure time from node x and its arrival at x is strictly
`larger than one.
`LEMMA 1. Let x, z ˛ V \ {u} and let x be a descendant of z in
`Tu(G). Let q and t be the times in which z receives the
`query Q and the response Rx during the execution of algo-
`rithm POLLING(Tu(G)), respectively. If Rx is delayed in z
`then the following conditions must hold:
`1) the number of sons of z in Tu(G) is ‡ 2;
`2) z has sent its response at time q + 1 and it has sent re-
`sponses of its descendants in each time t, for q + 3 £ t £ t ;
`3) Rx starts from z in a time £ Nz + q + 2.
`PROOF. Assertion 1 is obvious, let us prove condition 2. Let
`z = a0, a1, a2, L, aᐉ, aᐉ +1 = x be the nodes on the path
`from z to x in Tu(G). We assume ᐉ ‡ 1, otherwise, con-
`dition 2 is obviously true. If z receives the query at
`time q then, according to POLLING(Tu(G)), it sends its
`response at time q + 1. To complete the proof of con-
`dition 2, let us proceed by contradiction. Suppose that
`z does not transmit in every time unit t, q + 3 £ t £ t,
`and let t¢ be the smallest time unit in which this oc-
`curs. According to algorithm POLLING(Tu(G)), this
`means that z has no response to transmit at time t¢,
`that is, z had just one response to transmit at time t¢ - 1,
`and none of z’s sons has sent a response to z at time t¢
`- 1. In particular, z has not received a response at time
`t¢ - 1 from a1. This means that a1 has not received a re-
`sponse at time t¢ - 2 from a2. Iterating, we can say that
`aᐉ has not received a response at time t¢ - ᐉ - 1 from x.
`According to algorithm POLLING(Tu(G)), this implies
`that x has no response to send to aᐉ and, in particular,
`x has not any more its response; furthermore, no node
`on the path from x to z has Rx. This means that z has
`already received and sent to its parent the response
`Rx, that is, t < t¢ contradicting the fact that t¢ £ t.
`We now prove condition 3. Denote with delay(z)
`the number of time units during which Rx remains in
`z. By condition 2, z has sent t - q - 2 responses (except
`for its own response, Rz) to its parent before receiving
`Rx. Then,
`
`delay(z) £ Nz - 1 - (t - q - 2).
`Therefore, the time in which Rx leaves z is
`t + delay(z) + 1 £ t + Nz - 1 - (t - q - 2) + 1
`= Nz + q + 2.
`
`(cid:134)
`
`7
` in Definition 1
`.
`
`by 2.1 and the value of
`a
`r
`Suppose, now, that Rx is delayed at some node on the
`path going to u. Let us consider the last node on the
`path to u in which Rx is delayed. Let z be this last an-
`cestor in which Rx is delayed and let hz be the depth
`of z in Tr. Obviously, hz £ height(Tr) - 1. By condition 3
`of Lemma 1, Rx leaves z within time
`
`PROOF. By Remark 1 it is obvious that if D(u) = 1 then the
`time to accomplish polling using POLLING(PTu(G)) is
`two. Let us analyze the case D(u) ‡ 2. Two situations
`can occur.
`Case 1. 2D(u) > Ø(N - 1)/d(u )ø + 2. Let x be a node
`at depth 艎 in some subtree Tr of PTu(G), where r ˛
`N(u) and 0 £ 艎 £ height(Tr). According to the algorithm
`POLLING(PTu(G)), node x receives the query Q from
`its parent at time 艎 + 1 and sends its response to its
`parent at time 艎 + 2. This means that if the response Rx
`is not delayed on the path from x to u, then it arrives
`at u at time 2(艎 + 1). By property 1.1 of Definition 1,
`we can conclude that if no response is delayed, then
`the time to accomplish POLLING(PTu(G)) is 2D(u).
`Let x ˛ V(Tr) be a node whose response Rx is de-
`layed. Let us consider the last node on the path from x
`to u in which Rx is delayed. Let z be the last ancestor
`in which Rx is delayed and let hz be the depth of z in
`Tr. By condition 3 of Lemma 1, the time in which Rx
`reaches u is at most
`Nz + 2(hz + 1) + 1 £ 2(height(Tr) + 1) £ 2D(u).
`(1)
`where the last two inequalities in (1) follow from
`properties 1.2 and 1.1 of Definition 1, respectively; in-
`deed, by property 1.2 of Definition 1, we have Nz £
`2(height(Tr) - hz - 1) + 1. Therefore, by (1), we have
`that even if a response is delayed, it arrives at u in
`time £ 2D(u).
`Case 2. 2D(u) £ Ø(N - 1)/d(u )ø + 2. As in the above
`case, if a node x is at depth 艎 in some subtree Tr of
`PTu(G), where r ˛ N(u) and 0 £ 艎 £ height(Tr), and its
`response Rx is not delayed on the path from x to u,
`then Rx arrives at u at time 2(艎 + 1). We now prove
`that in the Polling Tree PTu(G) it holds 2(艎 + 1) £
`Ø(N - 1)/d (u)ø + 2. In fact, considering that 艎 £
`height(Tr), we have
`5
`2
`7
`3
`l +
`£
`+
`1
`2
`height T
`2
`7
`3
`2
`height T
`2
`7
`2
`1
`a
`V T
`r
`r
`7
`2
`by 2.2 of Definition 1
`5
`0 5
`-
`+
`1
`d u
`2
`
`+
`
`2
`
`a
`r
`
`+
`
`2
`
`8
`1
`
`8
`a
`r
`7
`
`-
`
`+
`
`r r
`
`+
`
`0
`
`N
`
`/
`
`2
`
`0
`2
`
`=
`
`£
`
`=
`
`APPL-1037 / IPR2018-00395
`Apple v. Uniloc / Page 4 of 13
`
`

`

`RESCIGNO: OPTIMAL POLLING IN COMMUNICATION NETWORKS
`
`453
`
` Suppose r = xj, for some 0 £ j £ |Vr| - 1. Let Tr be the
`spanning tree of Hr rooted at r obtained by removing
`the edge
`
`.
`
`(cid:28)(cid:30)(cid:29)
`
`x
`4
`
`+
`
`j
`
`3
`
`V
`r
`
`8
`9
`
`1 2/ mod
`
`-
`
`V
`r
`
`,
`
`x
`4
`
`+
`
`j
`
`3
`
`V
`r
`
`8
`
`1 2/
`
`-
`
`9
`1
`
`+
`
`mod
`
`V
`r
`
`(cid:25)(cid:27)(cid:26)
`
`7
`
`-
`
`1
`
`and
`
`a
`r
`
`=
`
`2
`
`(2)
`Nz + (hz + 1) + 2.
`If z ˛ N(u) (i.e., z = r) then, by (2), the time in which Rx
`reaches u is at most
`|V(Tr)| + 2 £ Ø(N - 1)/d(u )ø + 2.
`Now let z ˇ N(u). We first notice that by proper-
`ties 2.1 and 2.2 of Definition 1, it follows that the
`number of descendants of z in Tr is
`2
`7
`2
`-
`=
`2
`if
`V T
`h
`h
`height T
`r
`z
`z
`r
`2
`7
`2
`V T
`r
`
`-
`
`2
`
`h
`z
`
`7
`1
`
`+
`
`otherwise.
`
`%&K ’K
`
`N
`
`z
`
`£
`
`Therefore, the time in which the response Rx reaches u
`is upper bounded by
`2
`V T
`r
`
`N
`
`+
`
`2
`2
`
`7
`1
`
`+
`
`+ £
`1
`
`7
`
`-
`
`1
` and
`a
`r
`
`=
`
`2
`
`7
`
`+
`
`3
`
`Obviously, Tr is also a spanning tree of Gr. Let us con-
`sider, now, the spanning tree of G rooted at u, whose
`main subtrees are the trees Tr for r ˛ N(u). It is easy to
`verify that this spanning tree is a Polling Tree. Indeed,
`u has |N(u)| sons; furthermore, properties 2.1 and 2.2
`of Definition 1 are immediate by condition 2 in the
`hypothesis and the construction of each Tr.
`(cid:134)
`The above Lemma can be easily applied to the two-
`dimensional toroidal meshes.
`The two-dimensional m · n toroidal mesh Mm,n is the prod-
`uct graph Cm · Cn, where Cm and Cn are the cycles on m and
`n vertices, respectively. Therefore, the node set V(Mm,n) and
`edge set E(Mm,n) of Mm,n are
`V(Mm,n) = {(u, v) | 1 £ u £ m and 1 £ v £ n},
`E(Mm,n) = {((u, v), (u, v(mod n) + 1)), ((u,v), (u (mod m) + 1, v))
`| 1 £ u £ m and 1 £ v £ n}.
`It is immediate to see that for any odd n and any polling
`station (u, v) ˛ V(Mn,n), the two-dimensional toroidal mesh
`Mn,n can be partitioned in four meshes having the same
`even number of nodes. This consideration and the fact that
`meshes with an even number of nodes are Hamiltonian (see
`[32]) imply the following corollary to the above Lemma.
`COROLLARY 4. The two-dimensional n · n toroidal mesh Mn,n,
`with n odd, contains a Polling Tree rooted at any (u, v) ˛
`V(Mn,n). Furthermore, the polling time P(Mn,n) is
`2
`-
`1
`n
`3
`8 =
`P M
`4
`n n,
`5.1 Optimal Polling in the Hypercube
`The hypercube is one of the most popular interconnection
`networks for parallel and distributed computing systems.
`Its topological and fault tolerance properties have been ex-
`tensively studied in several papers (see for instance [6],
`[20], [24], [26], [29]). Thus, the hypercube stays, among the
`interconnection networks, as one of the most interesting
`multicomputer structures.
`As is well known, the hypercube Hn can be presented as
`an undirected graph consisting of 2n vertices labeled by the
`binary representations of the integers 0, 1, L, 2n - 1 and
`such that there is an edge between any two vertices if and
`only if their labels differ in exactly one bit. The diameter of
`Hn and the degree of each node is n. Furthermore, Hn can be
`0 and
`partitioned into two hypercubes of dimension n - 1, Hn
`1 are the subgraphs induced by theHn1 , where Hn0 and Hn
`
`
`
`nodes having labels with 0 and 1 in position n, respectively.
`In this section, we will build recursively a Polling Tree of
`Hn rooted at any node u ˛ {0, 1}n. We will denote it by T n
`u .
`
`2
`.
`
`+
`
`=
`if
`h
`z
`2
`height T
`r
`2
`otherwise
`0 5
`d u
`
`2
`
`,
`
`+
`
`+
`
`/
`
`2
`V T
`r
`
`N
`
`-
`
`7
`5
`1
`
`% &KK ’KK
`
`0
`
`£
`
`z
`
`h
`z
`
`where the last inequality again follows from prop-
`erty 2.1 and the value of ar in Definition 1.
`(cid:134)
`EXAMPLE 1 (continued). Let G be the graph given in Fig. 1a.
`Case 1 of Theorem 2 occurs if the polling algorithm is
`using the Polling Tree rooted at 5 given in Fig. 1c,
`Case 2 of Theorem 2 occurs if the polling algorithm is
`using the Polling Tree rooted at 4 given in Fig. 1b.
`The above theorem immediately gives a sufficient con-
`dition for a graph G to admit an optimal time polling algo-
`rithm when node u is the polling station.
`COROLLARY 3. Given a graph G = (V, E) and a node u ˛ V, if G
`contains a PTu(G), then u can perform polling in G in
`minimum time.
`
`5 OPTIMAL POLLING IN A LARGE CLASS OF GRAPHS
`In this section, we will give a sufficient condition for a
`graph to have a Polling Tree and, thus, an optimal time
`polling algorithm. We also show that members of a large
`class of graphs used for interconnection networks in parallel
`computers contain Polling Trees.
`LEMMA 2. Given a graph G = (V, E) and a node u ˛ V, if it is
`possible to partition the subgraph induced by V \ {u} into
`d(u) subgraphs, Gr = (Vr, Er) for r ˛ N(u), such that
`1) r ˛ Vr,
`2) |Vr| ˛ { Ø(N - 1)/d(u )ø, º(N - 1)/d(u )ß } ,
`3) Gr is Hamiltonian
`for each r, then G contains a PTu(G).
`PROOF. Since Gr is Hamiltonian, we can order the nodes in Vr
`is Hr =
`so
`that
`the Hamiltonian cycle
`in Gr
`
`,
`x x
`1
`k
`
`5
`1
`
`+
`
`k
`
`mod
`
`V
`r
`
`x
`
`0
`
`,
`
`K
`
`,
`
`x
`
`EH
`
`r
`
`=
`
`V
`r
`
`%&’
`
`(cid:25)(cid:27)
`
`%&’
`
`(cid:25)(cid:27)
`
`(cid:28)(cid:30)
`
`()*
`
`-
`
`1
`
`,
`
`EH
`
`r
`
` where
`
`()*
`
`1
`
`.
`
`0
`
`£
`
`k
`
`£
`
`V
`r
`
`-
`
`(cid:28)(cid:30)
`
`APPL-1037 / IPR2018-00395
`Apple v. Uniloc / Page 5 of 13
`
`

`

`454
`
`IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, VOL. 8, NO. 5, MAY 1997
`
`nb
`
`-
`
`1
`
`1
`
`nb
`
`-
`
`nb
`
`b
`-1, for b ˛ {0, 1}, the Polling Tree
`Let n ‡ 6. Denote by Tn
`b rooted at b0 obtained by Tn-1 (the Polling Tree of Hn-1)
`of Hn
`prefixing each binary vector in V(Tn-1) with bit b; that is,
`2
`7
`4
`9
`4
`9
`J
`L
`=
`˛
`=
`x x
`V T
`b
`V T
`V H
`n
`6
`7 1
`2
`2
`7
`4
`9
`J
`L
`˛
`=
`,
`.
`,
`b
`E T
`b
`E T
`x y
`x y
`-
`-
`1
`1
`n
`
`bLet STib , for 1 £ i £ n - 1, be the main subtrees of Tn
`
`-1. It is
`0
`1
`obvious, by the construction of Tn-1
`, that each
` and Tn-1
`0 , for 1 £ i £ n - 1, has the corresponding
`node 0x in STi
`1. Fig. 4a shows a schematic
`1x at its same position in STi
`0
`1
`representation of Tn-1
` and Tn-1
`.
`˝ 4
`9 be the subset obtained by deleting ti
`1
`1
`Let A
`V ST
`i
`i
`1 level by level starting from the deepest
`nodes from STi
`level (i.e., not removing a node at depth 艎 until level 艎 + 1 is
`4
`9 ). The number of nodes ti is cho-
`1
`empty, for l < height STi
`4
`9 , where
`0
`=
`-
`sen so that t
`s
`V ST
`i
`i
`i
`4
`9
`1
`9
`4
`1
`
`mod
`
`n
`
`< £
`i
`
`n
`
`-
`
`
`
`1.
`
`(3)
`
`4
`9
`1
`
`1
`4
`
`n
`
`2
`
`-
`
`n
`
`2
`
`-
`
`/
`
`n
`
`/
`
`n
`
`for
`
`for
`
`%&K ’K
`
`=
`
`s
`i
`
`n
`
`-
`
`2
`
`£ £
`i
`
`n
`
`2
`
`-
`
`9
`1
`
`mod
`
`n
`
`Fig. 3. The Polling Trees Tn for 2 £ n £ 5.
`
`Since Hn is vertex symmetric, without loss of generality, our
`construction consider the node 0 = 0 … 0 as root.
`The polling trees of Hn that we will construct have the
`property that each subtree of the root has almost the same
`number of nodes (i.e., their cardinality differs at most by
`one). We point out that in the literature have been proposed
`other spanning trees of the hypercube with a kind of
`“balance” property, see [9] and [24]. However, the trees
`proposed in [24] have the property that the subtrees of the
`root contain exactly the same number of nodes only for
`particular values of n. The trees proposed in [9] are well
`balanced, in sense that they satisfy property 2.1 of Defini-
`tion 1, but they do not satisfy property 2.2 that is crucial to
`obtain optimal polling time.
`To show the construction of T n
`0 , some definitions are
`necessary: bx will denote the binary vector of length n ob-
`tained by prefixing the binary vector x = xn-1, …, x1 with the
`b and a node
`bit b. Furthermore, given a spanning tree of Hn
`bx (different from the root) in it, we will denote by f(bx) the
`parent of bx in that tree. We also define 0i = 0..010..0, for 1 £
`i £ n, to be the binary vector whose only nonzero bit is in
`position i. In the following we will use Tn to mean T n
`0 .
`For any 2 £ n £ 5, Tn is shown in Fig. 3. It is easy to ver-
`ify, by direct inspection, that such trees are Polling Trees.
`
`APPL-1037 / IPR2018-00395
`Apple v. Uniloc / Page 6 of 13
`
`

`

`RESCIGNO: OPTIMAL POLLING IN COMMUNICATION NETWORKS
`
`455
`
`
`
`1 ; (b) construction of STi, for 1 £ i £ n - 1.Fig. 4. (a) A schematic representation of Tn-10 and Tn-1
`
`
`
`Fig. 3 and the above description of Tn immediately give
`the following lemma.
`LEMMA 3. For n ‡ 2,
`1) Tn is a spanning tree of Hn;
`4
`9
`n
`-
`2
`1
`/
`n
`4
`9
`1
`
`n
`
`-
`
`2
`
`mod
`
`n
`
`< £
`i
`
`.
`n
`
`£ £
`i
`
`n
`
`2
`
`-
`
`9
`1
`
`mod
`
`n
`
`4
`9
`1
`
`1
`4
`
`for
`
`for
`
`n
`
`2
`
`-
`
`/
`
`n
`
`%&K ’K
`
`2
`2) V ST
`i
`
`7
`
`=
`
`The following lemmas give some useful properties of Tn.
`Such properties will help us to prove that Tn is a Polling
`Tree of Hn then proving that Hn admits optimal polling
`algorithms.
`LEMMA 4. For n ‡ 6 and any 1 £ i £ n - 1,
`1
`2‡ ,
`1) Ai
`4
`9 ‡
`1
`2) V ST
`i
`
`+ .
`1
`
`1
`A
`i
`
`PROOF. Noticing that, for any 1 £ i £ n - 1,
`2
`2
`7 -
`4
`9
`0
`1 =
`V ST
`V ST
`V ST
`A
`i
`i
`i
`i
`
`=
`
`7
`
`2
`V STi
`
`7 ˛ 2
`4
`J
`
`n
`
`9
`1
`
`-
`
`/ ,
`n
`
`4
`
`n
`
`2
`
`9
`1
`
`-
`
`/
`
`n
`
`4
`1
`V ST
`i
`
`9 ,
`
`, and
`
`-
`
`L
`
`=
`9
`
`U
`
`7
`
`^ 1 the tree obtained from STi
`1 by de-
`We will denote by ST i
`1.
`leting the nodes in Ai
`Now, we are able to construct Tn by defining its main
`subtrees STi, for 1 £ i £ n. Let 1 £ i £ n - 1, STi is rooted at 0i
`and is defined as follows:
`2
`7
`4
`9
`0
`V ST
`V ST
`i
`i
`2
`2
`4
`J
`0
`=
`1
`0
`,
`x
`x
`E ST
`E ST
`i
`i
`2
`7
`˝ 4
`9 and V ST
`4
`1
`1
`1
`Since A
`V ST
`t
`s
`V ST
`i
`i
`i
`i
`i
`i
`have that each STi is a tree containing si nodes; furthermore,
`the node sets of ST1, L, STn-1 are pairwise disjoint. The
`construction of STi is sketched in Fig. 4b.
`1
` by deleting
`STn is rooted at 10 and is obtained from Tn-1
`1, for 1 £ i £ n - 1.the nodes in Ai1 from each subtree STi
`
`
`Formally,
`
`1U
`A
`i
`7
`
`1
`x
`
`=
`
`˛
`
`1
`A
`i
`9
`
`L
`
`.
`
`+
`
`=
`
`, we
`
`1
`A
`i
`
`11
`=-
`in
`
`\ U
`
`2
`V ST
`n
`
`7
`
`=
`
`4
`1
`V T
`-
`n
`
`1
`
`9
`
`2
`=
`
`0
`1
`x
`
`5
`
`f
`
`7
`B
`.
`
`,
`
`1
`x
`
`xU
`
`1
`
`=-
`in
`
`2
`E ST
`n
`
`7
`
`=
`
`4
`1
`E T
`-
`n
`
`1
`
`9
`
`\
`
`˛
`
`n
`
`-
`
`1
`
`2
`
`-
`
`0
`
`/
`
`n
`
`-
`
`5
`1
`
`,
`
`n
`
`-
`
`2
`
`4
`9
`4
`9
`4
`J
`1
`1
`V ST
`i
`the lemma follows by observing that
`2
`7
`2
`7
`4
`9
`1
`V ST
`V ST
`V ST
`i
`i
`i
`
`-
`
`‡
`
`2
`
`<
`
`9
`1
`
`/
`
`0
`
`n
`
`-
`
`5
`1
`
`L
`
`,
`
`1
`
`-
`
`4
`1
`V ST
`i
`
`9
`
`.
`
`2
`
`(cid:134)
`
`LEMMA 5. For n ‡ 6 and any 1 £ i £ n,
`1) the number of nodes at depth 艎 in STi is at least two, for
`艎 £ height(STi) - 1;
`2) height(STi) £ n - 1.
`
`U
`1
`˛
`11
`A
`i
`It is immediate that STn covers nodes in V(Hn) \ {0} that are
`not covered by STi, for 1 £ i £ n - 1; furthermore,
`-(cid:25)
`2
`7
`4
`9
`(cid:229)
`(cid:229)
`(cid:27)
`1
`V ST
`V T
`s
`-
`n
`n
`i
`4
`
`(cid:25)(cid:27)
`
`n
`
`2
`
`-
`
`9
`1
`
`mod
`
`9
`n
`
`(cid:28)(cid:30)
`
`4
`0
`V ST
`i
`
`9
`
`11
`=-
`in
`
`n
`
`-
`
`1
`
`=
`
`2
`
`-
`
`t
`i
`
`11
`=-
`in
`
`=
`
`-
`
`1
`
`(cid:31)!
`
`
`
`44
`
`=
`
`n
`
`2
`
`- -
`1
`
`n
`
`2
`
`-
`
`n
`
`-
`
`9
`1
`/
`5 4
`1
`
`n
`
`2
`
`9
`1
`
`-
`
`/
`
`n
`
`0
`
`-
`
`n
`
`-
`
`"$#
`(cid:28)(cid:30)
`
`4
`
`n
`
`2
`
`9
`1
`
`-
`
`/
`
`n
`
`=
`
`4
`
`n
`
`2
`
`9
`1
`
`-
`
`/ .
`n
`
`APPL-1037 / IPR2018-00395
`Apple v. Uniloc / Page 7 of 13
`
`

`

`456
`
`IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, VOL. 8, NO. 5, MAY 1997
`
`Such a condition is satisfied by Lemma 3 and Lemma 5.
`Hence, the theorem follows.
`(cid:134)
`COROLLARY 5. For n ‡ 2, the polling time P(Hn) of the hypercube
`with N = 2n nodes is
`2
`
`if
`
`2
`
`n
`
`£
`
`5
`
`,
`
`log
`-
`1
`N
`log
`N
`
`N
`+
`
`%&K ’K
`
`2
`P H
`
`n
`
`7 =
`
`PROOF. The proof is by induction. For n = 6, the lemma can
`be easily proved by direct inspection. Suppose the
`conditions 1 and 2 hold for n - 1, let us verify them
`for n. We distinguish two cases.
`Case 1. Let 1 £ i £ n - 1. By construction, STi is ob-
`tained by adding at most one child to each node of
`
`
`
`0STi0. Since STi0 is a main subtree of Tn-1
`, it has at least
`4
`9
`0
`two nodes at each depth 艎, with l £
`-
`1
`height STi
`(by the induction hypothesis 1). Then, STi has at least
`4
`9
`0
`-
`two nodes at each depth 艎, with l £
`1
`.
`height STi
`0 to obtain STi
`Considering that the nodes joined to STi
`are added level by level starting from the deepest
`level and that condition 1 of Lemma 4 assures that at
`0 , we have both
`least two nodes are added to STi
`2
`7 = height ST
`4
`9 + £
`0
`- and that there are
`1
`1
`