Deciding whether a vertex in a graph is reachable from another
vertex has been studied intensively in complexity theory and is
well understood. For common types of graphs like directed graphs,
undirected graphs, dags or trees it takes a (possibly
nondeterministic) logspace machine to decide the reachability
problem, and ... more >>>

Following Dwork, Naor, and Sahai (30th STOC, 1998),
we consider concurrent execution of protocols in a
semi-synchronized network. Specifically, we assume that each party
holds a local clock such that a constant bound on the relative rates
of these clocks is a-priori known, and consider protocols that
employ ... more >>>

In parallel and distributed computing scheduling low level tasks
on the available hardware is a fundamental problem.
Traditionally, one has assumed that the set of tasks to be executed
is known beforehand.
Then the scheduling constraints are given by a precedence graph.
Nodes represent the elementary tasks ... more >>>