SIAM J. COMPUT.

() 1992 Society for Industrial and Applied Mathematics

Vol. 21, No. 1, pp. 193-201, February 1992 015
Downloaded 11/22/13 to 132.64.42.56. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php

LOCALITY IN DISTRIBUTED GRAPH ALGORITHMS*

NATHAN LINIALt
Abstract. This paper concerns a number of algorithmic problems on graphs and how they may
be solved in a distributed fashion. The computational model is such that each node of the graph is
occupied by a processor which has its own ID. Processors are restricted to collecting data from others
which are at a distance at most away from them in time units, but are otherwise computationally
unbounded. This model focuses on the issue of locality in distributed processing, namely, to what
extent a global solution to a computational problem can be obtained from locally available data.
Three results are proved within this model:
A 3-coloring of an n-cycle requires time f(log* n). This bound is tight, by previous work
of Cole and Vishkin.
Any algorithm for coloring the d-regular tree of radius r which runs for time at most 2r/3
requires at least f(x/-) colors.
In an n-vertex graph of largest degree A, an O(A2)-coloring may be found in time O(log* n).

Key words, distributed algorithms, graph theory, locality, lower bounds

AMS(MOS) subject classifications. 05C35, 68R10, 68Q99

1. Introduction. In distributed processing all computations are made based on

local data. The aim of this paper is to bring up limitations that follow from this local
nature of the computation. Note that within the various computational models for
parallel computers this difficulty is specific to the distributed model. Shared memory
allows for fast dissemination of data, but no such means exist when dealing with
distributed systems.
In the present paper we are mostly interested in proving lower bounds, and there-
fore assume a powerful version of the distributed model: Each node of the undirected
graph G (V, E) is occupied by a processor. Computation is completely synchronous
and reliable. At each time unit a processor may pass messages to each of its neighbors,
and message size is unrestricted. Also, any computations carried out by individual
processors take one time unit and are not restricted in any way. This paper is only
concerned with the radius of the neighborhood around each node from which data
may be collected, this radius being the only significant parameter in this model, as
we later elaborate. Of interest is the time complexity of various "global" functions
of G, and the concrete examples are coloring and finding maximal independent sets.
Thus the theme of this paper is how local data may be utilized to find globally defined
solutions.
Before we proceed, symmetry-breaking has to be addressed (see [JS] and the
references therein for literature on symmetry-breaking). It is well known that most
functions cannot be computed in a distributed fashion by anonymous processors, even
for very simple graphs G. This impossibility usually results from symmetries that G
may have. Such symmetries are usually broken by means of either randomization or
the use of IDs, and the present paper is concerned only with the latter. Thus we
assume that there is a mapping ID from the set of vertices V to the positive integers.

Received by the editors July 17, 1989; accepted for publication (in revised form) December 4,
1990.
Computer Science Department, Hebrew University, Jerusalem 91904, Israel. Part of this work
was done while the author was visiting the IBM Research Center, Almaden, California, and the De-
partment of Computer Science, Stanford University, Stanford, California 94305. This work was sup-
ported in part by grants from the Israel-US Binational Science Foundation and the Israeli Academy
of Sciences.
193
 194 NATHAN LINIAL

In most cases ID is a bijection onto 1,..., V I- It is assumed that at time zero the
processor occupying a node in G knows the ID of that node. Incidentally, all our
Downloaded 11/22/13 to 132.64.42.56. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php

