Average Case Analysis of a Shared Register Emulation Algorithm
Distributed algorithms are important for managing systems with multiple networked components, where each component operates independently but coordinates to achieve a common goal. Previous theoretical research has produced numerous distributed algorithms but primarily uses mathematical proofs to yield theoretical results, such as worst-case runtime complexity. However, less research has been done on how these algorithms behave in practice, such as average-case runtime complexity. This paper will describe the empirical behavior of the distributed algorithm CCReg in a realistic environment, using the language DistAlgo to implement said algorithm. CCReg emulates a shared read/write register using a message-passing system. In particular, CCReg allows the underlying message-passing system to experience continuous changes to the set of components present, and tolerates crash failures of components. When the rate of component change and the fraction of crash failures are bounded, CCReg is proven to work correctly. The original paper specifies bounds for both that are guaranteed to work, and gives proof for those bounds. However, these bounds are restrictive and do not allow for much component change or many crash failures. Thus the goal of our implementation is to determine if CCReg's theoretical bounds can be relaxed in practice. We focus on CCReg's safety and liveness conditions: the algorithm eventually terminates, and a consistency condition called linearizability is maintained. We use a general method developed by Gibbons and Korach for determining if any ordering of operations satisfying linearizability exists. We find that, for executions where operations are randomly invoked, the algorithm does not exhibit any adverse behaviors. Each execution we tested terminates in finite time and has an order of operations satisfying linearizability. We discuss these findings, as well as future approaches and methodology for testing the theoretical boundaries in practice.
shared register emulation
average case analysis
Hu, Gerald Lee (2019). Average Case Analysis of a Shared Register Emulation Algorithm. Undergraduate Research Scholars Program. Available electronically from