This is a presentation of the paper The Topology of Local Computing in Networks. My name is Pierre Frenure, I am from CNRS and Université de Paris, and this is a joint

work with Ami Paz from Universitat Bien. The paper is about distributed computing. So in distributed computing we have a set of autonomous processes, P1 to Pn, and these processes are exchanging information via some communication medium.

They are aiming at solving tasks. So what is a task? In a task, every process Pi starts with some input value Xi, and it must eventually output some value Yi. And there are of course some input-output relation specifying the task.

So an output y, I mean a vector of output y, is correct with respect to some input vector x, if and only if the vector y satisfies the specification of the task with respect to the input vector x.

In fact, instead of talking about vectors, it is much more convenient to talk about simplices and complexes. And in fact, in this paper we will use the framework introduced by Erle and Chavit and Zaks and Zaro Oblu at the turn of the century, which is viewing distributed computing through

the lens of algebraic topology. The result by these authors enabled them to receive the Godel Prize in 2004. So just let me remind you that a simplicial complex, K, is simply a collection of non-empty subsets of a finite set V, and the main property is that these subsets must be downward closed

under inclusion. So V is denoting the set of vertices, and every subset of K is called a simplex. So in this figure, for instance, you can see the vertices as black dots, edges,

and you can see also full triangles, and even tetrahedron. So now tasks can be formalized in this context as follows. So we can define an input complex, which is form of the following vertices. Each vertex is a pair, i, xi, where i is the index of the process, pi, and xi is

the input of this process. And simplices are just sets of legal input configurations. So for instance, on the figure on the right, you can see an input complex in which there are three processes, the white one, the gray one, and the black one.

And the processes can receive input 0 or 1, and there are no constraints on the collection of inputs, so you can have all possible combination of zeros and one. And so the input complex in this case is a one of the three, the two-dimensional three. Now the output complex, again, it's the vertex set is form of pairs i, yi, where i is the

index of the process, and yi is some output value. And the simplices are the set of legal output configuration. Again, on the figure on the right, you can see at the bottom an output complex in

which there are only two legal output configurations, the set of all ones and the set of all zeros. This is, for instance, the case in consensus. And the specification of the task is done using a carrier map that specify for each

input simplex the collection of output complex that are legal with respect to this input. So for instance, in the case of consensus, if you start, if the system starts with all processes with input one, they are bounded to all output one. But if the system start with some processes input one and some other processes input zero,

then they can output either all ones or all zeros as long as they are legal. So computation can also be modeled in the framework of topology by defining protocol complex.

So protocol complexes, they are indexed by the time t where the notion of time may depend on the model. So at time zero, the protocol complex is simply the input complex. And at time t, a vertex of the protocol complex Pt is a pair i Si, where i is the index of the process, and Si is a state of the process Pi at time t.

So a simplex of the protocol complex Pt is just a set of legal global state. So it's the collection of mutually compatible pairs i Si. Finally, algorithm can also be modeled in the framework of topology by noticing that

an algorithm that outputs some value at time t induce a mapping from the protocol complex to the output complex. So specifically, if Pi in state Si at time t outputs some value yi, then we can define a mapping, delta, where the image of delta of i Si is the pair i yi, which is a vertex

in the output complex. Note that this mapping is name preserving in the sense that of course a process doesn't change name when it outputs a value. This figure represents all the aspects of descriptive computing in a single diagram.

So on the left, top left, we have the input complex. On the bottom right, we have the output complex. We have the specification of the task delta. Now on the top right, we have the protocol complex.

And so in fact, this protocol complex can be viewed as a topological transformation of the input complex, whose nature depends on the computational model at hand. And finally, we have the algorithm, which maps vertices from the protocol complex to vertices of the output complex.

And now, one of the main results of Yali and Shavit is to characterize what does it mean to solve a task. So a task i o delta is solvable in time t, if and only if there exists a name preserving simplicial map delta. So the map delta, which goes from p t to o, must be simplicial, must preserve the simplices