lower bounds hold even if every processor knows in advance what the graph G is, and
only the labeling function ID is unknown.
It is clear that the present model allows us to compute every function of G in
time O(diameter(G)). After this amount of time every processor obtains complete
knowledge of both G and ID. The problem is thus solved if, in the memory of each
processor a solution for the entire problem is prestored, for every possible labeling.
Our concern is therefore only with time complexities below diam(G). The major
question we raise is which functions may be computed by a nontrivial algorithm in
this model, in the sense that they can be computed faster than diam(G).
The model proposed here is, of course, of purely theoretical interest. Of the many
difficulties arising in distributed processing, it focuses only on transforming local data
into a global solution. Further research into this model may help classify problems as
either locally computable (solvable in time shorter than diam(G)) or not. One may
also look for bounds on run times which depend on graph parameters other than the
diameter. In accordance with the theory of the complexity class NC, it seems natural
to investigate graph problems whose time complexity in this model is polylogarithmic
in the number of vertices.
Here are our main results:
(1) Finding a maximal independent set distributively in a labeled n-cycle, requires
time (log* n). This bound is tight in view of the O(log* n) algorithm by Cole and
Vishkin [CV]. (Technically, their result was stated in the PRAM model, but it extends
without change to the distributed model as well.) Our proof relies on the interesting
construct of neighborhood graphs. An alternative proof based on the Ramsey theorem
was found by a number of other investigators in the area [A].
(2) Coloring trees: Let T be the d-ary tree ofheight r. In time 2r/3, it is
impossible to color T in fewer than colors. Note in contrast the algorithm by
Goldberg and Plotkin [GP], which shows that if every node in T "knows its parent
in the tree," i.e., a consistent orientation from the root outwards is given, then a
3-coloring can be found in time O(log* n). Though stated for the PRAM model, it is
easy to see that this result of [GP] applies to the distributed model as well.
(3) In a labeled graph of order n with maximal degree A, it is possible to find an
O(A2)-coloring in time (1 + o(1))log* n. This was previously shown in [GP] only in
the case of constant A.
Our terminology is standard: a k-labeling of a graph G (V, E) is 1:1 mapping
f V --. {1,..-,k}. In case k -[ V a k-labeling is called a labeling. Given a k-
labeling, G is said to be k-labeled, etc. Logarithms are to base 2. The k times iterated
logarithm is denoted by log (k) x, i.e., log(l) x :- log x and log(k) x log(log k-1 x).
The least integer k for which log (k) x < 1 is denoted by log* x.
2. Lower bound on finding a maximal independent set in a cycle. In
[CV] a very nice algorithm was presented to find a maximal independent set of vertices
(-- MIS) in the n-cycle Cn in time log* n. In this section we show that this is optimal
even in the present model, where computation takes no time. The algorithm presented
in 4 also achieves this time bound.
A basic observation is that in the present model there is no loss of generality
in assuming that processing proceeds by first collecting all data and then deciding.
That is, at time t each processor knows the labeling of all nodes at distance t or less
away. Also known are all edges between these nodes, except for edges both endpoints
 LOCALITY IN DISTRIBUTED GRAPH ALGORITHMS 195

of which are at distance exactly t. Note that no further information can reach a
processor by time t. This allows us to view the problem in purely combinatorial
Downloaded 11/22/13 to 132.64.42.56. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php

terms.
Let us state our theorem.
THEOREM 2.1. A synchronous distributed algorithm which finds a maximal in-
dependent set in a labeled n-cycle must take at least 1/2(log* n- 1) units of time. An
algorithm of the same class which colors the n-cycle with three colors requires time at
least 1/2 (log* n- 3). The same bounds hold also .for randomized algorithms.
Proof. The proof holds even under the assumption that there is a consistent
notion of clockwise orientation common to all processors. Given an algorithm which
finds a maximal independent set in the n-cycle endowed with a clockwise orientation,
it is easily seen that in one more timestep, the cycle may be 3-colored. The lower
bound is established for 3-coloring.
Coming back to the previous observation, at time t the data known to a processor
P is an ordered list of 2t / 1 labels, starting t places before it, through its own and on
to the next t labels. Let V be the set of all vectors (Xl,... ,x2t+l) where the xi are
mutually distinct integers from (1,..., n}. The algorithm is nothing but a mapping
c from V into { 1, 2, 3}.
Let us denote by Bt,n the graph whose set of vertices is V. All edges of Bt,n are
given by:
(xl,"’,x2t+l) and (y, xl,’.’,x2t)
are neighbors for all y
of degree 2(n- 2t- 1). Note that the mapping c: V
3-coloring of Bt,n. For suppose that c assigns
(Xl,’",x2t+l) and (y, xl,’",x2t)
-
# x2t+l. So St,, has n(n- 1)... (n-2t) vertices and is regular
{1, 2, 3} is, in fact, a proper

the same color. Then the 3-coloring algorithm for the n-cycle fails in case the labeling
happens to contain the segment:
y Xl X2 X2t+l.
The proof follows now by standard graph-theoretic arguments which show that the
chromatic number x(B,n) of B,n satisfies

x(Bt,,) t(log (2t) n),

the 2t times iterated logarithm of n. Therefore, for x(Bt,) to be at most 3, we must
have t (log* n).
The lower bound on x(Bt,) is proved, using a family of digraphs Ds,n closely
related to Bt,n. The vertices of Ds,, are all sequences (al,...,as) with 1 _< al <
a2 < < as <_ n. The outneighbors of (al,...,as) are all vertices of the form
(a2,-..,as,b) with as < b _< n. Note that Bt,n contains the underlying graph of
D2t+l,n, SO in particular x(Bt,) >_ x(D2t+l,n).
Given a digraph H (V, E) its dilinegraph DL(H) is a digraph whose vertex set
is E with (u, w) an edge if headH(u) tailH(w). The relation between the digraphs
D s,n is given by Proposition 2.1.
PROPOSITION 2.1. Dl,n is obtained from the complete graph of order n by re-
placing each edge by a pair of edges, one in each direction, and Ds+l,n DL(Ds,n)
for all s >_ 1.
 196 NATHAN LINIAL

Proof.The statement concerning Dl,n is just the definition. For the other claim,
identify the edge connecting (x,...,xs) and (x2,...,xs,y) in D,n with the vertex
Downloaded 11/22/13 to 132.64.42.56. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php

(Xl,...,x,y) in V(Ds+I,n) and check that the adjacency relationship in Ds+,n is

that of DL(Ds,,). D
The bound on x(D,n) is derived from the following simple and well-known propo-
sition.
PROPOSITION 2.2. For a digraph G,
x(DL(G)) >_ log x(G).

Proof. A k-coloring of DL(G) may be thought of as a mapping @ E(G)

{1,...,k} such that if u,w e E(G) and head(u)- tail(w), then @(u) @(w). Now
vertex-color G by associating with node x the set

c(x) ((u) x- tail(u)}.

__
This is easily seen to be a 2 k vertex-coloring of G. Indeed if u (x, y) E E(G), then
(u) e c(x) but (u) c(y), or else is improper. Therefore c(x) c(y).
The main claim can be derived now. If an MIS can be found in time t- 1, then
necessarily
3 >_ x(B,).
But
x(Bt,n) x(D2t+l,n) log (2t) n.
So
2t _> log*n- 1, t _> (log 2*n- 1),
as claimed.
The claim on randomized algorithms is proved in Corollary 2.1 below. [:]
In contrast with the low time complexity of 3-coloring, we can show that for an
even n, finding a 2-coloring of Cn requires time f(n).
THEOREM 2.2. A synchronous distributed algorithm which 2-colors a labeled 2n
cycle with labels from {1,..., 2n} must take at least n- 1 units of time.
Proof. Now the lowest t has to be found such that Bt,2n is bipartite. But even
for t n- 2, the graph Bt,2n contains an odd cycle:

(1,...,2t + 1), (2,...,2t + 2), (3,...,2t + 3), (4,...,2t + 3, 1),

The claim follows.

Let us point out that for an even n the last theorem implies that finding a max-
imum independent set requires time In/2] 1. It is easily verified that the same is
true for odd n as well.
We want to elaborate on the method developed here and point out its general
features. Given a graph G (V, E) of order n, and t >_ 1, the t-neighborhood graph of
 LOCALITY IN DISTRIBUTED GRAPH ALGORITHMS 197

G, Nt(G) is constructed as follows: For every x E V let St(x) be the subgraph of G

spanned by those vertices y whose distance from x is at most t. For every x consider
Downloaded 11/22/13 to 132.64.42.56. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php

all the n-labelings of St(x).

Every such labeling is a node in Nt(G). Let 1 Vt(x) --, {1,-.. ,n} and
neighbors in Nt(G) if Ix, y] E(G) and there is a labeling (I) V(G)
such that -
2 Vt(y) --* {1,... ,n} be two of these vertices of Nt(G). They are taken to be
{1,... ,n}

