Semitopology: distributed collaborative action via topology, algebra, and logic

ML LOG COL
2024年01月16日
本文介绍了半拓扑(semitopologies),它是点集拓扑的一种推广,消除了开集交集必须为开集的限制。直观上,点是某个分布式系统的参与者,开集是可以协作更新本地状态的参与者集合,我们称之为可操作联盟(actionable coalition)。什么构成可操作联盟取决于我们想要建模的行为。直观的例子包括“一群人集体足够强大,可以举起一块石头”,状态更新非常简单,是从“托低石头”到“举高石头”,此更新对所有可操作联盟的参与者都是共同的。或者,考虑“两个人希望用一罐果汁换一块巧克力”,在这种情况下,联盟是任何这样的一对人,状态更新在参与者之间不同,可以将它们翻转为“有/没有果汁”和“有/没有巧克力”。这些系统的特点是状态更新是局部的、自愿的、可能在参与者之间有所不同,并且不假定受到中央权威的许可或同步。点对点计算机网络,包括文件共享和区块链系统,提供了计算方面的有趣例子。本文提出了半拓扑的全面视角,包括点集半拓扑、代数和逻辑,这些视角都受到上述考虑的启发。这本身很有趣,而且提供了一个概念框架,可以理解一类有用的分布式系统。
We introduce semitopologies, a generalisation of point-set topology that removes the restriction that intersections of open sets need necessarily be open. The intuition is that points are participants in some distributed system, and an open set is a collection of participants that can collaborate to update their local state by taking a distributed collaborative action; we call this an actionable coalition. What constitutes an actionable coalition depends on what actions we want to model. Intuitive examples include 'a group of people that is collectively strong enough to lift a rock', where the state update is very simply 'holding rock low' to 'holding rock high' and this update is common to all participants in the actionable coalition. Or, consider 'two people wishing to barter a can of juice for a bar of chocolate', in which case the coalition is any such pair and the state updates differ between participants to flip them between 'has/has no juice' and 'has/has no chocolate'. A characteristic of these systems is that state updates are local to the coalition, voluntary, may vary between participants, and are not assumed subject to permission or synchronisation by a central authority. Peer-to-peer computer networks, including filesharing and blockchain systems, provide motivating examples from computing. This paper presents a comprehensive view of semitopologies which includes point-set semitopology, algebra, and logic inspired by these considerations. This is interesting in and of itself and it provides a conceptual framework within which to understand a useful class of distributed systems.
许愿