4.7 Workshop: Efficient Rock-Paper-Scissors

This workshop assumes that you have recently completed Workshop: Fair Rock-Paper-Scissors.

In this workshop, we study how transaction costs on consensus networks can be understood as the constants hidden by asymptotic notations when determining the expense of an algorithm when run on a decentralized application. In typical programming contexts, an algorithm that uses 3 log_2 n + 4 n operations is consider equivalent to an algorithm that uses 5 log_4 n + 22 n operations, because constants and bases are ignored in asymptoptic analysis. However, imagine that a program used n local computations and m consensus computations. We’ll call n the "computations" and m the "communications". In this case, the computations are free from the perspective of the consensus network, because they don’t cost network tokens, while the communication cost their price in gas, plus the fee to run them. Therefore, it is often economically efficient to increase n so that m can be smaller.

For example, in the context of tutorial’s version of Rock, Paper, Scissors!, the application uses 2 + 3r communications for a game with r rounds. This is because it takes two communications to set up the loop, then each round of the loop takes three communications. We could make a more complicated version of the application that is optimized in two ways.

First, we could optimize for the common case of when there is no draw and bundle a hand into the opening messages, and use 3 + 3(r - 1) = 3r communications for r rounds, for a saving of two communications. This would slightly increase the complexity of our program by duplicating the submission of hands, but we could easily abstract this into a Reach function.

Second, we could bundle k hands into each communication, so that the number of communications is 3(r//k) for r rounds for a reduction of communications by k times. This is possible through Reach’s ability to deal with array values. The exact value of k would be chosen empirically based on the relative difference in cost between increase message sizes and computations versus the fixed cost of having any transaction at all on the consensus network. Reach’s ability to abstract away the details of communication patterns also us to write this program abstractly and only specify the value of k as a compile-time parameter.

This is a general strategy that is regularly employed in efficient decentralized applications: although a textbook algorithm might say to use a setup phase and many round trips as you divide a space in half each time, it might be vastly more efficient on an actual network to apply meaning-preserving transformations like merging the setup into the loop and dividing the space by much larger constant, like one hundred.

This page is a placeholder for a future more detailed workshop. You could try to implement yourself though, given the sketch above!