  This paper presents a novel leaderless protocol (FPC-BI: Fast Probabilistic
Consensus within Byzantine Infrastructures) with a low communicational
complexity and which allows a set of nodes to come to a consensus on a value of
a single bit. The paper makes the assumption that part of the nodes are
Byzantine, and are thus controlled by an adversary who intends to either delay
the consensus, or break it (this defines that at least a couple of honest nodes
come to different conclusions). We prove that, nevertheless, the protocol works
with high probability when its parameters are suitably chosen. Along this the
paper also provides explicit estimates on the probability that the protocol
finalizes in the consensus state in a given time. This protocol could be
applied to reaching consensus in decentralized cryptocurrency systems. A
special feature of it is that it makes use of a sequence of random numbers
which are either provided by a trusted source or generated by the nodes
themselves using some decentralized random number generating protocol. This
increases the overall trustworthiness of the infrastructure. A core
contribution of the paper is that it uses a very weak consensus to obtain a
strong consensus on the value of a bit, and which can relate to the validity of
a transaction.
