A central problem in the field of distributed systems is the distributed consensus. In a consensus problem, the set of all processes is required to agree on a common value, out of one of the values initially held by one of the processes. If all processes are fault-tolerant and work without delays, the consensus problem can easily be solved by using a leader selection protocol. In the case of presence of faulty processes, the consensus problem becomes much harder. The problem of distributed consensus has extensively been studied in the last decades. The known protocols are usually developed with the goal of maximizing the number of allowed adversaries (faulty processors).
It is well known that any protocol that solves distributed consensus with g honest participants can tolerate at most f < g/2 faulty participants. In other words, the honest participants need a two-third majority and a simple majority (g>f) is not enough. The reason for this are the adversary's abilities to a) control all message delays in the network and b) to send different/conflicting messages to different participants. In our first line of work, we argue that these assumptions are too pessimistic for internet-scale applications. Participipants may have hidden trust relations or connections that can not controlled or even observed by a third party. For example, an honest participant can simply join with several unrelated IP adresses to confuse the adversary. Thus, the adversary can not control the flow of messages as tightly as required by classical lower bound arguments. Based on these observations, we develped a model to formalize these "hidden links" between participants. In our first contribution , we focussed on the case that each honest participant joins a system with k unrelated identities. We could show that maximum number of faulty players goes from g/2-1 to g(1-1/2^k) and present a protocol that almost matches this bound. Thus, for high values of k, the bound shift closer and closer to a simple majority.
Although, we could impove the number faulty participants with our additional assumptions, our protocols or, more generally, similar protocols that aim for a high number of faulty processes lead to a running time which is not acceptable for highly scalable systems. For instance, it is known that previously considered protocols for distributed consensus require on average a linear amount of time for every process, if the maximum number of possible faulty processes is allowed. Furthermore, previously presented protocols for distributed consensus usually are not self-stabilizing. Our goal is to determine up to which number of faulty processes an efficient protocol (a protocol with a maximum of polylogarithmic cost for each participant) is possible. Additionally, we aim to develop self-stabilizing protocols for the problem of distributed transactions, which are supposed to work correctly despite the presence of adversaries.
In  we presented a simple randomized algorithm that, with high probability, just needs O(log(m)loglog(n)+log(n)) time and work per process to arrive at an almost stable consensus for any set of m legal values as long as an adversary can corrupt the states of at most √n processes at any time. Without adversarial involvement, just O(logn) time and work is needed for a stable consensus, with high probability.
Further, we analyzed models that limit the adversaries knowledge to a more realistic level and see how this affects its power. It is known that O(√n) is a tight upper bound on the number adverserial processes if the adversary has full knowledge of the network. That means, it knows the current state of all nodes. However, full knowledge is not a very realistic assumption as an attacker would need instantanious access to every participant in the network. In  we assumed that the adversary has slightly outdated information about the system. In particular, we simply assume that it takes one round round to gather all information from all nodes. As it turns out, this small and realistic constraint significinatly increases the robustness of consensus protocols. With this so-called 1-late adversary the almost-everywhere consensus tolerates up to O(n) faulty processes.
 T. Götte, C. Scheideler "Brief Announcement: The (Limited) Power of Multiple Identities" in the 34th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2022
 B. Doerr, L. A. Goldberg, L. Minder, T. Sauerwald and C. Scheideler: "Stabilizing Consensus with the Power of Two Choices", in the 23rd Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2011
 P. Robinson, C. Scheideler, A. Setzer: "Breaking the Ω(√n) Barrier: Fast Consensus under a Late Adversary", in the 30th Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2018