of the protocol complex. Every simplex of the protocol complex must be mapped to a simplex of the output complex. And of course, the mapping should agree with delta. Here I am avoiding some technical details.

So now we have a global figure or global picture of descriptive computing through the hands of algebraic topology. What is the outcome of this formalism? Well, it's huge. Actually, a plethora of positive and negative results were obtained during the last two

decades using this framework. And I am referring here to the book of early Costlov and Rajbom, which presents a survey of all kinds of large, very many results that can be obtained using topology in various frameworks.

Now all these results, they apply to all-to-all communication media only. So to share memory or to message passing. And one question that was addressed very recently is what about network computing? Can we apply topology also to network computing?

So for instance, let us consider one of the main model of network computing, which is a so-called local model. So now it's not an all-to-all communication. The communication occurs only along the edges of the graph. So we have a network, which is modeled as an n-node graph, G. And every node Pi is given some ID, which is usually in a polynomial range, one between

one and n to the c, for some constant c greater than one. And it's a failure-free model. So no crashes, no failures. And it's a very, it's a synchronous model. So every, the computation perform in lock steps.

So there is a notion of round, and all the processes start at the same time. And at every round, every node sends a message to each of its neighbors, receives the messages that were sent by its neighbors, and performs some individual computation. And here, it's important to notice that the messages are unbounded.

So actually, it's a full information protocol, which enables the framework of Ali and Shabit to apply, to apply. Last year, Armando Castaneda, myself, Ami Paz, Sadio Rajbo, Mathieu Roy, and Corentin Travert, we studied the topological approach for the local model.

So, we consider the same framework as Ali and Shabit. And we consider complexes, where the vertices are of the form, I, I, V, I, V, I. Now it's a triplet. So I, again, is the index, or name of a process, so it's between 1 and n.

I, D, I is the ID which is given to this process, so it's again in the polynomial range. And V, I, it depends on the context, can be an input value, an output value, or simply the view of a process in the protocol complex. So what is the view? It's just a ball of reduced t in the network.

Now, it's important to note that the protocol complex depends on the structure of the network, because, of course, the balls depends, the structure of the balls depends on the structure of the graph, and therefore, what the information that can be acquired by a process in theorem

depends a lot on the structure of the network, G. And one of the main contributions of Castaneda et al. was to identify a new form of topological deformation that they call scissor cuts. So for instance, on this figure, I just represent the case of consensus,

we have the input complex, the output complex, and you see in the middle two types of scissor cuts that are depending on the structure of the network. And one of the main contributions of their paper is to establish a correspondence between the structure of the network G and the homology of the protocol complex PT.

And this result enables Castaneda et al. to, using this global approach, to derive a certain number of results, essentially lower bound, for various problems, and typically agreement problems.

So these problems are like consensus, so everybody must agree on the same value, k set agreement, in which the processes must agree in a set of at most k values, approximate consensus, et cetera. Now, the crucial point here is that all these tasks, the specifications of these tasks,

are actually independent of the network structure. So a natural question, and that was the motivation of this paper now, is what about tasks that depend on the network structure? Most of the tasks that actually are to be solved in the context of network computing

refer to the network structure. So they can be coloring, maximal independent set, maximal matching, minimum weight, spanning tree, et cetera. All these tasks are specified, and the output depends on the structure of the network. So what is the difference between our approach and the approach of Castaneda et al.?

Well, our approach is entirely local. So let's consider, for instance, the class GD of the regular graph with the grid D. So in our approach, which is local, the simplices are not composed of n vertices,

I mean the facets are not composed of n vertices, but on simply D plus 1 vertices. A node P0 and its neighbors P1, Pd. So the vertices of the complexes that we are considering are of the form triplets, I, I, D, I, V, I, but the index I is not in 1n, but simply in 0d.

Also, the IDs, as we will see, the IDs are not in a polynomial range, which depend on the number of processes, but they are in a finite set of processes whose range depends only on the degree

