Grassroots Distributed Systems for Digital Sovereignty: Abstract and Introduction

cover
13 May 2024

This paper is available on arxiv under CC BY-NC-ND 4.0 DEED license.

Authors:

(1) Ehud Shapiro, Department of Computer Science and Applied Math, Weizmann Institute of Science, Israel and ehud.shapiro@weizmann.ac.il.

Abstract

Informally, a distributed system is grassroots if it can have autonomous, independently-deployed instances—geographically and over time—that can interoperate once interconnected. An example would be a serverless smartphone-based social network supporting multiple independently budding communities that merge when a member of one community becomes also a member of another. Grassroots applications are potentially important as they may provide a foundation for digital sovereignty, which we interpret as the ability of people to conduct their social, economic, civic, and political lives in the digital realm solely using the networked computing devices they own and operate (e.g., smartphones), free of third-party control, surveillance, manipulation, coercion, or value-extraction (e.g., by global digital platforms such as Facebook or Bitcoin).

Here, we formalize the notion of grassroots distributed systems and grassroots implementations; specify an abstract grassroots dissemination protocol; describe and prove an implementation of grassroots dissemination for the model of asynchrony; extend the implementation to mobile (addresschanging) devices that communicate via an unreliable network (e.g. smartphones using UDP); and illustrate how grassroots dissemination can realize applications that support digital sovereignty – grassroots social networking and sovereign cryptocurrencies. The mathematical construction employs distributed multiagent transition systems to define the notions of grassroots protocols and grassroots implementations, to specify grassroots dissemination protocols and their implementation, and to prove their correctness. The implementation uses the blocklace – a partially-ordered DAG-like generalization of the blockchain.

2012 ACM Subject Classification Computer systems organization → Peer-to-peer architectures; Networks → Network protocol design; Networks → Formal specifications; Software and its engineering → Distributed systems organizing principles

Keywords and phrases Grassroots Distributed Systems, Digital Sovereignty, Dissemination Protocol, Multiagent Transition Systems, Blocklace

1 Introduction

Motivation. Today, client-server/cloud computing is the dominant architecture in the digital realm, supporting the global digital platforms we inhabit on a daily basis. These platforms have adopted surveillance-capitalism [30] as their business model, which drives them to monitor, induce, and manipulate their inhabitants for profit. Authoritarian regimes may have an added ingredient: A “back-door” to the global platform for the regime to monitor, censor, control, and even punish the digital behavior of its citizens.

Blockchain technology and cryptocurrencies [18, 4] offer a radically-different architecture that is peer-to-peer and ‘permissionless’, open to participation by everyone. Still, a ‘peer’ in this architecture is typically a high-performance server or, better yet, a highperformance server-cluster. Despite the promise of openness and distribution of power, leading cryptocurrencies are also global platforms dominated—even controlled—by a handful of ultra-high-performance server-clusters [13]. The operators of these server clusters are remunerated for their efforts via inflationary coin minting or transaction fees/gas paid by the platform users. An alternative server-based architecture that strives for better distribution of power is federation, employed for example by BitTorrent [9], IPFS [2], and Mastodon [21].

Today’s smartphones have orders-of-magnitude more computing power, memory, and network speed compared to the Unix workstations that were the workhorses of the Internet revolution. Yet, they function mostly as adorned gateways to global digital platforms, with even peer-to-peer streaming being initiated and controlled by the cloud. We believe that the lack of a business model that can incentivize ‘genuine’ peer-to-peer applications and the lack of suitable architectural foundations for such applications are the culprit.

Here, we are concerned with providing such architectural foundations, referred to as a grassroots architecture, a notion introduced and formally defined below. Informally, a distributed system is grassroots if it can have autonomous, independently-deployed instances— geographically and over time—that can interoperate once interconnected. The quintessential manifestation of a grassroots distributed system would be a peer-to-peer, serverless, smartphone-based social network that can form independently at multiple communities and at different times, and interoperate if and when the communities are interconnected, for example via a person that becomes a member of two hitherto-disjoint communities. The grassroots dissemination protocol developed here can, in principle, support such an application. Grassroots applications are potentially important as they may provide a foundation for digital sovereignty [20, 14, 17], which we interpret as the ability of people to conduct their social, economic, civic, and political lives in the digital realm solely using the networked computing devices they own and operate (e.g., smartphones), free of third-party control, surveillance, manipulation, coercion, or value-extraction (e.g., by global digital platforms such as Facebook or Bitcoin).

