Paul Keeler

Bartek Błaszczyszyn, Antoine Brochard, H. Paul Keeler

We propose a new class of algorithms for randomly scheduling network transmissions. The idea is to use (discrete) determinantal point processes (subsets) to randomly assign medium access to various {\em repulsive} subsets of potential transmitters. This approach can be seen as a natural extension of (spatial) Aloha, which schedules transmissions independently. Under a general path loss model and Rayleigh fading, we show that, similarly to Aloha, they are also subject to elegant analysis of the coverage probabilities and transmission attempts (also known as local delay). This is mainly due to the explicit, determinantal form of the conditional (Palm) distribution and closed-form expressions for the Laplace functional of determinantal processes. Interestingly, the derived performance characteristics of the network are amenable to various optimizations of the scheduling parameters, which are determinantal kernels, allowing the use of techniques developed for statistical learning with determinantal processes. Well-established sampling algorithms for determinantal processes can be used to cope with implementation issues, which is is beyond the scope of this paper, but it creates paths for further research.

Bartłomiej Błaszczyszyn, Paul Keeler

A new type of dependent thinning for point processes in continuous space is proposed, which leverages the advantages of determinantal point processes defined on finite spaces and, as such, is particularly amenable to statistical, numerical, and simulation techniques. It gives a new point process that can serve as a network model exhibiting repulsion. The properties and functions of the new point process, such as moment measures, the Laplace functional, the void probabilities, as well as conditional (Palm) characteristics can be estimated accurately by simulating the underlying (non-thinned) point process, which can be taken, for example, to be Poisson. This is in contrast (and preference to) finite Gibbs point processes, which, instead of thinning, require weighting the Poisson realizations, involving usually intractable normalizing constants. Models based on determinantal point processes are also well suited for statistical (supervised) learning techniques, allowing the models to be fitted to observed network patterns with some particular geometric properties. We illustrate this approach by imitating with determinantal thinning the well-known Mat{é}rn~II hard-core thinning, as well as a soft-core thinning depending on nearest-neighbour triangles. These two examples demonstrate how the proposed approach can lead to new, statistically optimized, probabilistic transmission scheduling schemes.

R. Bowden, H. P. Keeler, A. E. Krzesinski et al.

Bitcoin is a electronic payment system where payment transactions are verified and stored in a data structure called the blockchain. Bitcoin miners work individually to solve a computationally intensive problem, and with each solution a Bitcoin block is generated, resulting in a new arrival to the blockchain. The difficulty of the computational problem is updated every 2,016 blocks in order to control the rate at which blocks are generated. In the original Bitcoin paper, it was suggested that the blockchain arrivals occur according to a homogeneous Poisson process. Based on blockchain block arrival data and stochastic analysis of the block arrival process, we demonstrate that this is not the case. We present a refined mathematical model for block arrivals, focusing on both the block arrivals during a period of constant difficulty and how the difficulty level evolves over time.

Johannes Göbel, Paul Keeler, Anthony E. Krzesinski et al.

In the context of the `selfish-mine' strategy proposed by Eyal and Sirer, we study the effect of propagation delay on the evolution of the Bitcoin blockchain. First, we use a simplified Markov model that tracks the contrasting states of belief about the blockchain of a small pool of miners and the `rest of the community' to establish that the use of block-hiding strategies, such as selfish-mine, causes the rate of production of orphan blocks to increase. Then we use a spatial Poisson process model to study values of Eyal and Sirer's parameter $γ$, which denotes the proportion of the honest community that mine on a previously-secret block released by the pool in response to the mining of a block by the honest community. Finally, we use discrete-event simulation to study the behaviour of a network of Bitcoin miners, a proportion of which is colluding in using the selfish-mine strategy, under the assumption that there is a propagation delay in the communication of information between miners.