We propose a new hybrid fault model for clock synchronization and
single-round (approximate) agreement in synchronous distributed
systems (This research has been conducted in our SynUTC-project,
see http://www.auto.tuwien.ac.at/Projects/SynUTC/, supported by the
Austrian START programme Y41-MAT. Part of it has been presented at
DSN'01.) which accurately captures both node and link faults.
Unlike conventional ``global'' fault models, which rest
upon the total number of faulty nodes in the system, it solely relies
upon the number of faults in any two non-faulty nodes'
``perceptions'' ---conveyed by the messages from all other nodes---
of the system.  This way, arbitrary node and communication faults,
including receiver-caused omission and time/value faults, can be
modeled properly. We show that both the consistent broadcast
primitive of Srikanth & Toueg and our Fault-Tolerant Interval
convergence function (emulating Lundelius & Lynch's Fault-Tolerant
Midpoint algorithm as well) can be analyzed under this model.  As far
as link faults are concerned, our analysis reveals that both
algorithms require 4\ia+2\is+2\io+1 nodes for tolerating at most
\ia, \is, and \io asymmetric, symmetric, and omission faults at
each receiving node.

Keywords: Fault-tolerant distributed systems, fault models,
link failures, consistent broadcasting, convergence functions,
interval-based clock synchronization.