In general, a system designed to have a single global instance is not grassroots. Clientserver/cloud systems in which two instances cannot co-exists due to competition/conflict on shared resources (e.g., same web address), or cannot interoperate when interconnected, are not grassroots. So are peer-to-peer systems that require all-to-all dissemination, including mainstream cryptocurrencies and standard consensus protocols [6, 29, 15], since a community placed in a larger context cannot ignore members of the larger context. Also are systems that use a global shared data-structure such as pub/sub systems [7, 8], IPFS [2], and distributed hash tables [28], since a community placed in a larger context cannot ignore updates to the shared resource by others. While we do not prove this formally, federated systems such as BitTorrent [9] with private trackers and Mastodon [21], in which federation is optional and there are no shared global resources, may be grassroots.

Contributions. While the notion of ‘grassroots’ has intuitive appeal and is well-established in the social and political arena [5], it has not received, to the best of our knowledge, any formal treatment. One contribution of this work is its formal definition and characterization in the context of multiagent distributed systems.

Another contribution is a specification and a proven implementation for the model of asynchrony of perhaps the first grassroots dissemination protocol. The result is powerful enough to realize serverless social networking and sovereign cryptocurrencies [25]. The protocol is specified by the rather-abstract Grassroots Dissemination protocol and implemented by the blocklace-based Cordial Grassroots Dissemination protocol, both specified as asynchronous distributed multiagent transitions systems [24], with pseudocode realizing the latter for the model of asynchrony.

Related work. The blocklace is a partially-ordered generalization of the blockchain that functions as a fault-resilient, conflict-free replicated data type [26] and has been employed to realize consensus protocols [16]. All-to-all dissemination has been explored extensively over the past decades, under the notions of gossip [23] and epidemic [19] protocols. Here, we use all-to-all dissemination as a stepping stone to grassroots dissemination.

The grassroots dissemination protocol must give credit to the pioneering 1990’s Bayou project at Xerox PARC [10]. It is also reminiscent of the pub/sub model [7, 8], where every agent is viewed as a publisher and every follower as a subscriber. While peer-to-peer protocols for the pub/sub model were developed (see [22] for a review), apparently they are not grassroots. For example, the Poldercast protocol [22] is not grassroots since it assumes a global set of topics that is disjoint from the set of agents participating in the protocol. In particular, in Poldercast any infinite correct run of a group of agents P that subscribes to a topic t, when repeated within a larger group P’ with members that publish to the same topic t, would violate liveness. The reason is that members of P that subscribe to t, when embedded within P’, should receive in such a run posts to t by published by agents in P’ \ P; but in such a run they do not. In addition, there are social networks such as PeerSoN [3] that are peer-to-peer, but to the best of our understanding are not grassroots, for example since employing Distributed Hash Tables [28] as a shared global resource.

Outline. The dissemination protocols introduced in this paper and their implementations are summarized in Figure 1. The rest of the paper is organized as follows. Section 2 briefly introduces asynchronous distributed multiagent transition systems (expanded upon in Appendix A) and implementations among them, providing the mathematical basis for defining grassroots protocols and grassroots implementations. It then introduced the rather-abstract Grassroots Dissemination protocol GD and proves it to be grassroots. Section 3 describes the implementation of grassroots dissemination using the blocklace – a DAG-like partially-ordered generalization of the blockchain. It introduces blocklace basics; the blocklace-based Grassroots Cordial Dissemination protocol CGD; presents an implementation σ of GD by CGD and proves it correct; provides pseudocode implementation of CGD for the model of asynchrony; and extends the implementation to mobile devices using unreliable communication (UDP). Section 4 illustrates two potential applications of grassroots dissemination: Twitter-like and WhatsApp-like serverless social networking, and sovereign cryptocurrencies. Section 5 concludes the paper. Due to length limitations, proofs and some auxiliary material are relegated to the Appendices.

Figure 1 Protocols and Implementations presented in this paper. Allto-All Dissemination AD (Def. 44), Grassroots Dissemination GD (Def. 15),Cordial Grassroots Dissemination CGD (Def. 26), and the implementation σ (Def. 33, Thm. 29) of GD by CGD. Algorithms 1, 2, and 3 that implement CGD for Asynchrony and UDP are presented as pseudocode.