We introduce the notion of a validating labelled state transition and message production system (VLSM), a tool for formal modeling and analysing faulty distributed systems. The central focus of our investigation is equivocation, a faulty behaviour that we formally model, reason about, and then show how to detect from durable evidence that may be available locally to system components. Equivocating components exhibit behaviour that is inconsistent with single-trace system executions, while also only interacting with other components by sending and receiving valid messages. Components of system are called validators for that system if their validity constraints validate that the messages they receive are producible by the system. Our main result shows that for systems of validators, the effect that Byzantine components can have on honest nodes is precisely identical to the effect that equivocating validators can have on non-equivocating validators. Therefore, for distributed systems of potentially faulty validators, replacing Byzantine nodes with equivocating validators has no material analytical consequences, and forms the basis of a sound alternative foundation to Byzantine fault tolerance analysis.
翻译:我们引入了验证标记为国家过渡和电文制作系统(VLSM)的概念,这是一个正式建模和分析错误分布系统的工具。我们调查的中心焦点是空洞,这是一种我们正式模拟、说明理由的错误行为,然后显示如何从当地可能掌握的持久证据中发现系统部件元件的特征,这些元件的显示行为与单一跟踪系统执行不一致,同时仅与其他元件进行互动,发送和接收有效信息。如果系统元件的有效性限制证实其收到的电文可以由系统生成,则该系统的元件被称为验证人。我们的主要结果显示,对于验证人系统而言,拜占庭元件对诚实节点的效果与对非均衡验证人可能对非均衡验证人的效果完全相同。因此,对于分布的潜在错误验证人系统,用配有有效信号的验证人取代拜占廷节点,没有实质性的分析结果,并且构成比占庭断容度分析的可靠替代基础。