| dmx_dawg@hotmail.com 2005-11-25, 5:47 pm |
| [Responding to David C. DiNucci's post from October 1, 2005]
Hi David.
I hope to follow up in full on your last message shortly. There's a
lot to read (a good thing)! I will try to discuss a couple things in
more depth
The usefullness of modelling global states - how they relate to:
- adversaries
- levels of network awareness: does each process know how many other
processors are collaborating? Is the number of processors fixed or
varying? Is the network fixed or dynamic?
Do the processors have any 'sense' of direction' in the network?
Distributed knowledge
- ditopology, dihomology and dihomotopy
The last items are interesting when thinking of the relationship
between relativity (in the basic sense that 'everything is relative')
and distributed computing. Ditopology is a type of topology where the
spaces are built from locally partially ordered sets of process
executions. The space ends up looking like a manifold, where each
process has a neighbourhood about it which represents its own 'point of
view' of the system. The system as a whole is generally quite
different. The canonical example for the idea behind manifolds is the
sphere. Every point on the sphere has a neighbourhood that is locally
'flat' (technically, a neighbourhood homeomorphic to the open disc),
however the structure as a whole cannot be mapped onto a 'flat' surface
like a disc.
In terms of applications, what I have been focusing on recently is
protocol upper and lower bounds (mainly wrt message complexity) that
take into account the physical topology of the network. For me, I can
see a lot of possible realworld use for this - even though I'm tackling
it a very theoretical level. Hopefully there is a smooth bridge
between the physical network, the local states of the processors and
the global state of the system.
-mike
|