I'll give a survey of how cellular automata and related systems can be used to implement distributed consensus, including both specific results and general principles learned from exploring the computational universe of simple programs, as well as our recent Wolfram Physics Project. I'll also outline the historical directions that have been taken, highlighting connections to a surprising variety of fields and approaches.
I will talk about how cellular automata networks can be used as a consensus algorithm for large-scale blockchain systems. The talk will be focused on the theories behind the algorithm, the theoretical and engineering challenges we faced when applying the algorithm to real world systems, the security of the algorithm in the presence of malicious actors and our practical solutions.
As paradigmatic distributed computational systems, cellular automata constitute suitable testbeds for probing the emergence of solutions to decision problems defined in terms of achieving a consensus. The talk will review various results concerning two benchmark problems in this context, density and parity determination.
The designs of decentralized storage systems include data redundancy mechanisms and incentivization to provide dependable services. This talk will discuss how we take inspiration from cellular automata to benchmark diverse redundancy mechanisms while taking in consideration the dynamics of these complex networks. Then, I will outline our advanced work on the intersection of availability and integrity mechanisms as well as the challenges of using cellular automata to benchmark incentive mechanisms.
Decision problems such as the density classification problem can be solved using cellular automata if one allows more than one rule. Such solutions exploit phase transitions or bifurcations occurring in some cellular automata. We will review basic properties of such transitions in binary cellular automata in one dimension and discuss their potential applications to solving classification problems with higher number of states and in higher dimensions.
Any distributed ledger technology allows nodes to decide what information will be included into the permanent ledger and what information will be rejected. I will discuss to how to reach such binary decisions though voting protocols that can be modeled and understood through probabilistic cellular automata.
After outlining the main results on the possibility of information storage and reliable computation in cellular automata, we will focus on the challenges presented by asynchronous updating.
Consider a society of individuals represented as the nodes of a network, each having one over two possible opinions, which evolve (synchronously or asynchronously) according to the local majority rule. We study the properties and complexity of such dynamical systems. First, we show that it is possible to define an energy functional over each network configuration, which is nonincreasing over time, proving that the attractors of the majority dynamics are fixed points or limit cycles of period two. Later, we discuss under which conditions it is possible to predict the changes in the opinion of an individual. Specifically, we analyze the impact of the network's topology on the computational complexity of the state computation on a given time step. Presented from joint work with Pedro Montealegre.
In this talk, Professor Emin Gün Sirer will share insights from his vantage point at the cutting edge of blockchains, decentralized finance and digital assets. He will cover the state of blockchains today and the vast untapped potential of these technologies.
We introduce a new staking procedure based on the Ouroboros family of proof-of-stake blockchain protocols. This new staking procedure enhances the security of the underlying protocol while stabilizing block time intervals in the permissionless dynamic-availability setting. An automata model is used to calculate the adversarial advantage of nothing-at-stake grinding attacks, exhibiting tightly constrained branching chain growth under appropriate protocol parameters. This talk will present analysis and empirical results demonstrating for the first time a nonlinear trend in chain growth that favors the honest majority of staking power.