and not on the number of nodes. And again, Vi is, of course, some input-output value or views, depending whether we consider the input complex, the output complex, or the protocol complex. For instance, let us consider maximum independent set problem in the ring. So let's assume here we have the ring, and let's assume that the nodes have a consistent notion of left and right,

and I will, instead of using P0, P1, P2, I will instead use P0 for the center node, P minus 1 for its left neighbors, and P1 for its right neighbors. So the left neighbors will be black, the center node will be white,

and the right neighbor will be blue. So, for instance, in MIS, here is a formulation of MIS in this context. So if the center node is in the MIS, the label is 1, then none of its neighbors must be in the MIS. Both of them should be 0. Instead, if the center node, the right node, is 0, is not in the MIS,

then its neighbors may or may not be in the MIS, as long as at least one of its neighbors is in the MIS. So this is the resulting local complex corresponding to MIS. Note that the triangle 0, 0, 0, for instance, is not a facet,

as well as a facet in which the white node is 1, and some of the neighbors, blue or black, is 1, is also not a facet of the local complex of MIS. We can play the same thing for three-coloring the ring.

So again, we assume that we have the ring with a consistent notion of left and right, and three-coloring, we want to proper color the nodes with colors in 1, 2, or 3. So this figure displays the local complex of three-coloring. Again, we have, let's say, for instance, on the left, on the left square,

we have the center node which is colored 1, so all its neighbors may have colors 2 or 3, as long as they have no color 1 in it. Same thing for the center square, the center node is colored 3, so its neighbors can be colored 1 or 2, but definitely not 3.

Now we can ask, is there a way to do some reduction from three-coloring to MIS in the ring? Let's say, for instance, is there a zero-round algorithm? The processes start with a three-coloring, and can they, without communication, output some value MIS 0 or 1,

representing 0 if they are not in the MIS, 1 if they are in the MIS. So this corresponds to the question, is there a mapping from the input complex, which is the complex of coloring, of three-coloring,

to the output complex, which is the complex of MIS. And this mapping must not only be name-preserving as before, but it must be name-independent, in the sense that P0, P1, P-1, there are notions that are not available to the processes themselves,

they are just in the model. So it should be a mapping, which is name-independent and name-preserving. We can ask the same question about the existence of a one-round algorithm. So this is the protocol complex after one round. So actually it's composed of three disconnected components,

representing the compatible views of the nodes after one round. And again, we can show, it's not as easy to show as before, that there is no simply shall name-independent, name-preserving mapping,

from this protocol complex P1 to the output complex of MIS. After two rounds, can we do? Aha! It happens that after two rounds, the protocol complex consists of 12 disconnected components, and there is indeed a mapping from this protocol complex

to the output complex of MIS. It's a little bit bizarre, because each component looks the same as they look in the protocol complex after one round, but remember that the mapping should be name-independent and name-preserving. And after two rounds, we have more flexibility for the mapping,

and actually we can show that this mapping exists, and there is in fact indeed a trivial algorithm to do reduction from three-coloring to MIS in two rounds. So what is our general framework? We are not working, of course, only on coloring and MIS. We are working on so-called locally checkable labeling.

So what is a locally checkable labeling? So in this labeling, every node is given a label taken from a finite set L. And there is a local specification S for a labeling to be correct or to be legal or not. So for instance, for coloring, if you take k-coloring,

the labels are values 1, 2, up to k, and a labeling is correct if and only if for every two adjacent nodes, they have two different labels. Same thing for MIS. The labels are 0 or 1. If you are labeled 1, all of your neighbors must be labeled 0,

because it's independent set. And if you are labeled, if a node is labeled 0, then at least one of its neighbors should be labeled 1, because we want maximal independent set. And what is an LCL task? The input is specified by some LCL, l-in, s-in, and the output is specified also by some LCL, l-out, s-out.

