Local Color
-----------
You have been asked to write a program that will run as
a local algorithm in a network of processors and improve
a coloring of the network graph.
A network graph is an undirected graph. The vertices
are called nodes and the edges are called connections.
Two nodes sharing a connection are neighbors. The
number of connections attached to a node is the degree
of the node, and the degree of the network, denoted by
D, is the maximum degree of any node. If a node has
degree d, we identify its connections by integers in the
range 0, ..., d-1. The number of nodes in the network
is N, and we identify nodes by integers in the range
0, ..., N-1.
A coloring is an assignment of a color to each node
such that NO neighbors have the same color. If there
are C colors, we represent the colors by integers in
the range 0, ..., C-1.
The problem is that given a coloring with C > D+1
colors, improve the coloring to one with at most D+1
colors, using a local distributed algorithm.
A local distributed algorithm is a deterministic program
code that runs at each node and executes in K cycles.
At the beginning of each cycle but the first each node
receives a message from each of its neighbors. The node
then computes and for each cycle but the last, outputs a
message for each of its neighbors. At the beginning of
the first cycle each node receives a single input
message and at the end of the last cycle each node
outputs a single output message.
Your program executes one cycle at one node, and is
invoked by the judge's `monitor' program K*N times to
perform the local distributed computation and produce an
answer.
Importantly, in our problem K is set equal to C, the
number of original colors.
Messages are single lines of ASCII text whose maximum
length is 1,000 characters. Each node has a memory that
is represented as a message from the node to itself,
i.e., is output by the node at the end of a cycle and
input by the node at the beginning of its next cycle.
Your program is called by a monitor program in order
to execute each cycle of each node. The monitor pro-
gram, which is named `localcolor_network', is provided
by the judge. Your program is named `localcolor'.
You can invoke these programs by the command
localcolor_network localcolor
Input to Your Program
----- -- ---- -------
For each cycle of each node, first a line containing the
following information:
N K node_id node_degree cycle_number
where N is the total number of nodes, K the total number
of cycles, the N nodes have node_id's in the range 0,
..., N-1, and the K cycles are number 0, ..., K-1.
Then for the first cycle (cycle 0) a single line.
C initial_node_color
where C is the initial number of node colors and the
node is given an initial color in the range 0, ..., C-1.
For cycles other than the first, the above first input
line is followed by lines containing messages output by
the previous cycle. The first of these is a line that
contains the contents of the memory of the node at the
end of the previous cycle (the message from the node to
itself). This line is followed by a line for each con-
nection containing the message from the connection's
neighbor. These connection message lines are in order
of the connection number relative to the node, from 0
through node_degree-1.
You define the format of all message lines. Message
lines may not be longer than 1,000 characters and must
contain only printable ASCII characters and single
spaces (they need to be printable to debug, and they
are not permitted to contain form feeds, line feeds,
tabs, or any control character other than single
space).
Input ends with an end of file, at which point your
program should terminate (as there are no more test
cases).
Output from Your Program
------ ---- ---- -------
The output from your program for all cycles but the last
is a sequence of message lines. First, the line con-
taining the contents of the node's memory (the message
from the node to itself). Then for each connection a
line containing the message output by the cycle for
the connection. These lines are in order of the connec-
tion number, from 0 through node_degree-1. Lastly one
line containing just `END' (used to detect bugs).
For the last cycle of an algorithm execution output only
one line containing just an integer in the range 0, ...,
D that is the color of the node after the algorithm has
completed, followed by one line containing just `END'.
The monitor program will check that two neighbors do not
have the same color at this point, and that all colors
are in the range 0,..., D. Your algorithm will be
declared to be successful for the test case if this is
so.
Input to the Monitor
----- -- --- -------
For each test case, first a line containing just the
test case name. Then a second line containing
N D C SEED
where N is the number of nodes, D the maximum node
degree, C is the number of initial colors, and SEED is a
9-digit unsigned integer that is the seed of a pseudo-
random number generator used by the monitor to generate
the graph.
2 <= D <= 20
D + 1 <= N <= 1,000
D + 1 < C <= 100
Input ends with an end of file.
Output from the Monitor
------ ---- --- -------
For each test case, first a copy of the test case input
lines, and then a line containing just `OK' if the
solution is a coloring with D+1 colors, or a line
containing
FAILED node n1 and neighbor n2 both colored c
if neighboring nodes n1 and n2 were both colored c,
or a line containing
FAILED node n colored c
if node n was colored with c < 0 or c > D. If there was
some error in message format, the output will be
FAILED ...
where ... describes the error.
Debugging
---------
You can add debugging arguments to the program command:
localcolor_network localcolor debug_argument ...
If you do this your program will be invoked by the
monitor using the command
localcolor debug_argument ...
and the monitor will output the input and output for
each node and cycle in addition to the usual output
of the monitor. The input/output for a node and cycle
is surrounded by lines containing just `*****' and the
input is separated from the output by a line containing
just `-----'. You can put debugging information in your
messages, and used the debug arguments to tune this
information.
Sample Input
------ -----
-- SAMPLE 1 --
10 3 20 783927645
-- SAMPLE 2 --
20 10 50 259140687
Sample Output
------ ------
-- SAMPLE 1 --
OK
-- SAMPLE 2 --
OK
Reference
---------
For a discussion of local distributed algorithms, more
examples, and impossibility results see
A Survey of Local Algorithms, Jukka Suomela,
ACM Computing Surveys, Vol. 45, No. 2, 2013.
File: localcolor.txt
Author: Bob Walton <walton@seas.harvard.edu>
Date: Mon Oct 14 02:53:43 EDT 2013
The authors have placed this file in the public domain;
they make no warranty and accept no liability for this
file.
RCS Info (may not be true date or author):
$Author: walton $
$Date: 2013/10/14 07:10:46 $
$RCSfile: localcolor.txt,v $
$Revision: 1.9 $