and

Some easy observations regarding Nt(G) follow.

PROPOSITION 2.3. Neighborhood graphs have the following properties:
(1) x(Nt(G)) is the least number of colors with which G may be colored distribu-
tively on time t.
(2) x(Nt(G)) X(G) for t >_ diam(G).
(3) x(Nt(G)) is nonincreasing with t.
(4) For G Cn, the graph Ut,n is obtained from Nt(C,) by identifying vertices
in Nt (Cn) with identical sets of neighbors. In particular,

x(Bt,n) X(Nt(Cn)).

As in the case of the cycle, it is helpful to identify nonadjacent vertices with an

identical set of neighbors. Such an operation is called a reduction. Clearly it does not
change the chromatic number, while it may significantly simplify the graph. Neigh-
borhood graphs seem to be very interesting and promising constructs. Unfortunately,
the only case where we managed to calculate their graphical parameters is that of a
cycle. Particularly interesting are cases where in G the graph St(x) is independent of
x, as is the case, for example, with vertex transitive graphs.
Proposition 2.3 yields the following easy but interesting corollary.
COROLLARY 2.1. Irt the present model the time required to properly color a given
graph with a given number of colors cannot be reduced by using randomization.
Proof. The most general form of a randomized algorithm in the present model
allows each processor to precede each round of computation with any number of
coin flips, the outcomes of which are then passed to its neighbors along with all
other information, as in the deterministic version. Consider the following different
class C of randomized graph algorithms: A sufficiently long string of bits a is first
selected at random by some random source (not necessarily one of the processors in
the graph) and then announced to all processors. From this point on, the algorithm
proceeds in the usual deterministic way, where each processor gets to see its labeled
t-neighborhood (as well as the random string a, of course). It is not hard to see
that any randomized algorithm which can be performed in the present model can
be simulated by an algorithm in C. This is because a can be made long enough to
include as many random bits as may be required in any run of the original algorithm
by any processor at all. In the algorithm from C, processors get the advantage of
being informed of all these random bits, and in advance, which can only help.
Since we are interested in a lower bound, there is no loss of generality in consid-
ering only algorithms from the class C. Such an algorithm running in time t entails a
 198 NATHAN LINIAL

