A Markov-Chain-Based Model for Group Message Distribution in Connected Networks

A Markov-Chain-Based Model for Group Message Distribution in Connected Networks

Peter Bajorski, Michael Kurdziel
Copyright: © 2020 |Pages: 17
DOI: 10.4018/IJDA.2020070102
(Individual Articles)
No Current Special Offers


The authors introduce a stochastic Markov-chain-based model for the recursive distribution of a message from the source node to all remaining nodes. This recursive message distribution process produces a spanning tree topology over the connected network of nodes. The model has five input parameters: (1) the number of nodes n in the group, (2) the maximum number of child nodes, (3) the number of sub-message components needed to transfer a single message, (4) the probability p1 that two adjacent nodes in a network initiate a connection (edge) in the spanning tree, and (5) the probability p2 that each sub-message component is transferred correctly between nodes. The authors derive a closed-form expression for the expected group message distribution time, measured in discrete-time epochs, that is verified via Monte Carlo simulations. Since both the closed-form formulas and the Monte Carlo simulations are computationally intensive for networks with a large number of nodes n, this paper derives a reliable approximate formula for the expected distribution time for networks as large as n = 1000.
Article Preview

1. Introduction

Distributed networks can be described by a group of nodes that establish two-way communication channels. In settings with limited resources, it is often useful to model the communication between nodes in a network in order to develop efficient protocols. One example of such a protocol is group key agreement, in which a single message must be distributed to all members of the group in a secure and efficient manner. Consequently, as a precursor to the development of key agreement protocols, a method to model the message distribution time to all members of a group is a vital part of evaluating protocols built on this message distribution model.

Generally, group message distribution is initiated by a single node in the network who wishes to transmit a copy of a single message to every member of the group. There are several ways of performing this message distribution: (1) via point-to-point exchanges between the source node and every other node in the network, or more efficiently, (2) by recursively distributing the message from the source node to nearby neighboring nodes, who then in turn re-distribute the message on behalf of the source to their nearby nodes (this process repeats recursively until every node in the network receives the message). Our model relies on approach (2) for performance reasons. Furthermore, the recursive message distribution naturally produces a spanning tree topology over the connected network of nodes (see the timeline in Figure 1 for an illustration of this result).

In this work, we model the message distribution process with a Markov chain and then compute the expected message distribution time in this type of group-based communication setting. Our model captures a network and message distribution scenario with the following properties:

  • A fixed network (group) size,

  • A limitation on the number of connections which can be made by any single node,

  • The probability that two nodes successfully establish a communication link, and

  • For a message M that requires m - 1 exchanges to transfer, the probability that each exchange in the transmission is successful.

Our model is then verified via Monte Carlo simulations and useful trends are used to derive parameterized equations for computing the approximate message distribution time. We then conclude with a discussion of related work and motivating applications to which our model may be applied.

The model we present is by no means a first attempt at quantifying the performance of message distribution in ad-hoc (and related) networks. Similar Markov-based analyses have been performed for ad-hoc networks (Groenevelt et al. (2005)). Kong and Yeh (2008) also study the same problem, but include node mobility in their analysis, which is distinct from our fixed location ad-hoc network. The problem of message distribution latency has also been framed in different contexts, including both epidemic routing (Zhang et al. (2007)) and rumor spreading (Trpevski et al. (2010)). While constructed under related scenarios, these models are developed for different purposes with noticeable analytical differences. We discuss all of these related works at length in Section 5.


2. Group Message Distribution Model

Before presenting our model, we formalize the problem statement. We assume a network of n nodes, where each node can potentially establish communication with any other node. One node, denoted as IJDA.2020070102.m01, is assumed to contain a message M which is to be distributed to all other nodes in the network. In order to send the message from one node IJDA.2020070102.m02 to another IJDA.2020070102.m03, two steps need to occur:

  • Step 1: A communication link (edge) must be created between IJDA.2020070102.m04 and IJDA.2020070102.m05 .

  • Step 2: The message M is sent from the sender IJDA.2020070102.m06 to the recipient IJDA.2020070102.m07 in (m -1) installments, or stages, with a total of m stages needed for the entire transfer of M.

Complete Article List

Search this Journal:
Volume 4: 1 Issue (2023)
Volume 3: 2 Issues (2022): 1 Released, 1 Forthcoming
Volume 2: 2 Issues (2021)
Volume 1: 2 Issues (2020)
View Complete Journal Contents Listing