  Whereas distributed computing research has been very successful in exploring
the solvability/impossibility border of distributed computing problems like
consensus in representative classes of computing models with respect to model
parameters like failure bounds, this is not the case for characterizing
necessary and sufficient communication requirements. In this paper, we
introduce network abstractions as a novel approach for modeling communication
requirements in asynchronous distributed systems. A network abstraction of a
run is a sequence of directed graphs on the set of processes, where the $i$-th
graph defines the potential message chains that may arise in the $i$-th portion
of the run. Formally, it is defined via associating (potential) message sending
times with the corresponding message receiving times in a message schedule.
Network abstractions allow to reason about the future causal cones that might
arise in a run, hence also facilitate reasoning about liveness properties, and
are inherently compatible with temporal epistemic reasoning frameworks. We
demonstrate the utility of our approach by providing necessary and sufficient
network abstractions for solving the canonical firing rebels with relay (FRR)
problem, and variants thereof, in asynchronous systems with up to $f$ byzantine
processes. FRR is not only a basic primitive in clock synchronization and
consensus algorithms, but also integrates several distributed computing
problems, namely triggering events, agreement and even stabilizing agreement,
in a single problem instance.