function which computes a color for a vertex from its t-neighborhood and the random
a. Fix a graph G, an integer t, and two adjacent vertices x and y in G. Consider
Downloaded 11/22/13 to 132.64.42.56. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php

the adjacent vertices and / in Nt(G) which represent compatible labelings of t-

,
neighborhoods of x, y, and a random string a. The color is chosen based on seeing
the labeled neighborhood and the random a must differ from the one given for r/, a.
In other words, the coloring function constitutes a valid coloring for a graph which is
the disjoint union of copies of Nt (G), one copy per each a. This graph has, of course,
the same chromatic number as Nt(G), and the claim follows. D

1
2

- 3. Lower bound on coloring trees.

THEOREM 3.1. Let T Td, be the rooted d-regular tree of radius r. Any syn-
chronous distributed algorithm running in time <_ r
cannot color T by fewer than
colors. The same bound holds for randomized algorithms as well.
Proof. There are d-regular graphs Rd,n on n vertices of chromatic number _> v/-,1/2
where all cycles have length >_ (4/3) (log n/ log(d 1)) (see [LPS]). Consequently for
t < (2/3)(logn/log(d- 1)), the graph N(Td,) contains a copy of a reduction of
Nt (Rd,n). Therefore

>
and so Td,r cannot be colored with fewer than
follows now on observing that for Td,r,

log n
>

1/2
>
colors in time t. The conclusion

> r.
log(d- 1)
Corollary 2.1 establishes the bound for randomized algorithms as well. D
Two remarks are in order now: It is probably possible to improve the lower
bound of 1/2vf to (d/logd) by using an appropriate random graph rather than
Ramanujan graphs (e.g., [B, 11.4]). It is shown in the next section that for a d-
regular graph, an O(d2)-coloring can be found in time O(log* n). The gap between
(d/log d) and d2 is quite intriguing and is closely related to the complexity of finding
an MIS distributively, as we explain below. Also, it is not clear how the number
of colors sufficient to color the tree goes down as t grows from (2r/3) to 2r, where
already two colors suffice.
4. An O(log* n) algorithm for O(A2)-coloring. This section contains some
positive results on what can be achieved distributively in this model. It is shown how
to find an O(A2)-coloring in time O(log* n). The first proof is based on the existence of
certain hypergraphs for which no explicit construction is known. However, as Karloff
pointed out [K], a slightly weaker, though constructive, set system suffices to achieve
this goal.
THEOREM 4.1. Let G be a graph of order n and largest degree A. It is possible
to color G with 5A 2 log n colors in one unit of time distributively. Equivalently,

