This paper presents two Byzantine fault-tolerant state machine replication (BFT) algorithms that are minimal in several senses. First, they require only 2 f +1 replicas, instead of the usual 3 f +1. Second, the trusted service in which this reduction of replicas is based is arguably minimal: it provides an interface with a single function and is composed only by a counter and a signature generation primitive. Third, in nice executions the two algorithms run in the minimum number of communication steps for non-speculative and speculative algorithms, respectively 4 and 3 steps. The paper is also the first to present BFT algorithms with 2 f +1 replicas that require a trusted service implementable using commercial off-the-shelf trusted hardware: this service can be implemented with the Trusted Platform Module currently available as a chip in the mainboard of many commodity PCs

In this talk, the problem of designing distributed algorithms is presented and discussed its main challenges. Setting the task of having a distributed algorithm in a multi-agent system to achieve consensus of a variable of interest, we present a discrete-time reputation-based consensus algorithm that eliminates attacked agents' information for the case of a static topology and synchronous communication. Using only local information, agents can compute a reputation for each of its neighbors and assess the relative quality of the received data prior to the update. We show that, for each time step, the proposed method has quadratic complexity on the number of neighbors of each agent. Finally, we illustrate our method with several examples, portraying some attacking schemes successfully dealt by our method that succeed against the state-of-the-art.