Problems of consensus in multi-agent systems are often viewed as a series of independent, simultaneous local decisions made between a limited set of options, all aimed at reaching a global agreement. Key challenges in these protocols include estimating the likelihood of various outcomes and finding bounds for how long it may take to achieve consensus, if it occurs at all. To date, little attention has been given to the case where some agents have no initial opinion. In this paper, we introduce a variant of the consensus problem which includes what we call `agnostic' nodes and frame it as a combination of two known and well-studied processes: voter model and rumour spreading. We show (1) a martingale that describes the probability of consensus for a given colour, (2) bounds on the number of steps for the process to end using results from rumour spreading and voter models, (3) closed formulas for the probability of consensus in a few special cases, and (4) that the computational complexity of estimating the probability with a Markov chain Monte Carlo process is $O(n^2 \log n)$ for general graphs and $O(n\log n)$ for Erd\H{o}s-R\'enyi graphs, which makes it an efficient method for estimating probabilities of consensus. Furthermore, we present experimental results suggesting that the number of runs needed for a given standard error decreases when the number of nodes increases.

We consider two simple asynchronous opinion dynamics on arbitrary graphs where every node $u$ has an initial value $\xi_u(0)$. In the first process, the NodeModel, at each time step $t\ge 0$, a random node $u$ and a random sample of $k$ of its neighbours $v_1,v_2,\cdots,v_k$ are selected. Then, $u$ updates its current value $\xi_u(t)$ to $\xi_u(t+1) = \alpha \xi_u(t) + \frac{(1-\alpha)}{k} \sum_{i=1}^k \xi_{v_i}(t)$, where $\alpha \in (0,1)$ and $k\ge 1$ are parameters of the process. In the second process, the EdgeModel, at each step a random pair of adjacent nodes $(u,v)$ is selected, and then node $u$ updates its value equivalently to the NodeModel with $k=1$ and $v$ as the selected neighbour. For both processes, the values of all nodes converge to $F$, a random variable depending on the random choices made in each step. For the NodeModel and regular graphs, and for the EdgeModel and arbitrary graphs, the expectation of $F$ is the average of the initial values $\frac{1}{n}\sum_{u\in V} \xi_u(0)$. For the NodeModel and non-regular graphs, the expectation of $F$ is the degree-weighted average of the initial values. Our results are two-fold. We consider the concentration of $F$ and show tight bounds on the variance of $F$ for regular graphs. We show that, when the initial values do not depend on the number of nodes, then the variance is negligible, hence the nodes are able to estimate the initial average of the node values. Interestingly, this variance does not depend on the graph structure. For the proof we introduce a duality between our processes and a process of two correlated random walks. We also analyse the convergence time for both models and for arbitrary graphs, showing bounds on the time $T_\varepsilon$ required to make all node values `$\varepsilon$-close' to each other. Our bounds are asymptotically tight under assumptions on the distribution of the initial values.

Multi-agent consensus problems can often be seen as a sequence of autonomous and independent local choices between a finite set of decision options, with each local choice undertaken simultaneously, and with a shared goal of achieving a global consensus state. Being able to estimate probabilities for the different outcomes and to predict how long it takes for a consensus to be formed, if ever, are core issues for such protocols. Little attention has been given to protocols in which agents can remember past or outdated states. In this paper, we propose a framework to study what we call \emph{memory consensus protocol}. We show that the employment of memory allows such processes to always converge, as well as, in some scenarios, such as cycles, converge faster. We provide a theoretical analysis of the probability of each option eventually winning such processes based on the initial opinions expressed by agents. Further, we perform experiments to investigate network topologies in which agents benefit from memory on the expected time needed for consensus.

Provenance is a record that describes how entities, activities, and agents have influenced a piece of data. Such provenance information is commonly represented in graphs with relevant labels on both their nodes and edges. With the growing adoption of provenance in a wide range of application domains, increasingly, users are confronted with an abundance of graph data, which may prove challenging to analyse. Graph kernels, on the other hand, have been consistently and successfully used to efficiently classify graphs. In this paper, we introduce a novel graph kernel called \emph{provenance kernel}, which is inspired by and tailored for provenance data. It decomposes a provenance graph into tree-patterns rooted at a given node and considers the labels of edges and nodes up to a certain distance from the root. We employ provenance kernels to classify provenance graphs from three application domains. Our evaluation shows that they perform well in terms of classification accuracy and yield competitive results when compared against standard graph kernel methods and the provenance network analytics method while taking significantly less time.Moreover, we illustrate how the provenance types used in provenance kernels help improve the explainability of predictive models.