x(NI(G)) <_ 5A 2 log n.

Proof. We need some combinatorial preparation.

 LOCALITY IN DISTRIBUTED GRAPH ALGORITHMS 199

LEMMA 4.1. For integers n > A, there is a family J o.f n subsets o.f (1,...,
5 A2 log n] } such that if Fo,..., FA E J, then

_
Downloaded 11/22/13 to 132.64.42.56. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php

Proof. The existence of such families was considered in the literature [KSS],
[EFF], and follows, e.g., from Theorem 3.1 in JEFF]. This lemma is simple enough,
though, for a proof to be reproduced here. To prove the lemma, let m- 5A21ogn]
and consider a random collection J of n subsets of { 1,--., m} which is constructed as
follows" For 1 _< x _< m and 1 _< i n, let Pr(x Si) (l/A). All the decisions on
whether x Si are made independently.
We claim that there is a selection of such a family for which the lemma holds.
The probability that for a given 1 _< x <_ m and given F0,..., FA J (i.e., Fi S,
for appropriately chosen indices), there holds

i8

1( i-
->4A"
1

Therefore, the probability that F0 c_ UFi is at most (1 (1/4A)) m. The number of

ways for choosing Fo,...,FA is (A / 1)(A_I ). Therefore if

( 1)- (A+I) <1,

then there is a selection of a family J which satisfies the lemma. Standard estimates
show that this holds when

m > 5A 2 log n.
To prove the theorem, fix a family J {F1,..., Fn} as in the lemma. Consider
vertex with label i whose neighbors’ labels are j,..., jd where d _< A. Since
d

there is a 1 _< x _< m with x e F\(U= Fj.). The color of this vertex is x. It is
easily verified that this is a proper m-coloring of G.
The same proof yields, more generally, the following corollary.
COROLLARY 4.1. Let G be a graph whose vertices are properly colored with k
colors and whose largest degree is A. It is possible to color G with 5A 2 log k colors in
one unit of time distributively.
By iterating the coloring given by the corollary log* n times, a 10A 2 log A-coloring
is obtained. To eliminate the log A term we need a result of the same type as Lemma
4.1, only in that range.
Downloaded 11/22/13 to 132.64.42.56. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php

200 NATHAN LINIAL

Proof. Use Example 3.2 in JEFF] with d- 2.

