text: used to characterize the ﬁnite time stability boundary, and Theorem 17 implicates that the normal expansion rate can be used as a stability certiﬁcate for online monitoring. ∈ Theorem 16. For any ﬁnite time interval T > 0 and x0 Ws(xe), there exists an ε > 0 such that, following condition is satisﬁed, ∀ ∈ ρ(x,η0,T) > 1, x Bε(x0), where, Bε(x) represents an open ball of radius ε around x0, and Ws(xe) denotes the stable manifold of a type-1 saddle point xe, which is located at the boundary of the domain of attraction A(xs). Next, we outlline Theorem 17, which can specify the ﬁnite time stability region contained in the domain of attraction in terms of the normal expansion rates. Theorem 17. For any ﬁnite time interval T > 0 there exists an ε > 0 such that, follow- ing condition is satisﬁed, − ∀ ∈ ρ(x,η0, T) > 1, x Bε(xs), where, Bε(xs) represents an open ball of radius ε around the stable ﬁxed point xs. Theorem 16 provides a region for ﬁnite time stability based on the repulsion rate. Theorem 16 also can be rephrased as following - for an arbitrary ﬁnite time interval T > 0, there exists a ε > 0 such that, a material surface at a maximum distance of ε from the the stable manifold of any type - 1 saddle point , forms a ﬁnite time re- pelling hyperbolic surface. Hence, the normal repulsion rate provides a rigorous way to demarcate the ﬁnite time stability boundary. The classical methods were capable of demarcating the stability boundaries in terms of the asymptotic dynamics. But this may not be adequate for ﬁnite time stability analysis. For ﬁnite time stability monitoring, we compute normal repelling rate of the trajectory and ascertain the stability. Theorem 17 describes the material surfaces that form the ﬁnite time repelling material surfaces. for an arbitrary ﬁnite time interval T > 0, there exists a ε > 0 such that, a material surface inside the domain of attraction A(xs) of the stable ﬁxed point and at minimum distance of ε away from the all the stable manifolds of the type - 1 saddle point forms a ﬁnite time attracting hyperbolic surface. Also, the implication of Theo- rem 17 is that the normal repulsion rate can be used for a ﬁnite time stability certiﬁcate for online stability monitoring. For both Theorem 16, and 17, the parameter ε is a function of the time interval of interest, i.e. T. The normal expansion rate can be used to obtain the ﬁnite time stability boundaries, and also can be used for online stability monitoring. It is to be noted that, the ε in Theorem 16, decreases with increase in T, and ε in Theorem 17 increases with increase in T. The normal repulsion rate can be used as an estimate of the stability margin. Theorem 17 describes the material surfaces that are ﬁnite time repelling. Next, we would discuss the new insights that this approach brings to the existing method. 3.2 Margin of Stability from Normal Expansion Rate 9

text: used

label: paragraph

text: to

text: characterize

text: the

text: ﬁnite

text: time

text: stability

text: boundary,

text: and

text: Theorem

text: implicates

text: that

text: the

text: normal

text: expansion

text: rate

text: can

text: be

text: used

text: as

text: a

text: stability

text: certiﬁcate

text: for

text: online

text: monitoring.

text: Theorem

text: For

text: any

text: ﬁnite

text: time

text: interval

text: T

text: and

text: Ws(xe),

text: there

text: exists

text: an

text: ε

text: such

text: that,

text: following

text: condition

text: is

text: satisﬁed,

text: x

text: where,

text: Bε(x)

text: represents

text: an

text: open

text: ball

text: of

text: radius

text: ε

text: around

text: and

text: Ws(xe)

text: denotes

text: the

text: stable

text: manifold

text: of

text: a

text: saddle

text: point

text: xe,

text: which

text: is

text: located

text: at

text: the

text: boundary

text: of

text: the

text: domain

text: of

text: attraction

text: A(xs).

text: Next,

text: we

text: outlline

text: Theorem

text: which

text: can

text: specify

text: the

text: ﬁnite

text: time

text: stability

text: region

text: contained

text: in

text: the

text: domain

text: of

text: attraction

text: in

text: terms

text: of

text: the

text: normal

text: expansion

text: rates.

text: Theorem

text: For

text: any

text: ﬁnite

text: time

text: interval

text: T

text: there

text: exists

text: an

text: ε

text: such

text: that,

text: follow-

text: ing

text: condition

text: is

text: satisﬁed,

text: T)

text: x

text: Bε(xs),

text: where,

text: Bε(xs)

text: represents

text: an

text: open

text: ball

text: of

text: radius

text: ε

text: around

text: the

text: stable

text: ﬁxed

text: point

text: xs.

text: Theorem

text: provides

text: a

text: region

text: for

text: ﬁnite

text: time

text: stability

text: based

text: on

text: the

text: repulsion

text: rate.

text: Theorem

text: also

text: can

text: be

text: rephrased

text: as

text: following

text: for

text: an

text: arbitrary

text: ﬁnite

text: time

text: interval

text: T

text: there

text: exists

text: a

text: ε

text: such

text: that,

text: a

text: material

text: surface

text: at

text: a

text: maximum

text: distance

text: of

text: ε

text: from

text: the

text: the

text: stable

text: manifold

text: of

text: any

text: type

text: saddle

text: point

text: forms

text: a

text: ﬁnite

text: time

text: re-

text: pelling

text: hyperbolic

text: surface.

text: Hence,

text: the

text: normal

text: repulsion

text: rate

text: provides

text: a

text: rigorous

text: way

text: to

text: demarcate

text: the

text: ﬁnite

text: time

text: stability

text: boundary.

text: The

text: classical

text: methods

text: were

text: capable

text: of

text: demarcating

text: the

text: stability

text: boundaries

text: in

text: terms

text: of

text: the

text: asymptotic

text: dynamics.

text: But

text: this

text: may

text: not

text: be

text: adequate

text: for

text: ﬁnite

text: time

text: stability

text: analysis.

text: For

text: ﬁnite

text: time

text: stability

text: monitoring,

text: we

text: compute

text: normal

text: repelling

text: rate

text: of

text: the

text: trajectory

text: and

text: ascertain

text: the

text: stability.

text: Theorem

text: describes

text: the

text: material

text: surfaces

text: that

text: form

text: the

text: ﬁnite

text: time

text: repelling

text: material

text: surfaces.

text: for

text: an

text: arbitrary

text: ﬁnite

text: time

text: interval

text: T

text: there

text: exists

text: a

text: ε

text: such

text: that,

text: a

text: material

text: surface

text: inside

text: the

text: domain

text: of

text: attraction

text: A(xs)

text: of

text: the

text: stable

text: ﬁxed

text: point

text: and

text: at

text: minimum

text: distance

text: of

text: ε

text: away

text: from

text: the

text: all

text: the

text: stable

text: manifolds

text: of

text: the

text: type

text: saddle

text: point

text: forms

text: a

text: ﬁnite

text: time

text: attracting

text: hyperbolic

text: surface.

text: Also,

text: the

text: implication

text: of

text: Theo-

text: rem

text: is

text: that

text: the

text: normal

text: repulsion

text: rate

text: can

text: be

text: used

text: for

text: a

text: ﬁnite

text: time

text: stability

text: certiﬁcate

text: for

text: online

text: stability

text: monitoring.

text: For

text: both

text: Theorem

text: and

text: the

text: parameter

text: ε

text: is

text: a

text: function

text: of

text: the

text: time

text: interval

text: of

text: interest,

text: i.e.

text: T.

text: The

text: normal

text: expansion

text: rate

text: can

text: be

text: used

text: to

text: obtain

text: the

text: ﬁnite

text: time

text: stability

text: boundaries,

text: and

text: also

text: can

text: be

text: used

text: for

text: online

text: stability

text: monitoring.

text: It

text: is

text: to

text: be

text: noted

text: that,

text: the

text: ε

text: in

text: Theorem

text: decreases

text: with

text: increase

text: in

text: T,

text: and

text: ε

text: in

text: Theorem

text: increases

text: with

text: increase

text: in

text: T.

text: The

text: normal

text: repulsion

text: rate

text: can

text: be

text: used

text: as

text: an

text: estimate

text: of

text: the

text: stability

text: margin.

text: Theorem

text: describes

text: the

text: material

text: surfaces

text: that

text: are

text: ﬁnite

text: time

text: repelling.

text: Next,

text: we

text: would

text: discuss

text: the

text: new

text: insights

text: that

text: this

text: approach

text: brings

text: to

text: the

text: existing

text: method.

text: Margin

text: of

text: Stability

text: from

text: Normal

text: Expansion

text: Rate


text: (cid:20) (cid:21) (cid:20) (cid:21)(cid:20) (cid:21) equation using Kron reduction. A(cid:0)fter doing Kron redu(cid:1)ction, as described in [5], − δ˙T(t) − 0 I δT(t) ω˙ T(t) = M−1 Lgg −LglLl−l 1Llg M−1Dg ωT(t) The reduced state equation describes the linearized rotor angle and frequency evolution at generator buses. The reduced system has 10 generators as nodes and each of the generators has 2 states, namely rotor angle and frequency. It can be noted that the inversion of L matrix, which was sparse in nature, results in a fully connected reduced ll system. The states of the reduced system is denoted as x = [δTωT]T, and the state equation is of the form x˙(t) = Ax(t). Now we discretize the state equation as x(t +1) = (I + A∆t)x(t), where ∆t is the sampling period. We use this discretized model for purpose of computation. For simulation purposes, we consider New England 39 bus system, which is a reduced model for New England and Canada. The A matrix is computed using the MatPower package (which is supported on Matlab) [9]. It is veriﬁed that the eigen values of the A matrix lies inside the unit circle and the link outage results in output directions, which − − − are observable. We consider two set of possible contingencies (37 25,36 23,33 − 19,39 9) (The corresponding lines have been marked in green in Fig. 3). For this set of contingencies, the sensitivity values both F ’s and S ’s are plotted in Fig. 4 ij ij (a). It can be observed the vector E and S manifest similar pattern. This signiﬁes the uncertainties are not interacting much. The relative order of the links in terms of the sensitivity is preserved. This is also reﬂected in the value of interaction factor I, − − − which is 0.003. Next, we consider another set of contingencies (38 29,34 20,35 0.8 0.7 0.7 0.6 0.6 0.5 0.5 0.4 0.4 0.3 0.3 0.2 0.2 0.1 0.1 0 37−25 36−23 Link 33−19 39−9 0 38−29 34−20 Link 35−22 39−1 0.8 0.8 0.7 0.7 0.6 0.6 0.5 0.5 0.4 0.4 0.3 0.3 0.2 0.2 0.1 0.1 0 37−25 36−23 Link 33−19 39−9 0 38−29 34−20 Link 35−22 39−1 (a) (b) Figure 4: Normalized sensitivity values for ﬁrst set of contingencies - (a) marked in green in Fig. 3, (b) marked in red in Fig. 3. − 22,39 1) (The corresponding lines have been marked in red in Fig. 3). For this set of contingencies, the two set of contingencies normalized F ’s and S ’s can be seen in ij ij Fig. 4 (b). It can be observed the vectors E and S show different trends, as the relative criticality changes in the two cases. This signiﬁes the uncertainties are interacting and 9 F dezilamroN S dezilamroN ji ji F dezilamroN S dezilamroN ji ji ##LTFigure## ##LTFigure## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: equation

