GIT-CERCS-04-10
Subramanian Lakshmanan, Deepak J. Manohar, Mustaque Ahamad, H. Vekateswaran,
Collective Endorsement and the Dissemination Problem in Malicious Environments
We consider the problem of disseminating an update known to a set
of servers to other servers in the system via a gossip protocol.
Some of the servers can exhibit malicious behavior. We require
that only the updates introduced by authorized clients are
accepted by non-malicious servers. Spurious updates, in particular
those generated by compromised nodes, are not accepted by
non-malicious servers. We take the approach of collective
endorsement where each server endorses an accepted update by
computing a list of message authentication codes with symmetric
keys allocated to it. We use a novel key allocation scheme that
allocates a set of symmetric keys to each participating server to
minimize the total number of keys.
Our protocol is designed to minimize update diffusion time. In
the absence of faulty nodes, its diffusion time is O(log n),
which is the best possible time achieved when nodes only suffer
from benign faults. If the actual number of Byzantine faults
experienced during an update's dissemination is f, the diffusion
time increases to O(log n + f). This is better than the latency
of previously known protocols that take O(log n + b) time, where b
is the assumed threshold that defines the maximum number of
malicious servers that can be tolerated rather than f, the actual
number of failures. The buffer requirements and message sizes are
higher in our protocol than other known protocols and thus it
trades off memory and bandwidth resources to improve latency.