0.25
0.5
0.75
1.25
1.5
1.75
2
Algebraic Topology and Concurrency
Published on Oct 22, 20152185 Views
Algebraic topology, which started out as an approach to problems in physics, then developed as a curiosity driven area for almost a century. The last 15-20 years, a number of new applications have had
Related categories
Chapter list
Algebraic topology and concurrency00:00
Algebraic topology as an applied subject00:18
And then almost 100 years passed01:11
ATMCS01:33
New applications. Distributed Computing02:50
Concurrency and algebraic topology03:27
Data analysis, image analysis, computer vision. Persistent homology03:57
Common structure of these new applications04:23
From concurrency to geometry/topology05:17
Models of Non-parallel programs06:49
Parallel programs - several models07:27
Parallel programs = Many copies of sequential programs?07:55
The Swiss flag - two dining philosophers08:55
PV-programs - controlling concurrency through locks10:37
Geometrically - 111:53
Geometrically - 212:27
An execution is a directed path14:05
Equivalence of executions14:18
Topology - the mathematics of deformation14:35
Examples in the plane15:42
In 3d, homotopic ≠ directed homotopic16:32
A few words about directed topology18:32
Examples of d-spaces19:44
Equivalence of executions - dihomotopy21:11
Equivalence of executions21:44
Raussens algorithm22:28
Directed topology23:56
Serializability25:31
Deadlock - no time-directed paths leave the point26:57
Serializability28:26
Serializability. κ = 129:13
Serializability - a cut-off theorem29:33
In general pairwise serializability is not enough. Even when κ = 130:10
T = PaVa, T331:06
Tn31:52
The symmetric case T232:39
T2 serializability - 132:48
T2 serializability - 233:12
How complicated does Tn get?33:55
Serializability for κ > 135:14
Serializable and connectivity37:37
γ = T1.T2. . . . .Tn ' T1.T2. . . .Ti − 1.Ti + 1.Ti . . . .Tn37:42
Obstructions to serializability37:43
Why is the theorem true - sketch of proof - 139:47
Why is the theorem true - sketch of proof - 239:49
Realizing M - is M sharp?39:50
A choice point for n = M − 242:24
Cut-off43:01
A cut-off theorem for deadlocks43:59
More to do44:43
Commercial46:09