And there are also some potential input-output relation, like in least coloring. And the objective is starting from some input labeling, from the LCL, l-in, s-in, is to compute some output labeling corresponding to a legal labeling corresponding to l-out, s-out.

So that's a general framework. At this point, I just mentioned discussion without IDs. How do we deal with IDs? Well, we are essentially using the same technique which has now unstuck my ears, and the main ingredient is RAM-CTOR-M.

And in RAM-CTOR-M, I just want here to point out that, of course, there is a RAM-CTO value, which depends on various parameters that I will not discuss, and this R will appear in the next slide. This RAM-CTO value is what enables us

to discuss about constant number of IDs instead of discussing about the number of IDs that depends on the number of processes. So what is our main result? It's a constant reformulation of Theorem, Alla, Early and Chavit. So on the left-hand side of this slide,

you have the diagram corresponding to the global approach that was used by Castaneda et al. last year. So we have some input complex whose size depends on the number of processes, little n, and also on the number of IDs, capital N, where capital N is typically polynomial

in the size of the network. Same thing for the output complex, which depends on the number of nodes and the number of IDs and of the protocol complex. And we have this typical triangle, which is the Early and Chavit diagram. In this paper, in our local approach, the tasks are defined intimately of the IDs.

They are defined only as an input complex which depends only on d, that's the bottom horizontal line of the height diagram. So we have just a mapping, a carrier map from the input complex to the output complex that whose size depends only on the degree of the network.

Then, when we perform computation, we perform computation with IDs, so that's the height line of the diagram. But the input complex and the protocol complex depends on the IDs, but the number of IDs is bounded, is finite from 1 to r,

where r does not depend on the size of the network, but depends only on the time, number of rounds of the computation, and on the degree of the network. And now we have again a commutative diagram that we can resume in the following theorem,

which is for every LCL task on a graph of maximum degree d, and for every t, there exists some r, such that the task t is solvable in the local model, if and only if there is a simplicial map from the protocol complex whose size depends only on the time t,

the degree d, and the constant r, to the output complex that, of course, agree with the specification of the task. But what is crucial here is that all the complexes are of constant size, as opposed to what,

if we follow directly blindly, the early Shavit approach, in which case the size of the complexes depends on the size of the nodes. As an application of our main theorem, we reproved the famous result by Lignal, stating that essentially 3-coloring the n-node ring

requires log-star-n rounds. What we showed is that reduction from c-coloring to 3-coloring c-n requires omega of log-star-c rounds. And the proof goes as follows. So let's assume that we have a t-round algorithm for k-coloring. So this algorithm induced a simplicial map, delta,

from PTR to OK. Now let's... We can construct a functor that has the following properties. So every... The protocol complex is mapped to some other complex, phi of PTR. The output complex for k-coloring

is mapped to some complex phi of OK. Since it's a functor of phi, the mapping delta, the simplicial map delta is mapped to a simplicial map phi of delta. And this functor phi has a crucial property. Two, actually, crucial properties. First, the image of the output complex for k-coloring

is actually included in the output complex for 2 to the 2 to the k-coloring. And also, there is... We can show that there exists a simplicial map f from the protocol complex after t-1 round to the image of the protocol complex after t rounds by phi.

Therefore, by combining f and phi of delta, we obtain a simplicial map delta prime from the protocol complex after t-1 round to the protocol complex O of 2 to the 2 to the k. Which means that if there exists a t-round algorithm for k-coloring,

then there exists a t-1 algorithm for 2 to the 2 to the 2 to the k-coloring. If we iterate these things, we obtain the corollary. So, as a conclusion, there are two complementary approaches of distributed network computing through the lens of algebraic topology.

One is the global approach that was introduced last year by Ksenedar et al. and which is well suited to study tasks with specification or global, like consensus, k-set agreement, etc. And one local, which is done in this paper, which seems to be very well suited to study tasks with specification are purely local, like coloring, MIS, and LCL tasks in general.