text: using

text: Kron

text: reduction.

text: doing

text: Kron

text: as

text: described

text: in

text: δ˙T(t)

text: I

text: δT(t)

text: ω˙

text: T(t)

text: Lgg

text: −LglLl−l

text: ωT(t)

text: The

text: reduced

text: state

text: equation

text: describes

text: the

text: linearized

text: rotor

text: angle

text: and

text: frequency

text: evolution

text: at

text: generator

text: buses.

text: The

text: reduced

text: system

text: has

text: generators

text: as

text: nodes

text: and

text: each

text: of

text: the

text: generators

text: has

text: states,

text: namely

text: rotor

text: angle

text: and

text: frequency.

text: It

text: can

text: be

text: noted

text: that

text: the

text: inversion

text: of

text: L

text: matrix,

text: which

text: was

text: sparse

text: in

text: nature,

text: results

text: in

text: a

text: fully

text: connected

text: reduced

text: ll

text: system.

text: The

text: states

text: of

text: the

text: reduced

text: system

text: is

text: denoted

text: as

text: x

text: [δTωT]T,

text: and

text: the

text: state

text: equation

text: is

text: of

text: the

text: form

text: x˙(t)

text: Ax(t).

text: Now

text: we

text: discretize

text: the

text: state

text: equation

text: as