with 4A
[2
_
LEMMA 4.2. Let q be a prime power. Then, there is a collection J of qa subsets
of {1,..-, q2} such that if Fo,..., F[(q-1)/2l E g then Fo [.j(q-1)/] Fi.
Select q to be the smallest prime power with q _> 2A / 1. There is certainly one
+ 1 >_ q >_ 2A + 1. This construction transforms an O(A3)-coloring to an
O(A2)-coloring as in the proof of Theorem 4.1.
Theorem 4.2 now follows.
THEOREM 4.2. Let G be a labeled graph of order n with largest degree A. Then in
time O(log* n) it is possible to color G with O(A 2) colors in a distributive synchronous
algorithm. D
The previous proof is nonconstructive in that there is no known explicit construc-
tion as good as that which Lemma 4.1 guarantees. However, as Karloff pointed out
[K], the explicit geometric construction in Example 3.2 of JEFF] enables us, in the
same way, to reduce a k-coloring to an O((A 2 log 2 k) )-coloring in one timestep. (The
previous proof reduces a k-coloring to an O((A 2 log k))-coloring in a step.) The rest
of the proof remains unchanged, yielding the same results with only slightly worse
constants.
Proposition 3.4 of JEFF] sets a bound on the power of the present method, showing
that it does not enable one to color with fewer than (A2+2) colors. That proposition
shows that set systems of the type that would allow further reduction of the number of
colors do not exist. Other algorithms may still be capable of coloring with fewer colors.
It would be interesting to decide whether this quadratic bound can be improved when
time bounds rise from O(log* n) to polylog, for instance.
5. Some final remarks. It is well known now how to find a maximal indepen-
dent set in a graph by means of an NC algorithm ([KW], [ABI], ILl). The algorithm in
ILl can even be viewed as a randomized distributed algorithm. However, an algorithm
which is both deterministic and distributed still eludes us. In [GP] it is shown how
to find an MIS in time log*n for graphs of bounded degree. It is not clear what the
situation is for unbounded degrees. In particular, can it always be found in polyloga-
rithmic time in the present model? This, if true, would be a significant improvement
over the above-mentioned studies.
A standard trick (e.g., [L]) allows us to transform an efficient MIS algorithm to one
for (A + 1)-coloring: Take the cartesian product of G with KA+I. It is easily verified
that (A + 1)-colorings of G and MISs of G KA+I are in a natural 1:1 correspondence.
It is therefore particularly interesting to find out the best time complexity in terms
of n for finding a (A + 1)-coloring, and in particular whether polylogarithmic time
SUiCeS.
The fact that randomness does not help in coloring (Corollary 2.1) is thought-
provoking: Getting a deterministic polylog-time algorithm for MIS seems hard, though
simple randomized distributed algorithms are known. It is an intriguing problem to
classify distributed graph problems according to how much randomization can help
in solving them.
6. Acknowledgments. Comments recieved by .a number of colleagues helped
improve this paper, in a significant way. A comment by Noga Alon helped simplifying
the proof of Theorem 2.1. Howard Karloff’s comment on the proof of Theorem 4.1 is
recorded in the text, and a similar remark was made by Noga Alon as well. That ran-
domization does not help came up in discussions with Dror Zernik. Helpful comments
were also received from the referees. I am grateful to all of them.
 LOCALITY IN DISTRIBUTED GRAPH ALGORITHMS 201

REFERENCES
Downloaded 11/22/13 to 132.64.42.56. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php

[A] B. AWEBUCH, Private communication.

[ABI] N. ALON, L. BABAI, AND A. ITAI, A fast and simple randomized algorithm for the max-
imal independent set problem, J. Algorithms, 7 (1986), pp. 567-583.
[B] B. BOLLOBAS, Random Graphs, Academic Press, New York, 1J85.
[CV] R. COLE AND V. VISHKIN, Deterministic coin tossing and accelerating cascades: micro
and macro techniques for designing parallel algorithms, in Proc. 18th ACM Sympo-
sium on Theory of Computing, 1986, pp. 206-219.
JEFF] P. ERDSS, P. FRANKL AND Z. FOREDI, Families of finite sets in which no set is covered
by the union of r others, Israel J. Math., 51 (1985), pp. 79-89.
[GP] A. V. GOLDBERG AND S. A. PLOTKIN, Efficient parallel algorithms for (A + 1)-coloring
and maximal independent set problems, in Proc. 19th ACM Symposium on Theory
of Computing, 1987, pp. 315-324.
[JS] R. E. JOHNSON AND F. B. SCHNEIDER, Symmetry and similarity in distributed systems, in
Proc. 4th ACM Symposium on Principles of Distributed Computing, 1985, pp. 13-22.
[K] H. KARLOFF, Private communication.
[KSS] D. J. KLEITMAN, J. SHEARER AND D. STURTEVANT, Intersections of k-element sets, Com-
binatorica, 1 (1981), pp. 381-384.
[KW] R. M. KARP AND A. WIGDERSON, A fast parallel algorithm for the maximal independent
set problem, in Proc. 16th ACM Symposium on Theory of Computing, 1984, pp. 266-
272.
ILl M. LUBY, A simple parallel algorithm for the maximal independent set problem, in Proc.
17th ACM Symposium on Theory of Computing, 1985, pp. 1-10.
[LPS] A. LUBOTSKY, R. PHILLIPS AND P. SARNAK, Ramanujan graphs, Combinatorica, 8 (1988),
pp. 261-278.