  Reliable broadcast is a fundamental primitive, widely used as a building
block for data replication in distributed systems. Informally, it ensures that
system members deliver the same values, even in the presence of equivocating
Byzantine participants. Classical broadcast protocols are based on centralized
(globally known) trust assumptions defined via sets of participants (quorums)
that are likely not to fail in system executions. In this paper, we consider
the reliable broadcast abstraction in decentralized trust settings, where every
system participant chooses its quorums locally. We introduce a class of relaxed
reliable broadcast abstractions that perfectly match these settings. We then
describe a broadcast protocol that achieves optimal consistency, measured as
the maximal number of different values from the same source that the system
members may deliver. In particular, we establish how this optimal consistency
is related to parameters of a graph representation of decentralized trust
assumptions.