text: x(t

text: (I

text: A∆t)x(t),

text: where

text: ∆t

text: is

text: the

text: sampling

text: period.

text: We

text: use

text: this

text: discretized

text: model

text: for

text: purpose

text: of

text: computation.

text: For

text: simulation

text: purposes,

text: we

text: consider

text: New

text: England

text: bus

text: system,

text: which

text: is

text: a

text: reduced

text: model

text: for

text: New

text: England

text: and

text: Canada.

text: The

text: A

text: matrix

text: is

text: computed

text: using

text: the

text: MatPower

text: package

text: (which

text: is

text: supported

text: on

text: Matlab)

text: It

text: is

text: veriﬁed

text: that

text: the

text: eigen

text: values

text: of

text: the

text: A

text: matrix

text: lies

text: inside

text: the

text: unit

text: circle

text: and

text: the

text: link

text: outage

text: results

text: in

text: output

text: directions,

text: which

text: are

text: observable.

text: We

text: consider

text: two

text: set

text: of

text: possible

text: contingencies

text: (The

text: corresponding

text: lines

text: have

text: been

text: marked

text: in

text: green

text: in

text: Fig.

text: For

text: this

text: set

text: of

text: contingencies,

text: the

text: sensitivity

text: values

text: both

text: F

text: ’s

text: and

text: S

text: ’s

text: are

text: plotted

text: in

text: Fig.

text: ij

text: ij

text: (a).

text: It

text: can

text: be

text: observed

text: the

text: vector

text: E

text: and

text: S

text: manifest

text: similar

text: pattern.

text: This

text: signiﬁes

text: the

text: uncertainties

text: are

text: not

text: interacting

text: much.

text: The

text: relative

text: order

text: of

text: the

text: links

text: in

text: terms

text: of

text: the

text: sensitivity

text: is

text: preserved.

text: This

text: is

text: also

text: reﬂected

text: in

text: the

text: value

text: of

text: interaction

text: factor

text: I,

text: which

text: is

text: Next,

text: we

text: consider

text: another

text: set

text: of

text: contingencies

text: Link

text: Link

text: Link

text: Link

text: (a)

text: (b)

text: Figure

text: Normalized

text: sensitivity

text: values

text: for

text: ﬁrst

text: set

text: of

text: contingencies

text: (a)

text: marked

text: in

text: green

text: in

text: Fig.

text: (b)

text: marked

text: in

text: red

text: in

text: Fig.

text: (The

text: corresponding

text: lines

text: have

text: been

text: marked

text: in

text: red

text: in

text: Fig.

text: For

text: this

text: set

text: of

text: contingencies,

text: the

text: two

text: set

text: of

text: contingencies

text: normalized

text: F

text: ’s

text: and

text: S

text: ’s

text: can

text: be

text: seen

text: in

text: ij

text: ij

text: Fig.

text: (b).

text: It

text: can

text: be

text: observed

text: the

text: vectors

text: E

text: and

text: S

text: show

text: different

text: trends,

text: as

text: the

text: relative

text: criticality

text: changes

text: in

text: the

text: two

text: cases.

text: This

text: signiﬁes

text: the

text: uncertainties

text: are

text: interacting

text: and

text: F

text: dezilamroN

text: S

text: dezilamroN

text: ji

text: ji

text: F

text: dezilamroN

text: S

text: dezilamroN

text: ji

text: ji

text: ##LTFigure##

text: ##LTFigure##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: [17] K. G. Murty and S. N. Kabadi. Some NP-complete problems in quadratic and nonlinear programming. Mathematical Programming, 39:117–129, 1987. [18] A. Papachristodoulou and S. Prajna. On the construction of Lyapunov functions using the sum of squares decomposition. In IEEE Conference on Decision and Control, 2002. [19] P. A. Parrilo. Structured semideﬁnite programs and semialgebraic geometry methods in robust- ness and optimization. PhD thesis, California Institute of Technology, May 2000. [20] P. A. Parrilo. Semideﬁnite programming relaxations for semialgebraic problems. Mathematical Programming, 96(2, Ser. B):293–320, 2003. [21] M. M. Peet. Exponentially stable nonlinear systems have polynomial Lyapunov functions on bounded regions. IEEE Trans. Automat. Control, 54(5):979–987, 2009. [22] M. M. Peet and A. Papachristodoulou. A converse sum of squares Lyapunov result: an ex- istence proof based on the Picard iteration. In Proceedings of the 49th IEEE Conference on Decision and Control, 2010. [23] M. M. Peet and A. Papachristodoulou. A converse sum of squares Lyapunov result with a degree bound. IEEE Trans. Automat. Control, 57(9), 2012. [24] S. Prajna and A. Papachristodoulou. Analysis of switched and hybrid systems – beyond piecewise quadratic methods. In Proceedings of the American Control Conference, 2003. [25] B. Reznick. Some concrete aspects of Hilbert’s 17th problem. In Contemporary Mathematics, volume 253, pages 251–272. American Mathematical Society, 2000. [26] R. M. Robinson. Some deﬁnite polynomials which are not sums of squares of real polynomials. (cid:48) In Selected questions of algebra and logic (collection dedicated to the memory of A. I. Mal cev) (Russian), pages 264–282. Izdat. “Nauka” Sibirsk. Otdel., Novosibirsk, 1973. [27] L. Rosier. Homogeneous Lyapunov function for homogeneous continuous vector ﬁelds. Systems Control Lett., 19(6):467–473, 1992. [28] N. Samardzija. Stability properties of autonomous homogeneous polynomial diﬀerential sys- tems. Journal of Diﬀerential Equations, 48(1):60–70, 1983. [29] C. Scheiderer. Sums of squares on real algebraic surfaces. Manuscripta Mathematica, 119(4):395–410, 2006. [30] C. Scheiderer. A Positivstellensatz for projective real varieties. Manuscripta Mathematica, 138(1-2):73–88, 2012. 12

label: reference

text: K.

text: G.

text: Murty

text: and

text: S.

text: N.

text: Kabadi.

text: Some

text: NP-complete

text: problems

text: in

text: quadratic

text: and

text: nonlinear

text: programming.

text: Mathematical

text: Programming,

text: A.

text: Papachristodoulou

text: and

text: S.

text: Prajna.

text: On

text: the

text: construction

text: of

text: Lyapunov

text: functions

text: using

text: the

text: sum

text: of

text: squares

text: decomposition.

text: In

text: IEEE

text: Conference

text: on

text: Decision

text: and

text: Control,

text: P.

text: A.

text: Parrilo.

text: Structured

text: semideﬁnite

text: programs

text: and

text: semialgebraic

text: geometry

text: methods

text: in

text: robust-

text: ness

text: and

text: optimization.

text: PhD

text: thesis,

text: California

text: Institute

text: of

text: Technology,

text: May

text: P.

text: A.

text: Parrilo.

text: Semideﬁnite

text: programming

text: relaxations

text: for

text: semialgebraic

text: problems.

text: Mathematical

text: Programming,

text: Ser.

text: M.

text: M.

text: Peet.

text: Exponentially

text: stable

text: nonlinear

text: systems

text: have

text: polynomial

text: Lyapunov

text: functions

text: on

text: bounded

text: regions.

text: IEEE

text: Trans.

text: Automat.

text: Control,

text: M.

text: M.

text: Peet

text: and

text: A.

text: Papachristodoulou.

text: A

text: converse

text: sum

text: of

text: squares

text: Lyapunov

text: result:

text: an

text: ex-

text: istence

text: proof

text: based

text: on

text: the

text: Picard

text: iteration.

text: In

text: Proceedings

text: of

text: the

text: IEEE

text: Conference

text: on

text: Decision

text: and

text: Control,

text: M.

text: M.

text: Peet

text: and

text: A.

text: Papachristodoulou.

text: A

text: converse

text: sum

text: of

text: squares

text: Lyapunov

text: result

text: with

text: a

text: degree

text: bound.

text: IEEE

text: Trans.

text: Automat.

text: Control,

text: S.

text: Prajna

text: and

text: A.

text: Papachristodoulou.

text: Analysis

text: of

text: switched

text: and

text: hybrid

text: systems

text: beyond

text: piecewise

text: quadratic

text: methods.

text: In

text: Proceedings

text: of

text: the

text: American

text: Control

text: Conference,

text: B.

text: Reznick.

text: Some

text: concrete

text: aspects

text: of

text: Hilbert’s

text: problem.

text: In

text: Contemporary

text: Mathematics,

text: volume

text: pages

text: American

text: Mathematical

text: Society,

text: R.

text: M.

text: Robinson.

text: Some

text: deﬁnite

text: polynomials

text: which

text: are

text: not

text: sums

text: of

text: squares

text: of

text: real

text: polynomials.

text: In

text: Selected

text: questions

text: of

text: algebra

text: and

text: logic

text: (collection

text: dedicated

text: to

text: the

text: memory

text: of

text: A.

text: I.

text: Mal

text: cev)

text: (Russian),

text: pages

text: Izdat.

text: “Nauka”

text: Sibirsk.

text: Otdel.,

text: Novosibirsk,

text: L.

text: Rosier.

text: Homogeneous

text: Lyapunov

text: function

text: for

text: homogeneous

text: continuous

text: vector

text: ﬁelds.

text: Systems

text: Control

text: Lett.,

text: N.

text: Samardzija.

text: Stability

text: properties

text: of

text: autonomous

text: homogeneous

text: polynomial

text: diﬀerential

text: sys-

text: tems.

text: Journal

text: of

text: Diﬀerential

text: Equations,

text: C.

text: Scheiderer.

text: Sums

text: of

text: squares

text: on

text: real

text: algebraic

text: surfaces.

text: Manuscripta

text: Mathematica,

text: C.

text: Scheiderer.

text: A

text: Positivstellensatz

text: for

text: projective

text: real

text: varieties.

text: Manuscripta

text: Mathematica,


text: (even if V is nonnegative). Let d be the degree of V and consider the standard homogenization V h of V in n+1 variables given by V (x , . . . , x , y) = ydV (x). Since V is sos, V must be sos [25]. But h 1 1 y h this implies that t.h.c.(V ) must be sos since it is a restriction of V : t.h.c.(V ) = V (x , . . . , x , 0). h h 1 n A counterexample to the converse is the Motzkin polynomial − x4x2 + x2x4 3x2x2 + 1, 1 2 1 2 1 2 whose top homogeneous component x4x2 + x2x4 is sos, but the polynomial itself is not sos even 1 2 1 2 though it is nonnegative [25]. In the particular case of the plane (n = 2), the constraint “t.h.c.(V ) sos” in fact introduces no conservatism at all. This is because all nonnegative bivariate homogeneous polynomials (of any degree) are sums of squares [25]. By contrast, the alternative condition “V sos” can be conservative as there are (non-homogeneous) nonnegative bivariate polynomials that are not sums of squares. In addition to these features in terms of conservatism, the requirement “t.h.c.(V ) sos” is a cheaper constraint to impose than “V sos”. Indeed, if V is an n-variate polynomial of degree 2d, simple − 2d(n+2d 1)! calculation shows that the SDP underlying the former condition has fewer equality − − 2d!n! d(n+d 1)!((2n+d)(n+d 1)!+d!n!) constraints and fewer decision variables than the latter. Let us end 2(d!n!)2 with a concrete example. Example 4.1. Consider the vector ﬁeld − − x˙ = 0.36x + 2x 0.32x7 0.02x x6 + 8x7 + 3x2x5 1 − 1− 2 − 1 − −1 2 2− 1 2 x˙ = 2x 0.44x 16x7 x x6 0.16x7 0.06x2x5. 2 1 2 1 1 2 2 1 2 We solve an SDP which searches for a polynomial Lyapunov function V of degree d that satisﬁes − “t.h.c.(V ) sos and V˙ sos”. This SDP is infeasible for d = 2, 4, 6. Because of Lemma 4.2, we know − that the SDP with the more standard conditions “V sos and V˙ sos” would have been infeasible also. Moreover, since nonnegative bivariate forms are sos, we know that our constraint “t.h.c.(V ) sos” is lossless (while we wouldn’t be able to make such a claim for the constraint “V sos”). For d = 8, our SDP returns the following solution: V (x) = 2.195x2 + 4.237x8 + 2.183x2 + 2.170x8 1 1− 2 2 +1.055x2x6 + 0.863x x 0.286x7x + 0.037x6x2 1 2 − 1 2 − 1 2 1 2 +0.042x5x3 0.011x4x4 0.021x3x5 + 0.039x x7. 1 2 1 2 1 2 1 2 By checking the eigenvalues of the Gram matrices in our SDP, we can see that the top homo- − geneous component of this polynomial, as well as V˙ , are positive deﬁnite. Hence, by Lemma 4.2, we know that the system is GAS. For this example it happens that the returned solution V is sos although we asked for a weaker and cheaper condition. Indeed, the semideﬁnite constraint that we imposed to require t.h.c.(V ) to be sos has 105 fewer decision variables and 36 fewer equality constraints than the semideﬁnite constraint needed to impose V sos. In general, by leaving out the constant term in the parametrization of the polynomial V , we can make sure that V (0) = 0 and hence (in view of the proof of Proposition 4.1) radial unboundedness would automatically imply positive deﬁniteness of our Lyapunov function. Acknowledgments. The authors are grateful to Claus Scheiderer for insightful discussions. 10 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: (even

text: if

text: V

text: is

text: nonnegative).

text: Let

text: d

text: be

text: the

text: degree

text: of

text: V

text: and

text: consider

text: the

text: standard

text: homogenization

text: V

text: h

text: of

text: V

text: in

text: variables

text: given

text: by

text: V

text: (x

text: x

text: y)

text: ydV

text: (x).

text: Since

text: V

text: is

text: sos,

text: V

text: must

text: be

text: sos

text: But

text: h

text: y

text: h

text: this

text: implies

text: that

text: t.h.c.(V

text: must

text: be

text: sos

text: since

text: it

text: is

text: a

text: restriction

text: of

text: V

text: t.h.c.(V

text: V

text: (x

text: x

text: h

text: h

text: n

text: A

text: counterexample

text: to

text: the

text: converse

text: is

text: the

text: Motzkin

text: polynomial

text: whose

text: top

text: homogeneous

text: component

text: is

text: sos,

text: but

text: the

text: polynomial

text: itself

text: is

text: not

text: sos

text: even

text: though

text: it

text: is

text: nonnegative

text: In

text: the

text: particular

text: case

text: of

text: the

text: plane

text: (n

text: the

text: constraint

text: “t.h.c.(V

text: sos”

text: in

text: fact

text: introduces

text: no

text: conservatism

text: at

text: all.

text: This

text: is

text: because

text: all

text: nonnegative

text: bivariate

text: homogeneous

text: polynomials

text: (of

text: any

text: degree)

text: are

text: sums

text: of

text: squares

text: By

text: contrast,

text: the

text: alternative

text: condition

text: “V

text: sos”

text: can

text: be

text: conservative

text: as

text: there

text: are

text: (non-homogeneous)

text: nonnegative

text: bivariate

text: polynomials

text: that

text: are

text: not

text: sums

text: of

text: squares.

text: In

text: addition

text: to

text: these

text: features

text: in

text: terms

text: of

text: conservatism,

text: the

text: requirement

text: “t.h.c.(V

text: sos”

text: is

text: a

text: cheaper

text: constraint

text: to

text: impose

text: than

text: “V

text: sos”.

text: Indeed,

text: if

text: V

text: is

text: an

text: n-variate

text: polynomial

text: of

text: degree

text: simple

text: calculation

text: shows

text: that

text: the

text: SDP

text: underlying

text: the

text: former

text: condition

text: has

text: fewer

text: equality

text: d(n+d

text: constraints

text: and

text: fewer

text: decision

text: variables

text: than

text: the

text: latter.

text: Let

text: us

text: end

text: with

text: a

text: concrete

text: example.

text: Example

text: Consider

text: the

text: vector

text: ﬁeld

text: x˙

text: 1−

text: −1

text: 2−

text: x˙

text: x

text: We

text: solve

text: an

text: SDP

text: which

text: searches

text: for

text: a

text: polynomial

text: Lyapunov

text: function

text: V

text: of

text: degree

text: d

text: that

text: satisﬁes

text: “t.h.c.(V

text: sos

text: and

text: V˙

text: sos”.

text: This

text: SDP

text: is

text: infeasible

text: for

text: d

text: Because

text: of

text: Lemma

text: we

text: know

text: that

text: the

text: SDP

text: with

text: the

text: more

text: standard

text: conditions

text: “V

text: sos

text: and

text: V˙

text: sos”

text: would

text: have

text: been

text: infeasible

text: also.

text: Moreover,

text: since

text: nonnegative

text: bivariate

text: forms

text: are

text: sos,

text: we

text: know

text: that

text: our

text: constraint

text: “t.h.c.(V

text: sos”

text: is

text: lossless

text: (while

text: we

text: wouldn’t

text: be

text: able

text: to

text: make

text: such

text: a

text: claim

text: for

text: the

text: constraint

text: “V

text: sos”).

text: For

text: d

text: our

text: SDP

text: returns

text: the

text: following

text: solution:

text: V

text: (x)

text: 1−

text: x

text: By

text: checking

text: the

text: eigenvalues

text: of

text: the

text: Gram

text: matrices

text: in

text: our

text: SDP,

text: we

text: can

text: see

text: that

text: the

text: top

text: homo-

text: geneous

text: component

text: of

text: this

text: polynomial,

text: as

text: well

text: as

text: V˙

text: are

text: positive

text: deﬁnite.

text: Hence,

text: by

text: Lemma

text: we

text: know

text: that

text: the

text: system

text: is

text: GAS.

text: For

text: this

text: example

text: it

text: happens

text: that

text: the

text: returned

text: solution

text: V

text: is

text: sos

text: although

text: we

text: asked

text: for

text: a

text: weaker

text: and

text: cheaper

text: condition.

text: Indeed,

text: the

text: semideﬁnite

text: constraint

text: that

text: we

text: imposed

text: to

text: require

text: t.h.c.(V

text: to

text: be

text: sos

text: has

text: fewer

text: decision

text: variables

text: and

text: fewer

text: equality

text: constraints

text: than

text: the

text: semideﬁnite

text: constraint

text: needed

text: to

text: impose

text: V

text: sos.

text: In

text: general,

text: by

text: leaving

text: out

text: the

text: constant

text: term

text: in

text: the

text: parametrization

text: of

text: the

text: polynomial

text: V

text: we

text: can

text: make

text: sure

text: that

text: V

text: and

text: hence

text: (in

text: view

text: of

text: the

text: proof

text: of

text: Proposition

text: radial

text: unboundedness

text: would

text: automatically

text: imply

text: positive

text: deﬁniteness

text: of

text: our

text: Lyapunov

text: function.

text: Acknowledgments.

text: The

text: authors

text: are

text: grateful

text: to

text: Claus

text: Scheiderer

text: for

text: insightful

text: discussions.

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: − ≈ is stable for the arrival rate λ < e 1 0.368. Another paradigm of full-sensing algorithms was proposed independently by Capetanakis [17], Hayes [59] and Tsybakov and Mikhailov [113]. The algorithms they developed are usually called tree algorithms. They operate as follows. Let A be a positive integer interpreted as the arity of a tree. The algorithm run by a station is either in a waiting phase or a conﬂict resolution phase, switching between them accordingly. A conﬂict resolution phase starts after a conﬂict occurs. A waiting phase starts after all the packets of the stations involved in a conﬂict resolution have been transmitted successfully. If a new packet is generated then it is assigned to a station, which broadcasts it immediately if being in a waiting phase, otherwise it waits for the beginning of a waiting phase. Conﬂict resolution is performed as follows. First each among the involved stations selects randomly and independently an integer in the segment [1..A], we say that they branch out. Then A stages follow, the stations that selected number i participate in the i-th stage. They begin with broadcasting their packets. If a conﬂict occurs then it is resolved recursively, which may be interpreted as going down one level in a tree. A stage terminates when all the participating stations have succeeded. Parameter A is often taken equal to 2. If the channel is quiet during − all the branchings 1 through A 1, then stage A need not be performed, it will certainly result in a collision, hence the stations might branch out immediately. Tree algorithms are stable for suﬃciently small arrival rates, namely their variants were shown to be stable for λ < 3/8 in [113] and for λ < 0.430 in [17]. Notice that tree algorithms are not FCFS. A modiﬁcation of the tree-algorithm paradigm, called splitting algorithm, was proposed inde- pendently by Gallager and by Tsybakov and Mikhailov (see [44]). This algorithm is FCFS. The idea is to abandon the underlying tree structure and refer to the stations directly by their activation times. The stations join the conﬂict resolution in the order of activation. This may be interpreted as if they were stored in a stack. Suppose that at step k the protocol has just successfully transmit- ted all the messages that arrived before some time T (k). All the messages that arrived in the time period [T (k), T (k) + a(k)] are broadcast in slot k. If there is a collision then this time interval is partitioned into subintervals, namely into the left interval [T (k), T (k) + b(k)] and the right interval [T (k) + b(k), T (k) + a(k)], where 0 < b(k) < a(k). The stations from the left interval broadcast ﬁrst. If a collision happens again then the left interval is subdivided into two subintervals. It is now when the departure from the tree-algorithm paradigm happens. Namely, only these two subintervals obtained from the left interval are remembered, the stations from the right interval are put back on the stack, and are not distinguished from the other stations still there. Otherwise, if there is no collision in the left interval, then the right interval is considered in a similar fashion. − The function a(k) is of the form min[c, k T (k)], where the constant c is taken to be c = 2.6 to maximize the stable transmission rate. The simplest function b(k) to be considered is the one that halves the interval [T (k), T (k)+a(k)], this determines the binary version of the splitting algorithm. Binary splitting algorithm was shown to be strongly stable for λ < 0.4871. This binary algorithm was later streamlined by Mosely and Humblet, and Tsybakov and Mikhailov, who showed that by partitioning the interval in an optimal way increases the tenac- ity to 0.4878 (see [83, 114, 115]). Vvedenskaya and Pinsker [116] developed a protocol with tenacity × − still better by 3.6 10 7. More on the analysis of parameters of the tree and splitting algorithms can be found in [37, 54, 76]. In particular, they are strongly stable for suﬃciently small arrival rates. One might wonder if the best full-sensing protocols are FCFS. This hypothesis was shown to 17

text: is

text: stable

text: for

text: the

text: arrival

text: rate

text: λ

text: e

text: Another

text: paradigm

text: of

text: full-sensing

text: algorithms

text: was

text: proposed

text: independently

text: by

text: Capetanakis

text: Hayes

text: and

text: Tsybakov

text: and

text: Mikhailov

text: The

text: algorithms

text: they

text: developed

text: are

text: usually

text: called

text: tree

text: algorithms.

text: They

text: operate

text: as

text: follows.

text: Let

text: A

text: be

text: a

text: positive

text: integer

text: interpreted

text: as

text: the

text: arity

text: of

text: a

text: tree.

text: The

text: algorithm

text: run

text: by

text: a

text: station

text: is

text: either

text: in

text: a

text: waiting

text: phase

text: or

text: a

text: conﬂict

text: resolution

text: phase,

text: switching

text: between

text: them

text: accordingly.

text: A

text: conﬂict

text: resolution

text: phase

text: starts

text: after

text: a

text: conﬂict

text: occurs.

text: A

text: waiting

text: phase

text: starts

text: after

text: all

text: the

text: packets

text: of

text: the

text: stations

text: involved

text: in

text: a

text: conﬂict

text: resolution

text: have

text: been

text: transmitted

text: successfully.

text: If

text: a

text: new

text: packet

text: is

text: generated

text: then

text: it

text: is

text: assigned

text: to

text: a

text: station,

text: which

text: broadcasts

text: it

text: immediately

text: if

text: being

text: in

text: a

text: waiting

text: phase,

text: otherwise

text: it

text: waits

text: for

text: the

text: beginning

text: of

text: a

text: waiting

text: phase.

text: Conﬂict

text: resolution

text: is

text: performed

text: as

text: follows.

text: First

text: each

text: among

text: the

text: involved

text: stations

text: selects

text: randomly

text: and

text: independently

text: an

text: integer

text: in

text: the

text: segment

text: we

text: say

text: that

text: they

text: branch

text: out.

text: Then

text: A

text: stages

text: follow,

text: the

text: stations

text: that

text: selected

text: number

text: i

text: participate

text: in

text: the

text: i-th

text: stage.

text: They

text: begin

text: with

text: broadcasting

text: their

text: packets.

text: If

text: a

text: conﬂict

text: occurs

text: then

text: it

text: is

text: resolved

text: recursively,

text: which

text: may

text: be

text: interpreted

text: as

text: going

text: down

text: one

text: level

text: in

text: a

text: tree.

text: A

text: stage

text: terminates

text: when

text: all

text: the

text: participating

text: stations

text: have

text: succeeded.

text: Parameter

text: A

text: is

text: often

text: taken

text: equal

text: to

text: If

text: the

text: channel

text: is

text: quiet

text: during

text: all

text: the

text: branchings

text: through

text: A

text: then

text: stage

text: A

text: need

text: not

text: be

text: performed,

text: it

text: will

text: certainly

text: result

text: in

text: a

text: collision,

text: hence

text: the

text: stations

text: might

text: branch

text: out

text: immediately.

text: Tree

text: algorithms

text: are

text: stable

text: for

text: suﬃciently

text: small

text: arrival

text: rates,

text: namely

text: their

text: variants

text: were

text: shown

text: to

text: be

text: stable

text: for

text: λ

text: in

text: and

text: for

text: λ

text: in

text: Notice

text: that

text: tree

text: algorithms

text: are

text: not

text: FCFS.

text: A

text: modiﬁcation

text: of

text: the

text: tree-algorithm

text: paradigm,

text: called

text: splitting

text: algorithm,

text: was

text: proposed

text: inde-

text: pendently

text: by

text: Gallager

text: and

text: by

text: Tsybakov

text: and

text: Mikhailov

text: (see

text: This

text: algorithm

text: is

text: FCFS.

text: The

text: idea

text: is

text: to

text: abandon

text: the

text: underlying

text: tree

text: structure

text: and

text: refer

text: to

text: the

text: stations

text: directly

text: by

text: their

text: activation

text: times.

text: The

text: stations

text: join

text: the

text: conﬂict

text: resolution

text: in

text: the

text: order

text: of

text: activation.

text: This

text: may

text: be

text: interpreted

text: as

text: if

text: they

text: were

text: stored

text: in

text: a

text: stack.

text: Suppose

text: that

text: at

text: step

text: k

text: the

text: protocol

text: has

text: just

text: successfully

text: transmit-

text: ted

text: all

text: the

text: messages

text: that

text: arrived

text: before

text: some

text: time

text: T

text: (k).

text: All

text: the

text: messages

text: that

text: arrived

text: in

text: the

text: time

text: period

text: [T

text: (k),

text: T

text: (k)

text: a(k)]

text: are

text: broadcast

text: in

text: slot

text: k.

text: If

text: there

text: is

text: a

text: collision

text: then

text: this

text: time

text: interval

text: is

text: partitioned

text: into

text: subintervals,

text: namely

text: into

text: the

text: left

text: interval

text: [T

text: (k),

text: T

text: (k)

text: b(k)]

text: and

text: the

text: right

text: interval

text: [T

text: (k)

text: b(k),

text: T

text: (k)

text: a(k)],

text: where

text: b(k)

text: a(k).

text: The

text: stations

text: from

text: the

text: left

text: interval

text: broadcast

text: ﬁrst.

text: If

text: a

text: collision

text: happens

text: again

text: then

text: the

text: left

text: interval

text: is

text: subdivided

text: into

text: two

text: subintervals.

text: It

text: is

text: now

text: when

text: the

text: departure

text: from

text: the

text: tree-algorithm

text: paradigm

text: happens.

text: Namely,

text: only

text: these

text: two

text: subintervals

text: obtained

text: from

text: the

text: left

text: interval

text: are

text: remembered,

text: the

text: stations

text: from

text: the

text: right

text: interval

text: are

text: put

text: back

text: on

text: the

text: stack,

text: and

text: are

text: not

text: distinguished

text: from

text: the

text: other

text: stations

text: still

text: there.

text: Otherwise,

text: if

text: there

text: is

text: no

text: collision

text: in

text: the

text: left

text: interval,

text: then

text: the

text: right

text: interval

text: is

text: considered

text: in

text: a

text: similar

text: fashion.

text: The

text: function

text: a(k)

text: is

text: of

text: the

text: form

text: min[c,

text: k

text: T

text: (k)],

text: where

text: the

text: constant

text: c

text: is

text: taken

text: to

text: be

text: c

text: to

text: maximize

text: the

text: stable

text: transmission

text: rate.

text: The

text: simplest

text: function

text: b(k)

text: to

text: be

text: considered

text: is

text: the

text: one

text: that

text: halves

text: the

text: interval

text: [T

text: (k),

text: T

text: (k)+a(k)],

text: this

text: determines

text: the

text: binary

text: version

text: of

text: the

text: splitting

text: algorithm.

text: Binary

text: splitting

text: algorithm

text: was

text: shown

text: to

text: be

text: strongly

text: stable

text: for

text: λ

text: This

text: binary

text: algorithm

text: was

text: later

text: streamlined

text: by

text: Mosely

text: and

text: Humblet,

text: and

text: Tsybakov

text: and

text: Mikhailov,

text: who

text: showed

text: that

text: by

text: partitioning

text: the

text: interval

text: in

text: an

text: optimal

text: way

text: increases

text: the

text: tenac-

text: ity

text: to

text: (see

text: Vvedenskaya

text: and

text: Pinsker

text: developed

text: a

text: protocol

text: with

text: tenacity

text: still

text: better

text: by

text: More

text: on

text: the

text: analysis

text: of

text: parameters

text: of

text: the

text: tree

text: and

text: splitting

text: algorithms

text: can

text: be

text: found

text: in

text: In

text: particular,

text: they

text: are

text: strongly

text: stable

text: for

text: suﬃciently

text: small

text: arrival

text: rates.

text: One

text: might

text: wonder

text: if

text: the

text: best

text: full-sensing

text: protocols

text: are

text: FCFS.

text: This

text: hypothesis

text: was

text: shown

text: to


text: be doubtful by Vvedenskaya and Pinsker [116] whose protocol is not FCFS. The issue of optimality among subclasses of full-sensing algorithms was also studied by Molle [81] and then by Panwar, Towsley and Wolf [88]. In particular, they considered nested FCFS algorithms which enable stations in the following conservative way: 1. If no set of stations is known in a step to contain more than one message and the set of stations C enabled in the next step contains station s then set C contains also all the stations preceding s whose status, with respect to holding a message, has not been clariﬁed yet (this is the FCFS property). 2. If a set B of stations is known in a step to contain more than one message then in the next step a subset of B is enabled (this is the property of being nested). A method to construct an optimal nested FCFS algorithm for a given probability to hold a message (Bernoulli arrivals for static model) has been developed in [88]. It is based on the Markovian decision theory, in particular on the value iteration algorithm (see [60]) and the Odoni bound (see [85]). Panwar, Towsley and Wolf [88] developed a scheme of mixing algorithms, which are not FCFS, and showed that they have higher transmission rates than optimal nested FCFS ones, for certain small probabilities to hold messages. To obtain such an algorithm, run an optimal nested FCFS algorithm augmented with the following trick. Suppose that we have identiﬁed a set { } s , s , s of three stations, of which we know only that at least two of them hold packets. Then 1 2 3 { } { } { } instead of enabling either s or s , s , as a FCFS algorithm would do, enable s , s , where 1 1 2 1 4 station s is the next station after s , and which may or may not hold a message. This approach 4 3 works because, for suﬃciently small probability to hold a message, station s will likely turn out 4 not to hold a message, so with a single try we will eliminate two stations. 4.2.3 Acknowledgement-based protocols Now we consider protocols which rely on the weakest feedback, that of a network without collision detection. They can be run on any single-hop network, they simply ignore the information from the channel, if any, obtained while staying idle. Such protocols usually erase their history after a successful broadcast, so they are acknowledgement-based. Because of that, we will not distinguish between possibly more general arbitrary protocols for the channel without collision detection and acknowledgement-based protocols. The oldest protocols, namely Aloha and the binary exponential backoﬀ, are in this class. The inﬁnitely-many users model was initially considered with a hope to show in a clean setting that these two protocols were stable, at least for suﬃciently small arrival rates. First, it was realized that the expected packet delay in Aloha is inﬁnite (see [2, 66]). Then it was shown that Aloha is unstable for any arrival rate (see [38]). This follows directly from the Kaplan’s criterion (see Section ). Namely, ﬁrst notice that the downward transitions are uniformly bounded. Secondly, let 0 < f < 1 be the probability(cid:0) that a station (cid:1)with(cid:0) a backlogged packet(cid:1)performs a broadcast in a step, and let i be the number of such stations. Then the drift is at least · − − − − − − · · · − − 2 1 e λ λe λ e λ i f (1 f)i 1 . So it is positive and bounded away from zero by a constant for suﬃciently large i. Rosenkrantz and Towsley [97] proved that Aloha is transient, by their criterion based on the martingale convergence theorem (see Section ). This result was later strengthened by Kelly [63] 18

text: be

text: doubtful

text: by

text: Vvedenskaya

text: and

text: Pinsker

text: whose

text: protocol

text: is

text: not

text: FCFS.

text: The

text: issue

text: of

text: optimality

text: among

text: subclasses

text: of

text: full-sensing

text: algorithms

text: was

text: also

text: studied

text: by

text: Molle

text: and

text: then

text: by

text: Panwar,

text: Towsley

text: and

text: Wolf

text: In

text: particular,

text: they

text: considered

text: nested

text: FCFS

text: algorithms

text: which

text: enable

text: stations

text: in

text: the

text: following

text: conservative

text: way:

label: list

text: If

text: no

text: set

text: of

text: stations

text: is

text: known

text: in

text: a

text: step

text: to

text: contain

text: more

text: than

text: one

text: message

text: and

text: the

text: set

text: of

text: stations

text: C

text: enabled

text: in

text: the

text: next

text: step

text: contains

text: station

text: s

text: then

text: set

text: C

text: contains

text: also

text: all

text: the

text: stations

text: preceding

text: s

text: whose

text: status,

text: with

text: respect

text: to

text: holding

text: a

text: message,

text: has

text: not

text: been

text: clariﬁed

text: yet

text: (this

text: is

text: the

text: FCFS

text: property).

text: If

text: a

text: set

text: B

text: of

text: stations

text: is

text: known

text: in

text: a

text: step

text: to

text: contain

text: more

text: than

text: one

text: message

text: then

text: in

text: the

text: next

text: step

text: a

text: subset

text: of

text: B

text: is

text: enabled

text: (this

text: is

text: the

text: property

text: of

text: being

text: nested).

text: A

text: method

text: to

text: construct

text: an

text: optimal

text: nested

text: FCFS

text: algorithm

text: for

text: a

text: given

text: probability

text: to

text: hold

text: a

text: message

text: (Bernoulli

text: arrivals

text: for

text: static

text: model)

text: has

text: been

text: developed

text: in

text: It

text: is

text: based

text: on

text: the

text: Markovian

text: decision

text: theory,

text: in

text: particular

text: on

text: the

text: value

text: iteration

text: algorithm

text: (see

text: and

text: the

text: Odoni

text: bound

text: (see

text: Panwar,

text: Towsley

text: and

text: Wolf

text: developed

text: a

text: scheme

text: of

text: mixing

text: algorithms,

text: which

text: are

text: not

text: FCFS,

text: and

text: showed

text: that

text: they

text: have

text: higher

text: transmission

text: rates

text: than

text: optimal

text: nested

text: FCFS

text: ones,

text: for

text: certain

text: small

text: probabilities

text: to

text: hold

text: messages.

text: To

text: obtain

text: such

text: an

text: algorithm,

text: run

text: an

text: optimal

text: nested

text: FCFS

text: algorithm

text: augmented

text: with

text: the

text: following

text: trick.

text: Suppose

text: that

text: we

text: have

text: identiﬁed

text: a

text: set

text: s

text: s

text: s

text: of

text: three

text: stations,

text: of

text: which

text: we

text: know

text: only

text: that

text: at

text: least

text: two

text: of

text: them

text: hold

text: packets.

text: Then

text: instead

text: of

text: enabling

text: either

text: s

text: or

text: s

text: s

text: as

text: a

text: FCFS

text: algorithm

text: would

text: do,

text: enable

text: s

text: s

text: where

text: station

text: s

text: is

text: the

text: next

text: station

text: after

text: s

text: and

text: which

text: may

text: or

text: may

text: not

text: hold

text: a

text: message.

text: This

text: approach

text: works

text: because,

text: for

text: suﬃciently

text: small

text: probability

text: to

text: hold

text: a

text: message,

text: station

text: s

text: will

text: likely

text: turn

text: out

text: not

text: to

text: hold

text: a

text: message,

text: so

text: with

text: a

text: single

text: try

text: we

text: will

text: eliminate

text: two

text: stations.

text: Acknowledgement-based

text: protocols

text: Now

text: we

text: consider

text: protocols

text: which

text: rely

text: on

text: the

text: weakest

text: feedback,

text: that

text: of

text: a

text: network

text: without

text: collision

text: detection.

text: They

text: can

text: be

text: run

text: on

text: any

text: single-hop

text: network,

text: they

text: simply

text: ignore

text: the

text: information

text: from

text: the

text: channel,

text: if

text: any,

text: obtained

text: while

text: staying

text: idle.

text: Such

text: protocols

text: usually

text: erase

text: their

text: history

text: after

text: a

text: successful

text: broadcast,

text: so

text: they

text: are

text: acknowledgement-based.

text: Because

text: of

text: that,

text: we

text: will

text: not

text: distinguish

text: between

text: possibly

text: more

text: general

text: arbitrary

text: protocols

text: for

text: the

text: channel

text: without

text: collision

text: detection

text: and

text: acknowledgement-based

text: protocols.

text: The

text: oldest

text: protocols,

text: namely

text: Aloha

text: and

text: the

text: binary

text: exponential

text: backoﬀ,

text: are

text: in

text: this

text: class.

text: The

text: inﬁnitely-many

text: users

text: model

text: was

text: initially

text: considered

text: with

text: a

text: hope

text: to

text: show

text: in

text: a

text: clean

text: setting

text: that

text: these

text: two

text: protocols

text: were

text: stable,

text: at

text: least

text: for

text: suﬃciently

text: small

text: arrival

text: rates.

text: First,

text: it

text: was

text: realized

text: that

text: the

text: expected

text: packet

text: delay

text: in

text: Aloha

text: is

text: inﬁnite

text: (see

text: Then

text: it

text: was

text: shown

text: that

text: Aloha

text: is

text: unstable

text: for

text: any

text: arrival

text: rate

text: (see

text: This

text: follows

text: directly

text: from

text: the

text: Kaplan’s

text: criterion

text: (see

text: Section

text: Namely,

text: ﬁrst

text: notice

text: that

text: the

text: downward

text: transitions

text: are

text: uniformly

text: bounded.

text: Secondly,

text: let

text: f

text: be

text: the

text: that

text: a

text: station

text: a

text: backlogged

text: a

text: broadcast

text: in

text: a

text: step,

text: and

text: let

text: i

text: be

text: the

text: number

text: of

text: such

text: stations.

text: Then

text: the

text: drift

text: is

text: at

text: least

text: e

text: λ

text: λe

text: λ

text: e

text: λ

text: i

text: f

text: f)i

text: So

text: it

text: is

text: positive

text: and

text: bounded

text: away

text: from

text: zero

text: by

text: a

text: constant

text: for

text: suﬃciently

text: large

text: i.

text: Rosenkrantz

text: and

text: Towsley

text: proved

text: that

text: Aloha

text: is

text: transient,

text: by

text: their

text: criterion

text: based

text: on

text: the

text: martingale

text: convergence

text: theorem

text: (see

text: Section

text: This

text: result

text: was

text: later

text: strengthened

text: by

text: Kelly


text: 2. The sizes of nodes at the same level i are all equal to bri, for some constant parameters b and r. The arity of the tree is some positive integer k, which is a parameter satisfying k > r. The protocol operates as follows. When a message m arrives at time step t then it is assigned to the leaf v which is the leftmost one among those with the property L(v) > t. As soon as m is assigned to a node v then it picks a time t uniformly at random from T rial(v), and is attempted to be sent onto the channel at time step t. If a failure occurs then message m is moved immediately to the parent of v. This deﬁnes the way message m keeps moving up the tree along the ancestor links until eventually it is broadcast successfully. Notice that the protocol described above resembles the unmodiﬁed exponential backoﬀ protocols in that it uses a partition of time steps into disjoint subsets S of sizes growing exponentially in i. i,t Messages that arrive at time step t jump from one subset S to the next one S after having i,t i+1,t failed to use the channel at a random time step in S . The eﬃciency of the protocol stems from i,t the fact that groups of many messages arriving together are spread among a number of leaves and hence handled independently; this is because the trial sets of leaves are not contiguous segments of time steps but are intertwined with the trial sets of the nodes from higher levels. 5 Finitely-many users models In this section we continue our discussion of the single-hop networks, concentrating on the case of ﬁnitely many stations, which may be considered as more realistic. Also it allows to study natural problems for the static arrivals which have no counterparts in the inﬁnitely-many users model, namely when the packets are distributed arbitrarily among the stations. These problems are considered in the next subsection. We assume the ternary feedback, unless stated otherwise. 5.1 Static case Let n be the total number of stations, and suppose some k of them have messages. The static selection problem is to broadcast just any single message successfully. The all-broadcast problem is to make all the k stations with messages to broadcast successfully. Notice ﬁrst that if the value of k is known to the participating stations then they may run controlled Aloha, that is, each would broadcast with probability 1/k in a step, independently, and a successful broadcast will happen O after the expected time (1). Hence we assume in what follows that the number k is not known to the stations. Willard [117] developed a randomized protocol for the static selection problem. It is in two versions. The ﬁrst one covers the scenario when number n is known, it has the expected time O lg lg n + (1). The second version assumes that n is unknown and terminates in the expected time O lg lg k + (lg lg lg k). We present a brief overview of the approach in [117]. Suppose ﬁrst that number n is known. The algorithm is in two phases. The underlying idea of the ﬁrst phase is to perform a binary search on a space of size log n to estimate the number k of stations with messages. This is done by adaptively adjusting the individual probabilities to broadcast. More precisely, let K be an integer, and let TEST(K) be a procedure in which each stations performs a broadcast in a step with the probability 1/K; it returns either silence or success or collision. Let lg() be the 21

text: The

text: sizes

text: of

text: nodes

text: at

text: the

text: same

text: level

text: i

text: are

text: all

text: equal

text: to

text: bri,

text: for

text: some

text: constant

text: parameters

text: b

text: and

text: r.

text: The

text: arity

text: of

text: the

text: tree

text: is

text: some

text: positive

text: integer

text: k,

text: which

text: is

text: a

text: parameter

text: satisfying

text: k

text: r.

text: The

text: protocol

text: operates

text: as

text: follows.

text: When

text: a

text: message

text: m

text: arrives

text: at

text: time

text: step

text: t

text: then

text: it

text: is

text: assigned

text: to

text: the

text: leaf

text: v

text: which

text: is

text: the

text: leftmost

text: one

text: among

text: those

text: with

text: the

text: property

text: L(v)

text: t.

text: As

text: soon

text: as

text: m

text: is

text: assigned

text: to

text: a

text: node

text: v

text: then

text: it

text: picks

text: a

text: time

text: t

text: uniformly

text: at

text: random

text: from

text: T

text: rial(v),

text: and

text: is

text: attempted

text: to

text: be

text: sent

text: onto

text: the

text: channel

text: at

text: time

text: step

text: t.

text: If

text: a

text: failure

text: occurs

text: then

text: message

text: m

text: is

text: moved

text: immediately

text: to

text: the

text: parent

text: of

text: v.

text: This

text: deﬁnes

text: the

text: way

text: message

text: m

text: keeps

text: moving

text: up

text: the

text: tree

text: along

text: the

text: ancestor

text: links

text: until

text: eventually

text: it

text: is

text: broadcast

text: successfully.

text: Notice

text: that

text: the

text: protocol

text: described

text: above

text: resembles

text: the

text: unmodiﬁed

text: exponential

text: backoﬀ

text: protocols

text: in

text: that

text: it

text: uses

text: a

text: partition

text: of

text: time

text: steps

text: into

text: disjoint

text: subsets

text: S

text: of

text: sizes

text: growing

text: exponentially

text: in

text: i.

text: i,t

text: Messages

text: that

text: arrive

text: at

text: time

text: step

text: t

text: jump

text: from

text: one

text: subset

text: S

text: to

text: the

text: next

text: one

text: S

text: after

text: having

text: i,t

text: failed

text: to

text: use

text: the

text: channel

text: at

text: a

text: random

text: time

text: step

text: in

text: S

text: The

text: eﬃciency

text: of

text: the

text: protocol

text: stems

text: from

text: i,t

text: the

text: fact

text: that

text: groups

text: of

text: many

text: messages

text: arriving

text: together

text: are

text: spread

text: among

text: a

text: number

text: of

text: leaves

text: and

text: hence

text: handled

text: independently;

text: this

text: is

text: because

text: the

text: trial

text: sets

text: of

text: leaves

text: are

text: not

text: contiguous

text: segments

text: of

text: time

text: steps

text: but

text: are

text: intertwined

text: with

text: the

text: trial

text: sets

text: of

text: the

text: nodes

text: from

text: higher

text: levels.

text: Finitely-many

text: users

text: models

text: In

text: this

text: section

text: we

text: continue

text: our

text: discussion

text: of

text: the

text: single-hop

text: networks,

text: concentrating

text: on

text: the

text: case

text: of

text: ﬁnitely

text: many

text: stations,

text: which

text: may

text: be

text: considered

text: as

text: more

text: realistic.

text: Also

text: it

text: allows

text: to

text: study

text: natural

text: problems

text: for

text: the

text: static

text: arrivals

text: which

text: have

text: no

text: counterparts

text: in

text: the

text: inﬁnitely-many

text: users

text: model,

text: namely

text: when

text: the

text: packets

text: are

text: distributed

text: arbitrarily

text: among

text: the

text: stations.

text: These

text: problems

text: are

text: considered

text: in

text: the

text: next

text: subsection.

text: We

text: assume

text: the

text: ternary

text: feedback,

text: unless

text: stated

text: otherwise.

text: Static

text: case

text: Let

text: n

text: be

text: the

text: total

text: number

text: of

text: stations,

text: and

text: suppose

text: some

text: k

text: of

text: them

text: have

text: messages.

text: The

text: static

text: selection

text: problem

text: is

text: to

text: broadcast

text: just

text: any

text: single

text: message

text: successfully.

text: The

text: all-broadcast

text: problem

text: is

text: to

text: make

text: all

text: the

text: k

text: stations

text: with

text: messages

text: to

text: broadcast

text: successfully.

text: Notice

text: ﬁrst

text: that

text: if

text: the

text: value

text: of

text: k

text: is

text: known

text: to

text: the

text: participating

text: stations

text: then

text: they

text: may

text: run

text: controlled

text: Aloha,

text: that

text: is,

text: each

text: would

text: broadcast

text: with

text: probability

text: in

text: a

text: step,

text: independently,

text: and

text: a

text: successful

text: broadcast

text: will

text: happen

text: O

text: after

text: the

text: expected

text: time

text: Hence

text: we

text: assume

text: in

text: what

text: follows

text: that

text: the

text: number

text: k

text: is

text: not

text: known

text: to

text: the

text: stations.

text: Willard

text: developed

text: a

text: randomized

text: protocol

text: for

text: the

text: static

text: selection

text: problem.

text: It

text: is

text: in

text: two

text: versions.

text: The

text: ﬁrst

text: one

text: covers

text: the

text: scenario

text: when

text: number

text: n

text: is

text: known,

text: it

text: has

text: the

text: expected

text: time

text: O

text: lg

text: lg

text: n

text: The

text: second

text: version

text: assumes

text: that

text: n

text: is

text: unknown

text: and

text: terminates

text: in

text: the

text: expected

text: time

text: O

text: lg

text: lg

text: k

text: (lg

text: lg

text: lg

text: k).

text: We

text: present

text: a

text: brief

text: overview

text: of

text: the

text: approach

text: in

text: Suppose

text: ﬁrst

text: that

text: number

text: n

text: is

text: known.

text: The

text: algorithm

text: is

text: in

text: two

text: phases.

text: The

text: underlying

text: idea

text: of

text: the

text: ﬁrst

text: phase

text: is

text: to

text: perform

text: a

text: binary

text: search

text: on

text: a

text: space

text: of

text: size

text: log

text: n

text: to

text: estimate

text: the

text: number

text: k

text: of

text: stations

text: with

text: messages.

text: This

text: is

text: done

text: by

text: adaptively

text: adjusting

text: the

text: individual

text: probabilities

text: to

text: broadcast.

text: More

text: precisely,

text: let

text: K

text: be

text: an

text: integer,

text: and

text: let

text: TEST(K)

text: be

text: a

text: procedure

text: in

text: which

text: each

text: stations

text: performs

text: a

text: broadcast

text: in

text: a

text: step

text: with

text: the

text: probability

text: it

text: returns

text: either

text: silence

text: or

text: success

text: or

text: collision.

text: Let

text: lg()

text: be

text: the


text: √ needs time Ω(log n) on some 2-relation. An Ω(h + log log n) lower bound, for routing h-relations in the OCPC model, was shown by Goldberg, Jerrum and MacKenzie [50], with no restriction on algorithms, in particular it covers indirect algorithms. 5.2 Dynamic arrivals (cid:80) Let the number of stations be denoted by n. The average arrival rate at station i is λ , and i λ = ≤ ≤ λ is the total arrival rate. 1 i n i 5.2.1 Aloha If arrivals are diversiﬁed among the stations, then we need the probability of performing a broadcast in Aloha also diversiﬁed, that is, station i performs a broadcast in a step with some probability f , provided its queue is nonempty, independently of the other steps and stations. i Tsybakov and Mikhailov [112] considered arbitrary arrival processes, not necessary Bernoulli, and showed that Aloha was stable for certain conﬁgurations of parameters. For more on the topic see [98, 106, 107]. These results are in contrast with the situation for the inﬁnitely-many users model where Aloha is not even weakly stable (see Subsection ). However this is not that surprising if we realize that with the number of station n ﬁxed and known to all the stations, using f = Θ(1/n) i yields a process that is quite similar to controlled Aloha, hence it might be expected to be stable, at least for certain arrival rates. M (cid:104) (cid:105) Consider the Markov chain which has the sequences of sizes of the buﬀers q , . . . , q as o 1 n its states. This chain is not state homogeneous, in the sense that the probability of moving from − state a to b by vector c = b a does not depend only on c. The approach in [112] was by way of considering another state homogeneous Markov chain, which was suggested by the observation that Aloha has its worst time when all the buﬀers are nonempty. First let us present intuitions of this approach, inspired by [112]. For the simplicity of calculations, let us consider the special case when the arrivals are Bernoulli and distributed evenly among the stations, that is λ = λ/n, i and also where the probabilities f = f/n are all equal, for i < n. Deﬁne the protocol Aloha with i jamming to run like Aloha but if a station has an empty buﬀer then let it immediately generate itself a dummy message and run Aloha until the packet with this message is successfully broadcast. It is intuitively clear that if the Aloha with jamming is stable so is the original Aloha. We compute the drift in order to apply the Pakes’ criterion. It is equal to the average arrival rate minus the (cid:16) (cid:17) average departure rate. The departure rate is − · f · − f n 1 − ≈ − − n 1 e λ fe fe λ . n n However the arrival rate is not just λ but also the average arrival rate of the dummy packets. This additional rate can be estimated directly by ﬁnding the stationary distribution of the Markov chain, which requires solving a linear recurrence with constant coeﬃcients. After combining all this we obtain a bound on the arrival rate which guarantees ergodicity, details are omitted. The approach presented in [112] was direct, by way of generating functions and systems of equations to determine probabilities, rather than by applying any ergodicity criteria. The authors M considered Markov chains , for k = 1, . . . , n, with the state space 0, 1, 2, . . ., where state i k corresponds to the total number of packets in the buﬀer of the k-th station, and the probability p −ij of going from i to j is deﬁned as the probability of changing the buﬀer of the k-th station by j i 24 ##LTLine## ##LTLine## ##LTLine##

text: needs

text: time

text: Ω(log

text: n)

text: on

text: some

text: An

text: Ω(h

text: log

text: log

text: n)

text: lower

text: bound,

text: for

text: routing

text: h-relations

text: in

text: the

text: OCPC

text: model,

text: was

text: shown

text: by

text: Goldberg,

text: Jerrum

text: and

text: MacKenzie

text: with

text: no

text: restriction

text: on

text: algorithms,

text: in

text: particular

text: it

text: covers

text: indirect

text: algorithms.

label: section

text: Dynamic

text: arrivals

text: Let

text: the

text: number

text: of

text: stations

text: be

text: denoted

text: by

text: n.

text: The

text: average

text: arrival

text: rate

text: at

text: station

text: i

text: is

text: λ

text: and

text: i

text: λ

text: λ

text: is

text: the

text: total

text: arrival

text: rate.

text: i

text: n

text: i

text: Aloha

text: If

text: arrivals

text: are

text: diversiﬁed

text: among

text: the

text: stations,

text: then

text: we

text: need

text: the

text: probability

text: of

text: performing

text: a

text: broadcast

text: in

text: Aloha

text: also

text: diversiﬁed,

text: that

text: is,

text: station

text: i

text: performs

text: a

text: broadcast

text: in

text: a

text: step

text: with

text: some

text: probability

text: f

text: provided

text: its

text: queue

text: is

text: nonempty,

text: independently

text: of

text: the

text: other

text: steps

text: and

text: stations.

text: i

text: Tsybakov

text: and

text: Mikhailov

text: considered

text: arbitrary

text: arrival

text: processes,

text: not

text: necessary

text: Bernoulli,

text: and

text: showed

text: that

text: Aloha

text: was

text: stable

text: for

text: certain

text: conﬁgurations

text: of

text: parameters.

text: For

text: more

text: on

text: the

text: topic

text: see

text: These

text: results

text: are

text: in

text: contrast

text: with

text: the

text: situation

text: for

text: the

text: inﬁnitely-many

text: users

text: model

text: where

text: Aloha

text: is

text: not

text: even

text: weakly

text: stable

text: (see

text: Subsection

text: However

text: this

text: is

text: not

text: that

text: surprising

text: if

text: we

text: realize

text: that

text: with

text: the

text: number

text: of

text: station

text: n

text: ﬁxed

text: and

text: known

text: to

text: all

text: the

text: stations,

text: using

text: f

text: i

text: yields

text: a

text: process

text: that

text: is

text: quite

text: similar

text: to

text: controlled

text: Aloha,

text: hence

text: it

text: might

text: be

text: expected

text: to

text: be

text: stable,

text: at

text: least

text: for

text: certain

text: arrival

text: rates.

text: M

text: Consider

text: the

text: Markov

text: chain

text: which

text: has

text: the

text: sequences

text: of

text: sizes

text: of

text: the

text: buﬀers

text: q

text: q

text: as

text: o

text: n

text: its

text: states.

text: This

text: chain

text: is

text: not

text: state

text: homogeneous,

text: in

text: the

text: sense

text: that

text: the

text: probability

text: of

text: moving

text: from

text: state

text: a

text: to

text: b

text: by

text: vector

text: c

text: b

text: a

text: does

text: not

text: depend

text: only

text: on

text: c.

text: The

text: approach

text: in

text: was

text: by

text: way

text: of

text: considering

text: another

text: state

text: homogeneous

text: Markov

text: chain,

text: which

text: was

text: suggested

text: by

text: the

text: observation

text: that

text: Aloha

text: has

text: its

text: worst

text: time

text: when

text: all

text: the

text: buﬀers

text: are

text: nonempty.

text: First

text: let

text: us

text: present

text: intuitions

text: of

text: this

text: approach,

text: inspired

text: by

text: For

text: the

text: simplicity

text: of

text: calculations,

text: let

text: us

text: consider

text: the

text: special

text: case

text: when

text: the

text: arrivals

text: are

text: Bernoulli

text: and

text: distributed

text: evenly

text: among

text: the

text: stations,

text: that

text: is

text: λ

text: λ/n,

text: i

text: and

text: also

text: where

text: the

text: probabilities

text: f

text: f/n

text: are

text: all

text: equal,

text: for

text: i

text: n.

text: Deﬁne

text: the

text: protocol

text: Aloha

text: with

text: i

text: jamming

text: to

text: run

text: like

text: Aloha

text: but

text: if

text: a

text: station

text: has

text: an

text: empty

text: buﬀer

text: then

text: let

text: it

text: immediately

text: generate

text: itself

text: a

text: dummy

text: message

text: and

text: run

text: Aloha

text: until

text: the

text: packet

text: with

text: this

text: message

text: is

text: successfully

text: broadcast.

text: It

text: is

text: intuitively

text: clear

text: that

text: if

text: the

text: Aloha

text: with

text: jamming

text: is

text: stable

text: so

text: is

text: the

text: original

text: Aloha.

text: We

text: compute

text: the

text: drift

text: in

text: order

text: to

text: apply

text: the

text: Pakes’

text: criterion.

text: It

text: is

text: equal

text: to

text: the

text: average

text: arrival

text: rate

text: minus

text: the

text: average

text: departure

text: rate.

text: The

text: departure

text: rate

text: is

text: f

text: f

text: n

text: n

text: e

text: λ

text: fe

text: fe

text: λ

text: n

text: n

text: However

text: the

text: arrival

text: rate

text: is

text: not

text: just

text: λ

text: but

text: also

text: the

text: average

text: arrival

text: rate

text: of

text: the

text: dummy

text: packets.

text: This

text: additional

text: rate

text: can

text: be

text: estimated

text: directly

text: by

text: ﬁnding

text: the

text: stationary

text: distribution

text: of

text: the

text: Markov

text: chain,

text: which

text: requires

text: solving

text: a

text: linear

text: recurrence

text: with

text: constant

text: coeﬃcients.

text: After

text: combining

text: all

text: this

text: we

text: obtain

text: a

text: bound

text: on

text: the

text: arrival

text: rate

text: which

text: guarantees

text: ergodicity,

text: details

text: are

text: omitted.

text: The

text: approach

text: presented

text: in

text: was

text: direct,

text: by

text: way

text: of

text: generating

text: functions

text: and

text: systems

text: of

text: equations

text: to

text: determine

text: probabilities,

text: rather

text: than

text: by

text: applying

text: any

text: ergodicity

text: criteria.

text: The

text: authors

text: M

text: considered

text: Markov

text: chains

text: for

text: k

text: n,

text: with

text: the

text: state

text: space

text: where

text: state

text: i

text: k

text: corresponds

text: to

text: the

text: total

text: number

text: of

text: packets

text: in

text: the

text: buﬀer

text: of

text: the

text: k-th

text: station,

text: and

text: the

text: probability

text: p

text: −ij

text: of

text: going

text: from

text: i

text: to

text: j

text: is

text: deﬁned

text: as

text: the

text: probability

text: of

text: changing

text: the

text: buﬀer

text: of

text: the

text: k-th

text: station

text: by

text: j

text: i

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: A brief exposition of the algorithm is as follows. There are two procedures Decay and Broadcast. An essential property of procedure Decay is that if node x has some d neighbors, and they all know ≥ the message and simultaneously perform Decay(k), where k 2 lg d, then node x will hear the message by time step k with the probability greater than 1/2. procedure Decay(k); repeat at most k times : transmit the message ; toss a coin ; until tails come up . The broadcasting algorithm itself begins with the source node transmitting the message to the nodes reachable from it directly, then all the nodes perform procedure Broadcast, which consists of procedure Decay(k) iterated about log(n/(cid:15)) times, where number k is about log ∆. A precise description of Broadcast is as follows: procedure Broadcast ; (cid:100) (cid:101) set k = 2 lg ∆ ; wait until receiving the message ; (cid:100) (cid:101) repeat 2 lg(n/(cid:15)) times : wait until the time step is a multiple of k ; call Decay(k) ; end repeat . O · The expected number of transmissions performed by the algorithm is (n log(n/(cid:15))). Observe that the information reaching a node might have traversed the network via paths of diﬀerent lengths, so the broadcasting algorithm cannot be used directly to ﬁnd distances to the source node. A Monte Carlo algorithm to construct the Breadth-First Search (BFS) tree was developed in [12], which also ﬁnds the distances of each node to the root. The algorithm is again based on procedure Decay, which now is slowed down to increase the probability to detect distances correctly from the times of arrivals. The algorithm refers to local variable distance, to store the distance to the source node, and the current time step given by time. Each node runs the following procedure BFS: procedure BFS : (cid:100) (cid:101) set k = 2 lg ∆ ; wait until receiving the message ; (cid:98) (cid:100) (cid:101) (cid:99) set distance = time/(k lg(n/(cid:15)) ) ; (cid:100) (cid:101) repeat lg(n/(cid:15)) times : (cid:100) (cid:101) wait until the time step is a multiple of k lg(n/(cid:15)) ; call Decay(k) ; end repeat . O − The algorithm operates in time (D log ∆ log(n/(cid:15))) with the probability 1 (cid:15), and is correct with the same probability. 28

text: A

text: brief

text: exposition

text: of

text: the

text: algorithm

text: is

text: as

text: follows.

text: There

text: are

text: two

text: procedures

text: Decay

text: and

text: Broadcast.

text: An

text: essential

text: property

text: of

text: procedure

text: Decay

text: is

text: that

text: if

text: node

text: x

text: has

text: some

text: d

text: neighbors,

text: and

text: they

text: all

text: know

text: the

text: message

text: and

text: simultaneously

text: perform

text: Decay(k),

text: where

text: k

text: lg

text: d,

text: then

text: node

text: x

text: will

text: hear

text: the

text: message

text: by

text: time

text: step

text: k

text: with

text: the

text: probability

text: greater

text: than

text: procedure

text: Decay(k);

text: repeat

text: at

text: most

text: k

text: times

text: transmit

text: the

text: message

text: toss

text: a

text: coin

text: until

text: tails

text: come

text: up

text: The

text: broadcasting

text: algorithm

text: itself

text: begins

text: with

text: the

text: source

text: node

text: transmitting

text: the

text: message

text: to

text: the

text: nodes

text: reachable

text: from

text: it

text: directly,

text: then

text: all

text: the

text: nodes

text: perform

text: procedure

text: Broadcast,

text: which

text: consists

text: of

text: procedure

text: Decay(k)

text: iterated

text: about

text: times,

text: where

text: number

text: k

text: is

text: about

text: log

text: A

text: precise

text: description

text: of

text: Broadcast

text: is

text: as

text: follows:

text: procedure

text: Broadcast

text: set

text: k

text: lg

text: wait

text: until

text: receiving

text: the

text: message

text: repeat

text: times

text: wait

text: until

text: the

text: time

text: step

text: is

text: a

text: multiple

text: of

text: k

text: call

text: Decay(k)

text: end

text: repeat

text: O

text: The

text: expected

text: number

text: of

text: transmissions

text: performed

text: by

text: the

text: algorithm

text: is

text: (n

text: Observe

text: that

text: the

text: information

text: reaching

text: a

text: node

text: might

text: have

text: traversed

text: the

text: network

text: via

text: paths

text: of

text: diﬀerent

text: lengths,

text: so

text: the

text: broadcasting

text: algorithm

text: cannot

text: be

text: used

text: directly

text: to

text: ﬁnd

text: distances

text: to

text: the

text: source

text: node.

text: A

text: Monte

text: Carlo

text: algorithm

text: to

text: construct

text: the

text: Breadth-First

text: Search

text: (BFS)

text: tree

text: was

text: developed

text: in

text: which

text: also

text: ﬁnds

text: the

text: distances

text: of

text: each

text: node

text: to

text: the

text: root.

text: The

text: algorithm

text: is

text: again

text: based

text: on

text: procedure

text: Decay,

text: which

text: now

text: is

text: slowed

text: down

text: to

text: increase

text: the

text: probability

text: to

text: detect

text: distances

text: correctly

text: from

text: the

text: times

text: of

text: arrivals.

text: The

text: algorithm

text: refers

text: to

text: local

text: variable

text: distance,

text: to

text: store

text: the

text: distance

text: to

text: the

text: source

text: node,

text: and

text: the

text: current

text: time

text: step

text: given

text: by

text: time.

text: Each

text: node

text: runs

text: the

text: following

text: procedure

text: BFS:

text: procedure

text: BFS

text: set

text: k

text: lg

text: wait

text: until

text: receiving

text: the

text: message

text: set

text: distance

text: time/(k

text: repeat

text: times

text: wait

text: until

text: the

text: time

text: step

text: is

text: a

text: multiple

text: of

text: k

text: call

text: Decay(k)

text: end

text: repeat

text: O

text: The

text: algorithm

text: operates

text: in

text: time

text: (D

text: log

text: with

text: the

text: probability

text: and

text: is

text: correct

text: with

text: the

text: same

text: probability.


text: assume that multi-hop radio networks are ad-hoc, when considering distributed communication protocols for them, unless stated otherwise. A model related to radio networks is that of optical communication (see [46, 49, 50]). To explain the relationship, notice that a radio network can be interpreted as operating under just one wave frequency used by all the nodes. In an optical communication parallel computer (OCPC) each node v is assigned its own frequency F (v). Node v can simultaneously receive any message placed on F (v) (possibly garbled) and send a single message to the channel of any other node. Node v can hear a message delivered by F (v) only if it was just a single message placed on it in a step. We can see that OCPC is similar to a single-hop radio network in two respects: ﬁrst, it can be interpreted as a communication network with the topology of a complete bi-directional graph, and secondly, if many messages are send to a node then it cannot hear any of them. The main diﬀerence between the models of OCPC and single-hop radio-networks is that the operation of sending in an OCPC network delivers the message to just a single recipient node rather than to all the stations. A node v sending to channel F (v ) cannot detect the collisions at F (v ) but 1 2 2 at F (v ). If a message is successfully delivered in a single-hop radio network then the sender also 1 can hear the message, which serves as an acknowledgement. This mechanism can be implemented indirectly in the OCPC: let each packet carry both a message and the identiﬁcation of its sender, then let after each “sending step” another “acknowledgement step” follow, when all the nodes that have successfully received messages send conﬁrmation messages to the senders. Our discussion of optical communication protocols will be limited to situations in which there is some connection with radio-network communication. 2 Single-hop networks Most of the work done about randomized communication in radio networks has concerned multiple access channels. In this section we ﬁrst give a historical background, then discuss various methodologies used to investigate problems in this area. 2.1 History and existing systems The ﬁrst communication network with the semantics of a (single-hop) radio network seems to be the system Alohanet [1, 4]. developed in the beginning of the 1970’s at the University of Hawaii. The system used packet radio communication between the central computer and its terminals on the campuses on remote islands. That is how a “broadcast channel” was born. This historical development is a justiﬁcation to classify as “radio communication” all modes of communication in which conﬂicting packets cannot be heard, even if the electromagnetic waves are not used as a medium to propagate signals. The work on the Alohanet system has started already at the end of the 1960’s. As Abramson [3] put it, the key idea was: “not the use of radio communications for computers, but the use of a broadcast communication architecture for the radio channel.” The developers of Alohanet realized that a protocol was needed to handle bursty traﬃc, with most of the stations being idle for most of the time, hence techniques like time-division multiplexing were not considered suitable. The protocol invented for Alohanet is called Aloha. Its most relevant feature is that control is distributed among the attached stations, and arbitration of access is statistical. This is done in Aloha in an exceptionally simple way: the stations needing to broadcast backlogged packets keep tossing 3

text: assume

text: that

text: multi-hop

text: radio

text: networks

text: are

text: ad-hoc,

text: when

text: considering

text: distributed

text: communication

text: protocols

text: for

text: them,

text: unless

text: stated

text: otherwise.

text: A

text: model

text: related

text: to

text: radio

text: networks

text: is

text: that

text: of

text: optical

text: communication

text: (see

text: To

text: explain

text: the

text: relationship,

text: notice

text: that

text: a

text: radio

text: network

text: can

text: be

text: interpreted

text: as

text: operating

text: under

text: just

text: one

text: wave

text: frequency

text: used

text: by

text: all

text: the

text: nodes.

text: In

text: an

text: optical

text: communication

text: parallel

text: computer

text: (OCPC)

text: each

text: node

text: v

text: is

text: assigned

text: its

text: own

text: frequency

text: F

text: (v).

text: Node

text: v

text: can

text: simultaneously

text: receive

text: any

text: message

text: placed

text: on

text: F

text: (v)

text: (possibly

text: garbled)

text: and

text: send

text: a

text: single

text: message

text: to

text: the

text: channel

text: of

text: any

text: other

text: node.

text: Node

text: v

text: can

text: hear

text: a

text: message

text: delivered

text: by

text: F

text: (v)

text: only

text: if

text: it

text: was

text: just

text: a

text: single

text: message

text: placed

text: on

text: it

text: in

text: a

text: step.

text: We

text: can

text: see

text: that

text: OCPC

text: is

text: similar

text: to

text: a

text: single-hop

text: radio

text: network

text: in

text: two

text: respects:

text: ﬁrst,

text: it

text: can

text: be

text: interpreted

text: as

text: a

text: communication

text: network

text: with

text: the

text: topology

text: of

text: a

text: complete

text: bi-directional

text: graph,

text: and

text: secondly,

text: if

text: many

text: messages

text: are

text: send

text: to

text: a

text: node

text: then

text: it

text: cannot

text: hear

text: any

text: of

text: them.

text: The

text: main

text: diﬀerence

text: between

text: the

text: models

text: of

text: OCPC

text: and

text: single-hop

text: radio-networks

text: is

text: that

text: the

text: operation

text: of

text: sending

text: in

text: an

text: OCPC

text: network

text: delivers

text: the

text: message

text: to

text: just

text: a

text: single

text: recipient

text: node

text: rather

text: than

text: to

text: all

text: the

text: stations.

text: A

text: node

text: v

text: sending

text: to

text: channel

text: F

text: (v

text: cannot

text: detect

text: the

text: collisions

text: at

text: F

text: (v

text: but

text: at

text: F

text: (v

text: If

text: a

text: message

text: is

text: successfully

text: delivered

text: in

text: a

text: single-hop

text: radio

text: network

text: then

text: the

text: sender

text: also

text: can

text: hear

text: the

text: message,

text: which

text: serves

text: as

text: an

text: acknowledgement.

text: This

text: mechanism

text: can

text: be

text: implemented

text: indirectly

text: in

text: the

text: OCPC:

text: let

text: each

text: packet

text: carry

text: both

text: a

text: message

text: and

text: the

text: identiﬁcation

text: of

text: its

text: sender,

text: then

text: let

text: after

text: each

text: “sending

text: step”

text: another

text: “acknowledgement

text: step”

text: follow,

text: when

text: all

text: the

text: nodes

text: that

text: have

text: successfully

text: received

text: messages

text: send

text: conﬁrmation

text: messages

text: to

text: the

text: senders.

text: Our

text: discussion

text: of

text: optical

text: communication

text: protocols

text: will

text: be

text: limited

text: to

text: situations

text: in

text: which

text: there

text: is

text: some

text: connection

text: with

text: radio-network

text: communication.

text: Single-hop

text: networks

text: Most

text: of

text: the

text: work

text: done

text: about

text: randomized

text: communication

text: in

text: radio

text: networks

text: has

text: concerned

text: multiple

text: access

text: channels.

text: In

text: this

text: section

text: we

text: ﬁrst

text: give

text: a

text: historical

text: background,

text: then

text: discuss

text: various

text: methodologies

text: used

text: to

text: investigate

text: problems

text: in

text: this

text: area.

text: History

text: and

text: existing

text: systems

text: The

text: ﬁrst

text: communication

text: network

text: with

text: the

text: semantics

text: of

text: a

text: (single-hop)

text: radio

text: network

text: seems

text: to

text: be

text: the

text: system

text: Alohanet

text: developed

text: in

text: the

text: beginning

text: of

text: the

text: at

text: the

text: University

text: of

text: Hawaii.

text: The

text: system

text: used

text: packet

text: radio

text: communication

text: between

text: the

text: central

text: computer

text: and

text: its

text: terminals

text: on

text: the

text: campuses

text: on

text: remote

text: islands.

text: That

text: is

text: how

text: a

text: “broadcast

text: channel”

text: was

text: born.

text: This

text: historical

text: development

text: is

text: a

text: justiﬁcation

text: to

text: classify

text: as

text: “radio

text: communication”

text: all

text: modes

text: of

text: communication

text: in

text: which

text: conﬂicting

text: packets

text: cannot

text: be

text: heard,

text: even

text: if

text: the

text: electromagnetic

text: waves

text: are

text: not

text: used

text: as

text: a

text: medium

text: to

text: propagate

text: signals.

text: The

text: work

text: on

text: the

text: Alohanet

text: system

text: has

text: started

text: already

text: at

text: the

text: end

text: of

text: the

text: As

text: Abramson

text: put

text: it,

text: the

text: key

text: idea

text: was:

text: “not

text: the

text: use

text: of

text: radio

text: communications

text: for

text: computers,

text: but

text: the

text: use

text: of

text: a

text: broadcast

text: communication

text: architecture

text: for

text: the

text: radio

text: channel.”

text: The

text: developers

text: of

text: Alohanet

text: realized

text: that

text: a

text: protocol

text: was

text: needed

text: to

text: handle

text: bursty

text: traﬃc,

text: with

text: most

text: of

text: the

text: stations

text: being

text: idle

text: for

text: most

text: of

text: the

text: time,

text: hence

text: techniques

text: like

text: time-division

text: multiplexing

text: were

text: not

text: considered

text: suitable.

text: The

text: protocol

text: invented

text: for

text: Alohanet

text: is

text: called

text: Aloha.

text: Its

text: most

text: relevant

text: feature

text: is

text: that

text: control

text: is

text: distributed

text: among

text: the

text: attached

text: stations,

text: and

text: arbitration

text: of

text: access

text: is

text: statistical.

text: This

text: is

text: done

text: in

text: Aloha

text: in

text: an

text: exceptionally

text: simple

text: way:

text: the

text: stations

text: needing

text: to

text: broadcast

text: backlogged

text: packets

text: keep

text: tossing