Consensus among n parties tolerating up to t Byzantine faults requires n > 2t in synchronous networks and n > 3t in asynchronous networks. The higher resilience achievable in synchrony relies on a known message delay bound Δ, whereas asynchronous protocols make no timing assumptions but must tolerate fewer faults. Prior work addressed this gap only partially. Some protocols achieve responsiveness under synchrony, meaning that their running time adapts to the actual network delay, but offer no guarantees under asynchrony, while others guarantee correctness under both network conditions but sacrifice responsiveness. Only recently, Elsheimy, Kamp, Loss, and Nielsen (IACR 2026) showed for binary validated Byzantine agreement (VBA) that if ts, ta, and tr denote the synchronous, asynchronous, and responsiveness thresholds, respectively, then the conditions n > 2ts + ta and n > ts + 2tr are necessary and sufficient to simultaneously achieve asynchronous security, synchronous security, and responsiveness. While binary BA (or VBA) can be extended to multi-valued Byzantine agreement (MVBA) via standard reductions, such transformations generally incur blow-up in the communication. Whether these tight resilience conditions can be achieved for MVBA with optimal communication complexity remained open.

We present a deterministic synchronous protocol for binary Byzantine Agreement against a corrupt minority with adaptive O(n · f) communication complexity, where f is the exact number of corruptions. Our protocol improves the previous best-known deterministic Byzantine Agreement protocol developed by Momose and Ren (DISC 2021), whose communication complexity is quadratic, independent of the exact number of corruptions. Our approach combines two distinct primitives that we introduce and implement with O(n · f) communication, Reliable Voting and Weak Byzantine Agreement. In Reliable Voting, all honest parties agree on the same value only if all honest parties start with that value, but there is no agreement guarantee in the general case. In Weak Byzantine Agreement we achieve agreement, but validity requires that the inputs to the protocol satisfy certain properties. Our Weak Byzantine Agreement protocol is an adaptation of the recent Cohen et al. protocol (OPODIS 2022), in which we identify and address various issues.

Society appears to be on the verge of recognizing the need for control over sensitive data in modern web applications. Recently, many systems claim to give control to individuals, promising the preeminent goal of data sovereignty. However, despite recent attention, research and industry efforts are fragmented and lack a holistic system overview. In this paper, we provide the first transecting systematization of data sovereignty by drawing from a dispersed body of knowledge. We clarify the field by identifying its three main areas: (i) decentralized identity, (ii) decentralized access control and (iii) policy-compliant decentralized computation. We find that literature lacks a cohesive set of formal definitions. Each area is considered in isolation, and priorities in industry and academia are not aligned due to a lack of clarity regarding user control. To solve this issue, we propose formal definitions for each sub-area. By highlighting that data sovereignty transcends the domain of decentralized identity, we aim to guide future works to embrace a broader perspective on user control. In each section, we augment our definition with security and privacy properties, discuss the state of the art and proceed to identify open challenges. We conclude by highlighting synergies between areas, emphasizing the real-world benefit obtained by further developing data sovereign systems.