Re: Algebraic Topology and Distributed Computing

• Previous message: Michael N. Christoff: "Computer Science Theory Group"
• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]

Date: Thu, 15 Jan 2004 23:26:08 GMT

"Michael N. Christoff" <mchristoff@sympatico.caREMOVETHIS> wrote in
news:TkJCb.19101$aF2.2209102@news20.bellglobal.com:

> Algebraic toplogy (AT herein) seems to be a good way of formalizing
> protocols in distributed systems (DS herein) (such as decision
> problems like 'consensus'). I am interested in learning more, however
> AT is a huge field and I am only interested in learning the parts
> directly related to distributed computing. Can anyone suggest a book,
> that a) assumes no knowledge of algebraic toplogy b) assumes no more
> than undergraduate level math - ie: calculus, linear algebra, basic
> geometry, ability to do proofs, etc... c) focused on showing how AT
> can be utilized to solve DS problems and does not get into non-DS
> related aspects of AT (unless they are required background for
> understanding DS related AT topics).
>
> I have found many introductions on the net, but they seem to assume at
> least basic knowledge of topology, homotopy, and other topics I am not
> familiar with, so I think a full book dedicated to the subject sounds
> more feasible as a basis for learning AT for DS. But any links or
> online books you may know of will be of great help as well.
>
>
>
> l8r, Mike N. Christoff
>
>
>
>

I thought I'd give an extremely low detail explanation of how algebraic
topology can be to model asynchronous distributed protocols. I will
also note that apparently it requires very little general topology to
understand as it is almost entirely combinatorial in nature. In fact,
one only needs to know the AT described in the first chapter of
Munkres' book on algebraic topology to understand it (but not to
understand this overview which requires none). This is taken from a
response I gave on the theory-edge yahoo group (also posted on comp-sci-
theory). Note that this must be viewed with a fixed width font like
courier or courier new.

----- Original Message -----
From: vznuri
To: theory-edge@yahoogroups.com
Sent: Thursday, January 08, 2004 12:45 PM
Subject: [theory-edge] topology & its applications

-------------------------------
hi mike. did you say you were going to apply
topology to distributed or parallel processing?
while Ive no background in this area,
the areas you are studying are clearly very
abstract & I would be surprised if they have
major applications.
--------------------------------

There has already been major work done in the connection between DC
and AT. Many new lower bounds have been proven for classic DC
problems like k-set agreement and consensus. A quote by Frédéric
Tronel of the French National Institute for Reseasrch In Computer
Science and Control:

<quote>
... the problem of consensus (distributed agreement) plays a central
role in the theory of distributed computing. Since it has been proven
to be unsolvable by deterministic algorithms in a purely asynchronous
system, it was a real challenge to explicitly determine the border
that exists between solvable and unsolvable problems in asynchronous
systems. This problem remained unsolved till the publication of a
seminal paper by Maurice Herlihy and Nir Shavit. In fact at the
reading of this paper, one can understand that all the previous
approaches where prone to fail. Indeed, all of them kept on using the
traditional way of modelling an asynchronous system, namely by the
mean of a graph of local states. This technic can be successful, when
there is only one crash in the system. However, it does not scale
well, when the number of crashes increases. On the contrary, Herlihy
and Shavit have chosen to model the evolution of the system through
the use of high dimensional geometrical objects.
</quote>

The area of distributed computing I'm interested uses asynchronous
message passing. This is the type you want to look at if you're
interested in technologies like peer to peer networking (which I am).

The idea is very combinatorial. You start with a set of nodes, each
with an initial value from some finite set. For concreteness, imagine
you have three nodes arranged in a triangle (vertices = nodes, edges =
network connections). Let the initial value set = {0,1}. Then this can
be represented as

a ----- b
\ /
  \ /
   \ /
    c

where a,b,c are tuples (node_id, initial_value). The number of possible
initial states for the system are then 2^3 since we have 3 nodes which
can each be initialized with either a 0 or a 1. This gives us 2^3
triangles.
Now here is the tricky part. Connect the triangles together by matching
edges whose vertices a,b are equal. For example, take the three
triangles below.

A) 001
(n1, 0) ------------ (n2,0)
  \ /
    \ /
       \ /
         (n3,1)

B) 101
(n1, 1) ------------ (n2,0)
  \ /
     \ /
       \ /
         (n3,1)

C) 000
(n1, 0) ------------ (n2,0)
  \ /
    \ /
      \ /
        (n3,0)

This becomes:

         (n3,0)
      / \
    / C \
/ \
(n1, 0) ------------ (n2,0)
  \ / \
    \ A / B \
      \ / \
        (n3,1) ----------- (n1,1)

Now if we continue this process we will have generated a closed
geometric figure. This one in particular looks like like two
tetrahedrons connected at their bases. Or one could think of it as an
approximation of a sphere using 8 triangles. This is called the input
complex at step 0.

As the protocol evolves in time, each face (triangle) of the object
subdivides further to represent all possible states the nodes could be
at step 2. So for instance, the triangle C will subdivide into a
subcomplex representing all possible states of the nodes after
starting with the inital inputs all 0. The system is fault tolerant,
as some of the structure of the subcomplex also represents possible
states of the nodes if one or more of the nodes have failed.

The set of structures that develop as the protocol progresses are
called protocol complexes.

In theoretical computer science we have the decsion problem, so in DC
we have decision tasks. A decision task is a finite process after
which each node makes a decision on what its output should be. For
example, in the binary consensus problem each node is initially given
a number in {0,1}.
After a finite number of steps, all nodes must output identical values
from {0,1}. From a specification like this, we can define the output
complex of the problem. For binary consensus with three nodes, the
only acceptable output complex is shown below:

(n1, 1) ------------ (n2,1)
  \ /
    \ /
      \ /
        (n3,1)

(n1, 0) ------------ (n2,0)
  \ /
    \ /
      \ /
        (n3,0)

In other words, the final state of all nodes must either be all 1s or
all 0s.

A 'simplicial map' is used to map the protocol complex to the output
complex. Without getting into the machinery of it (which I'm still
not very clear on), the idea is to determine if the protocol complex
can evolve to the required output complex. This is done by trying to
find any topological obstructions (holes) to the simplicial map. If
there are, then the protocol cannot work, otherwise it can.

That is a bare bare bones description of the idea and I may have
misexplained parts.

l8r, Mike N. Christoff

• Previous message: Michael N. Christoff: "Computer Science Theory Group"
• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]