# ZeroDL: Zero-shot Distribution Learning for Text Clustering
via Large Language Models

Hwiyeol Jo1,2, Hyunwoo Lee1,2, Taiwoo Park2
1NAVER, 2NAVER Search US
<EMAIL_ADDRESS>

###### Abstract

The recent advancements in large language models (LLMs) have brought
significant progress in solving NLP tasks. Notably, in-context learning (ICL)
is the key enabling mechanism for LLMs to understand specific tasks and
grasping nuances. In this paper, we propose a simple yet effective method to
contextualize a task toward a specific LLM, by (1) observing how a given LLM
describes (all or a part of) target datasets, i.e., open-ended zero-shot
inference, and (2) aggregating the open-ended inference results by the LLM,
and (3) finally incorporate the aggregated meta-information for the actual
task. We show the effectiveness of this approach in text clustering tasks, and
also highlight the importance of the contextualization through examples of the
above procedure.

##  1 Introduction

Large language models (LLMs) have demonstrated impressive performances on
various downstream tasks Devlin et al. (2019); Radford et al. (2019). These
also exhibit the ability to understand the context of input text, known as in-
context learning (ICL) Brown et al. (2020); OpenAI (2023). ICL allows to
leverage LLMs for specific tasks without further extensive training. However,
effective use of ICL hinges on well-designed prompts.

While prompts with few-shot examples can demonstrably improve performance,
they can easily overfit a model to the examples (Perez et al. (2021); Mizrahi
et al. (2023); inter alia). This led to a growing interest in zero-shot
learning, which reduces the need for intricate few-shot selection. Recent
advancements in zero-shot learning involve incorporating more sophisticated
use of prompt structures, such as Chain-of-Thought Wei et al. (2022), zero-
shot reasoning Kojima et al. (2022), and models trained to follow instructions
Ouyang et al. (2022); Chung et al. (2024).

Figure 1: Illustration of proposed method ZeroDL. While in-context learning
(ICL) relies on examples tailored to specific tasks, ZeroDL aggregates all the
outputs from these zero-shot inferences, resulting in meta-level information.
This meta-level information is then used by the LLM to generate its final
predictions.

Motivated by the core principle of ICL–providing task and data contexts within
prompts–we propose an approach to construct more effective zero-shot prompts
by understanding how LLMs describe datasets across prompting outputs. As
illustrated in Figure 1, the method, called Zero-shot Distribution Learning
(ZeroDL), first aims to learn data distributions through zero-shot inferences.
The method comprises two key components: (1) open-ended zero-shot inference,
and (2) output aggregation. A zero-shot prompt is then constructed with the
generated meta information, and used for actual task. This method takes
advantage of the self-generated frame of LLMs to successfully carry out a
given task.

We exemplify the effectiveness of ZeroDL with text clustering tasks, where we
assume an absence of ground-truth class labels. Unlike traditional clustering
algorithms such as K-Means representing groups based on distance metrics in
embedding space, our method works in a text-to-text format. Hence, our
approach allows clustering with perspectives and/or specific context. For
instance, the sentences "I love this movie" and "I hate this movie" express
opposite sentiment but belong to the same topic cluster of movie reviews.
Refer to Table 8 in the Appendix for potential risk of absence of the
perspectives.

Our contributions in this paper are as follows:

  * •

We propose a novel approach called Zero-shot Distribution Learning that
leverages zero-shot inferences to generate meta-level information about the
data distribution by aggregating open-ended inference outputs from datasets.

  * •

ZeroDL enables models to perform text-based clustering, empowering them to
handle data with specific context, which offers advantages over embedding-
based clustering methods.

  * •

Our experiments show that ZeroDL is competitive against embedding-based
clustering methods on several datasets. ZeroDL even achieves better
performances than models with ground-truth class labels in some cases.

##  2 Related Works

While there have been a few attempts to leverage LLMs for clustering tasks,
majority of existing approaches rely on traditional methods like K-Means
clustering based on LLM-generated embeddings Petukhova et al. (2024);
BehnamGhader et al. (2024). In contrast, our approach leverages text-level
prompting, which injects specific viewpoints into LLMs, enabling it to perform
more targeted and contextualized clustering.

The importance of appropriate ground-truth labels extends beyond clustering
and permeates ICL. While Min et al. (2022) observed cases where the input-
label correspondence does not play significant roles, Yoo et al. (2022) argued
that the impact heavily depends on target tasks and experiment settings.
Compared with the few-shot settings these works assumed, our method is with
zero-shot for clustering. We believe that this work would serve as a reference
that supports the appropriate class information is crucial for the
performances, as we develop ZeroDL to leverage the power of generative LLMs to
propose effective class labels, i.e., adjusting a task from LLMs’ perspective.

Model |  Method |  IMDB |  SST-2 |  SST-5 |  YRev |  AGNew |  DBp(F) |  DBp(B) |  Yah(F) |  Yah(B) |  Macro |  Micro
---|---|---|---|---|---|---|---|---|---|---|---|---
TF-IDF |  KMeans |  52.1 |  53.0 |  26.2 |  35.2 |  43.8 |  55.9 |  62.8 |  44.7 |  46.5 |  46.7 |  48.8
mistral |  Gold(C-T) |  87.5 |  77.0 |  41.8 |  50.8 |  60.7 |  74.2 |  85.2 |  40.8 |  62.5 |  64.5 |  68.1
-7b-inst |  Gold(T-C) |  91.7 |  82.5 |  43.3 |  51.8 |  82.7 |  84.1 |  82.7 |  50.9 |  73.8 |  71.5 |  72.7
|  ZeroDL(C-T) |  85.3 |  82.4 |  43.4 |  51.6 |  75.4 |  64.0 |  73.3 |  47.2 |  69.4 |  65.8 |  65.1
|  ZeroDL(T-C) |  92.2 |  79.4 |  36.0 |  48.2 |  81.0 |  62.2 |  78.4 |  51.8 |  73.4 |  67.0 |  66.4
|  llm2vec+KMeans |  62.1 |  55.2 |  30.3 |  56.0 |  84.4 |  96.1 |  70.8 |  48.0 |  46.2 |  61.0 |  67.5
Llama-3 |  Gold(C-T) |  66.5 |  73.7 |  42.1 |  48.9 |  55.9 |  71.3 |  75.5 |  35.2 |  54.7 |  58.2 |  61.1
-8b-inst |  Gold(T-C) |  93.2 |  84.2 |  46.0 |  53.5 |  70.2 |  74.6 |  79.2 |  49.3 |  75.4 |  69.5 |  70.3
|  ZeroDL(C-T) |  89.8 |  74.2 |  42.6 |  37.6 |  69.0 |  65.9 |  52.5 |  46.8 |  48.2 |  58.5 |  56.4
|  ZeroDL(T-C) |  66.7 |  79.1 |  41.1 |  49.2 |  80.4 |  73.2 |  63.7 |  49.1 |  48.6 |  61.2 |  60.8
|  llm2vec+KMeans |  53.2 |  53.2 |  29.6 |  54.8 |  85.1 |  94.5 |  72.7 |  47.4 |  50.4 |  60.1 |  66.2
Llama-3 |  Gold(C-T) |  94.4 |  88.9 |  53.0 |  56.6 |  83.2 |  94.8 |  95.8 |  65.3 |  82.4 |  79.4 |  80.7
-70b-inst |  Gold(T-C) |  95.2 |  89.4 |  52.3 |  58.2 |  81.1 |  95.8 |  91.0 |  63.8 |  82.6 |  78.8 |  80.3
|  ZeroDL(C-T) |  94.3 |  90.0 |  42.7 |  47.7 |  83.3 |  55.3 |  35.4 |  51.2 |  82.0 |  64.7 |  57.5
|  ZeroDL(T-C) |  95.0 |  89.4 |  41.5 |  49.3 |  72.6 |  47.0 |  36.1 |  53.2 |  81.4 |  62.8 |  56.2

Table 1:  The performance of LLMs for text clustering. C-T denotes the prompt
order with class information then input text. T-C is the reversed. Bold means
the best accuracy and underline the outperforming cases than ground-truth
(i.e., Gold) class label setting. Note that llm2vec for Llama3-70b is not
publicly available at the moment.

##  3 Proposed Method: ZeroDL

The framework is illustrated in Figure 1.

Stage 1: Open-Ended Inference. We begin by designing a prompt for zero-shot
classification. This prompt intentionally avoids any detailed information
about the task, minimizing the risk of overfitting. Based on the idea, we opt
for the simplest prompt format:  Text: [text]\n\nClassify the text to the best
[type_of_task]. where [text] is the input data and [type_of_task] provides
view of the task. In the experiment, it can be either sentiment or topic.
Leveraging this prompt, we perform model inferences on the input data ($D$).
This process generates open-ended class predictions, denoted as
$\hat{m_{1}}\cdots\hat{m_{N}}$.

Stage 2: Aggregation. The open-ended predictions lack constraints, leading to
potentially inconsistent output formats. For instance, the model might predict
"positive" and "non-positive" classes, while the ground-truth is "positive"
and "negative". The predictions could even be entire sentences. To address the
inconsistencies in the open-ended predictions, we employ aggregation strategy.

Before the aggregation, we count the frequency of each predictions and sort
it. After that, the predictions which frequency is only 1 are dropped in order
to filter out extraordinary predictions and save computation. Next, we
iteratively construct subsets of the predictions by removing the least
frequent predictions one by one. This process results in a list of subsets,
denoted as [ $\\{\hat{m_{1}},\hat{m_{2}},\cdots,\hat{m_{U}}\\}$,
$\\{\hat{m_{1}},\hat{m_{2}},\cdots,\hat{m_{U-1}}\\}$, $\cdots$
$\\{\hat{m_{1}}\\}$ ] where $U$ denotes the number of remained predictions. We
input all the subset to provide more weights to the frequently occurred
predictions. The prompt for aggregation is as follows:
[type_of_task] List: \- $\hat{m_{1}}$\n- $\hat{m_{2}}$\n- ... \n$\hat{m_{U}}$
# prompt (sub)set \n\nAggregate the [type_of_task] List into
[NUM_CLUSTER_CLASS] classes. where [NUM_CLUSTER_CLASS] is pre-defined number
of classes to cluster.
While the prompt instructs the LLM to predict a specific number of classes
([NUM_CLUSTER_CLASS]), the model outputs often still lack coherence,
especially in generating exact number of classes. To address this, we select
the LLM outputs where the number of aggregated classes matches the pre-defined
number of cluster classes. We then use the most frequent class pairs
aggregated from prompt (sub)sets as meta-information $\hat{M}$. This
information represents the model’s understanding of potential views over the
entire data.

Stage 3: Leveraging Meta-Information for Prediction.  We incorporate the
aggregated meta-information ($\hat{M}$) into the classification prompt111The
order of Text: and Class description: can be reversed. to enhance the model’s
prediction capabilities:

Text: [text]\n\nClass description:
---
\- Class 0: $\hat{M_{0}}$
\- Class 1: $\hat{M_{1}}$
\- Class $\cdots$: $\hat{M_{\cdots}}$
\- Class $C$: $\hat{M_{C}}$
\n\nBased on the class description, classify
the text to the best [type_of_task] class.

Within the prompt, we include placeholders denoted as \- Class n:. These
placeholders serve as templates for the LLM to parse.

By incorporating the meta-information ($\hat{M}$) into the prompt, we enable
the LLM to perform conditioned classification within the clustering context.
The generated meta-information might not directly correspond to the ground-
truth classes, potentially leading to variations in performance.

##  4 Experiments

Models.  Our experiments are conducted on mistral-7b-instruct-v0.2 Jiang et
al. (2023) due to its impressive performance even with a relatively small
parameter size compared with other LLMs. We additionally report results
obtained with the Llama-3 family models Meta (2024) from HuggingFace Wolf et
al. (2020) ran with vLLM library Kwon et al. (2023). Greedy decoding is
employed for generation222Note that the current version of vLLM might exhibit
non-deterministic behavior. and the final prediction is done with
guided_choice hyperparameters. We follow the official instruction formatting
guidelines. The results are averaged from 5 runs. We also tested llm2vec
BehnamGhader et al. (2024) with KMeans approach where applicable.

Datasets and Evaluation.  We use 6 datasets: IMDB Maas et al. (2011), SST-2,
SST-5 Socher et al. (2013), YelpReivews Zhang et al. (2015) for sentiment
classification and AGNews, DBpedia Lehmann et al. (2015), YahooAnswers Chang
et al. (2008) for topic classification. Further information is presented in
Table 4 of the Appendix.

3 Data | Method | ClassLabels
---|---|---
3 SST-5 | ZeroDL |  |  Negative Sentiment: This class includes all the sentiment labels that express a negative or sad emotion towards the movie or documentary. Examples include (…)
---
Ambiguous Sentiment: This class includes all the sentiment labels that do not
clearly express a positive or negative emotion towards the movie or
documentary. Examples include (…)
Mixed Sentiment: This class includes all the sentiment labels that express a
mixed sentiment towards the movie or documentary. Examples include (…)
Positive Sentiment: This class includes all the sentiment labels that express
a positive emotion towards the movie or documentary. Examples include (…)
Gold |  |  Very Negative, Negative, Neutral, Positive, Very Positive
---
AGNews | ZeroDL |  |  International Relations and Politics: This class includes topics related to international relations, diplomacy, Middle East politics, terrorism, nuclear politics, and elections.
---
Sports and Entertainment: This class includes topics related to sports,
tennis, golf, basketball, baseball, cricket, and entertainment.
Business and Economy: This class includes topics related to the economy,
finance, stocks, mergers and acquisitions, retail, real estate, and labor
markets.
Technology and Science: This class includes topics related to technology,
computing, internet, cybersecurity, space exploration, and science.
Gold |  |  World, Sports, Business, Sci/Tech
---
3 |  |

Table 2: The example of generated class labels in 5-class sentiment classification (SST-5), and topic classification (AGNews). ZeroDL can generates alternative class labels and its description. Additional examples are in Table 7. |  S2(C-T) |  S2(T-C) |  S5(C-T) |  S5(T-C)
---|---|---|---|---
RandToken |  51.6 |  59.5 |  28.6 |  28.6
AutoL(Best) |  86.8 |  84.9 |  41.8 |  38.5
AutoL(Worst) |  82.5 |  80.7 |  41.7 |  38.6
[0.4pt/2pt] Gold |  77.0 |  82.5 |  41.8 |  43.3
ZeroDL(Mistral) |  82.4 |  79.4 |  43.4 |  36.0
ZeroDL(GPT3.5) |  73.3 |  79.1 |  42.8 |  42.1
Table 3:  The performance with various class labels. The best AutoL in SST-2
are [Wonderful, Bad] and the worst labels are [Irresistible, Pathetic]. In
SST-5, [Terrible, Better, Good, Extraordinary, Unforgettable] are the best
while [Awful, Better, Hilarious, Perfect, Wonderful] are the worst. GPT3.5
with ZeroDL generates only 4 classes in SST-5.

We evaluate the model performance using accuracy. To determine the predicted
class, we leverage the Class n: anchor tokens within the LLM outputs. LLMs
might not directly predict the same classes as the ground-truth labels, for
example, Class 0 means Positive in the prediction while Negative is labeled as
Class 0 in the ground-truth. We thus test all possible mapping combinations
and report the best performed mapping. However, this results in a total of
factorial of C potential mappings, so we split datasets with more than 7
classes (i.e., DBpedia and YahooAnswers333After removing the 3 smallest size
of classes: CarsAndTransportation, SocialScience, Sports) into 2 subsets Front
(F) and Back (B) to avoid out-of-memory.

##  5 Results

Table 1 reports the performance of our method. Interestingly, ZeroDL achieves
even better performance than models provided with ground-truth (i.e., Gold)
class labels on several datasets. This suggests that ZeroDL might uncover
richer or more nuanced class structures within the data compared with the pre-
defined labels. Our method demonstrates comparable performance to K-Means
clustering that utilizes LLM embeddings444However, llm2vec involves additional
training steps., outperforming on tasks with relatively smaller datasets.
ZeroDL achieves this by flexible zero-shot prompting. Table 8 in the Appendix
shows the importance of the constraints utilized by ZeroDL with detailed
examples.

Table 3 investigates the significance of class labels in text clustering
tasks. We explore the performance of mistral-7b-instruct-v0.2 using class
labels suggested by AutoL Gao et al. (2021) designed for prompt-based model
fine-tuning. These labels represent a curated selection. We also investigate
the class labels generated by gpt-3.5-turbo. The results demonstrate that
clustering performance is generally higher when using manually selected labels
compared with the original dataset labels. This suggests that carefully chosen
labels can significantly improve clustering outcomes. In the context, ZeroDL
performs particularly well on SST-5, implying that the critical role of class
labels in text clustering and the potential of ZeroDL to capitalize on
informative class labels automatically.

Table 2 shows the examples of class labels generated by ZeroDL. Notably, these
labels provide richer explanations for the classifications compared with the
original ground-truth labels555The generation of class description might
depend on datasets and LLMs; Llama-3 usually does not make it.. Table 6 in the
Appendix delves deeper into the data points classified into newly emerged
classes, such as "Ambiguous Sentiment" and "Mixed Sentiment," which ZeroDL
might uncover based on the data.

ZeroDL involves a trade-off in computational cost. To investigate this aspect,
we measure the performance changes based on the amount of input data used (see
Table 5 in the Appendix). The results indicate that using only 10% of the data
yields plausible performance but it leads to inconsistency in the model
performances, considering increased standard deviation.

##  6 Conclusion

We introduce ZeroDL, a novel approach to contextualize LLM tasks for a given
LLM. ZeroDL employs open-ended zero-shot inference and output aggregation to
learn data distributions. We demonstrate its effectiveness, showing
competitive performances against embedding-based clustering methods and
superior performance than ground-truth labels in some cases. Beyond its
clustering capabilities, ZeroDL offers the generation of informative class
labels that provide deeper insights into LLMs.

##  7 Limitations

### Prompt Dependency and Heuristics.

ZeroDL relies on carefully designed prompts to guide LLMs towards effective
clustering. While our focus was on using simple and intuitive prompts, prompt
selection can potentially influence the model’s behavior and introduce biases.
Future work could explore more sophisticated prompt engineering techniques to
further enhance ZeroDL’s performance.

### Experiments with Diverse LLMs and Prompts.

While we acknowledge the computational limitations (and price) of ZeroDL,
investigating its behavior with a wider range of LLMs (including commercial
models like GPT-4, Claude, and Gemini) and prompt templates could provide
valuable insights into the generalizability and robustness of the approach.

### Lower than State-of-the-Art Performance.

Achieving state-of-the-art performance is not the sole focus of ZeroDL but it
offers a valuable framework in understanding data distributions with zero-shot
inference via LLMs. By addressing the limitations mentioned above, ZeroDL has
the potential to become a powerful and versatile tool not only for text
clustering but data exploration.

### Expensive Computational Cost in Inferences.

Although ZeroDL have an alternative approach to reduce computational burden
through data sampling, effectively sampling data to generate appropriate class
labels remains a challenge. The technique within the framework presents a
valuable future direction.

## References

  * BehnamGhader et al. (2024) Parishad BehnamGhader, Vaibhav Adlakha, Marius Mosbach, Dzmitry Bahdanau, Nicolas Chapados, and Siva Reddy. 2024.  Llm2vec: Large language models are secretly powerful text encoders.  _arXiv preprint arXiv:2404.05961_.
  * Brown et al. (2020) Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. 2020.  Language models are few-shot learners.  _Advances in neural information processing systems_ , 33:1877–1901.
  * Chang et al. (2008) Ming-Wei Chang, Lev-Arie Ratinov, Dan Roth, and Vivek Srikumar. 2008.  Importance of semantic representation: Dataless classification.  In _AAAI_ , volume 2, pages 830–835.
  * Chung et al. (2024) Hyung Won Chung, Le Hou, Shayne Longpre, Barret Zoph, Yi Tay, William Fedus, Yunxuan Li, Xuezhi Wang, Mostafa Dehghani, Siddhartha Brahma, et al. 2024.  Scaling instruction-finetuned language models.  _Journal of Machine Learning Research_ , 25(70):1–53.
  * Devlin et al. (2019) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019.  BERT: Pre-training of deep bidirectional transformers for language understanding.  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)_ , pages 4171–4186, Minneapolis, Minnesota. Association for Computational Linguistics.
  * Gao et al. (2021) Yanjun Gao, Ting-Hao Huang, and Rebecca J. Passonneau. 2021.  Learning clause representation from dependency-anchor graph for connective prediction.  In _Proceedings of the Fifteenth Workshop on Graph-Based Methods for Natural Language Processing (TextGraphs-15)_ , pages 54–66, Mexico City, Mexico. Association for Computational Linguistics.
  * Jiang et al. (2023) AQ Jiang, A Sablayrolles, A Mensch, C Bamford, DS Chaplot, D de las Casas, F Bressand, G Lengyel, G Lample, L Saulnier, et al. 2023.  Mistral 7b (2023).  _arXiv preprint arXiv:2310.06825_.
  * Kojima et al. (2022) Takeshi Kojima, Shixiang Shane Gu, Machel Reid, Yutaka Matsuo, and Yusuke Iwasawa. 2022.  Large language models are zero-shot reasoners.  _Advances in neural information processing systems_ , 35:22199–22213.
  * Kwon et al. (2023) Woosuk Kwon, Zhuohan Li, Siyuan Zhuang, Ying Sheng, Lianmin Zheng, Cody Hao Yu, Joseph E. Gonzalez, Hao Zhang, and Ion Stoica. 2023.  Efficient memory management for large language model serving with pagedattention.  In _Proceedings of the ACM SIGOPS 29th Symposium on Operating Systems Principles_.
  * Lehmann et al. (2015) Jens Lehmann, Robert Isele, Max Jakob, Anja Jentzsch, Dimitris Kontokostas, Pablo N Mendes, Sebastian Hellmann, Mohamed Morsey, Patrick Van Kleef, Sören Auer, et al. 2015.  Dbpedia–a large-scale, multilingual knowledge base extracted from wikipedia.  _Semantic Web_ , 6(2):167–195.
  * Maas et al. (2011) Andrew L. Maas, Raymond E. Daly, Peter T. Pham, Dan Huang, Andrew Y. Ng, and Christopher Potts. 2011.  Learning word vectors for sentiment analysis.  In _Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies_ , pages 142–150, Portland, Oregon, USA. Association for Computational Linguistics.
  * Meta (2024) Meta. 2024.  Introducing meta llama 3: The most capable openly available llm to date.  https://ai.meta.com/blog/meta-llama-3/.
  * Min et al. (2022) Sewon Min, Xinxi Lyu, Ari Holtzman, Mikel Artetxe, Mike Lewis, Hannaneh Hajishirzi, and Luke Zettlemoyer. 2022.  Rethinking the role of demonstrations: What makes in-context learning work? In _Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing_ , pages 11048–11064, Abu Dhabi, United Arab Emirates. Association for Computational Linguistics.
  * Mizrahi et al. (2023) Moran Mizrahi, Guy Kaplan, Dan Malkin, Rotem Dror, Dafna Shahaf, and Gabriel Stanovsky. 2023.  State of what art? a call for multi-prompt llm evaluation.  _arXiv preprint arXiv:2401.00595_.
  * OpenAI (2023) OpenAI. 2023.  Gpt-4 technical report.
  * Ouyang et al. (2022) Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, et al. 2022.  Training language models to follow instructions with human feedback.  _Advances in neural information processing systems_ , 35:27730–27744.
  * Perez et al. (2021) Ethan Perez, Douwe Kiela, and Kyunghyun Cho. 2021.  True few-shot learning with language models.  _Advances in neural information processing systems_ , 34:11054–11070.
  * Petukhova et al. (2024) Alina Petukhova, Joao P Matos-Carvalho, and Nuno Fachada. 2024.  Text clustering with llm embeddings.  _arXiv preprint arXiv:2403.15112_.
  * Radford et al. (2019) Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, Ilya Sutskever, et al. 2019.  Language models are unsupervised multitask learners.  _OpenAI blog_ , 1(8):9.
  * Socher et al. (2013) Richard Socher, Alex Perelygin, Jean Wu, Jason Chuang, Christopher D Manning, Andrew Y Ng, and Christopher Potts. 2013.  Recursive deep models for semantic compositionality over a sentiment treebank.  In _Proceedings of the 2013 conference on empirical methods in natural language processing_ , pages 1631–1642.
  * Wei et al. (2022) Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoc V Le, Denny Zhou, et al. 2022.  Chain-of-thought prompting elicits reasoning in large language models.  _Advances in neural information processing systems_ , 35:24824–24837.
  * Wolf et al. (2020) Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Remi Louf, Morgan Funtowicz, Joe Davison, Sam Shleifer, Patrick von Platen, Clara Ma, Yacine Jernite, Julien Plu, Canwen Xu, Teven Le Scao, Sylvain Gugger, Mariama Drame, Quentin Lhoest, and Alexander Rush. 2020.  Transformers: State-of-the-art natural language processing.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing: System Demonstrations_ , pages 38–45, Online. Association for Computational Linguistics.
  * Yoo et al. (2022) Kang Min Yoo, Junyeob Kim, Hyuhng Joon Kim, Hyunsoo Cho, Hwiyeol Jo, Sang-Woo Lee, Sang-goo Lee, and Taeuk Kim. 2022.  Ground-truth labels matter: A deeper look into input-label demonstrations.  In _Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing_ , pages 2422–2437, Abu Dhabi, United Arab Emirates. Association for Computational Linguistics.
  * Zhang et al. (2015) Xiang Zhang, Junbo Zhao, and Yann LeCun. 2015.  Character-level convolutional networks for text classification.  In _Advances in neural information processing systems_ , pages 649–657.

##  Appendix A Appendix

|  #Train |  #Valid |  #Test |  #Class |  Pre-defined ClassTitle
---|---|---|---|---|---
IMDB |  25,000 |  3,750 |  25,000 |  2 |  Negative, Positive
SST-2 |  9,645 |  1,101 |  2,210 |  2 |  Negative, Positive
SST-5 |  9,645 |  1,101 |  2,210 |  5 |  Very Negative, Negative, Neutral, Positive, Very Positive
YelpReviews |  650,000 |  97,500 |  49,999 |  5 |  Very Negative, Negative, Neutral, Positive, Very Positive
AGNews |  120,000 |  18,000 |  7,600 |  4 |  World, Sports, Business, Sci/Tech
DBpedia(F) |  280,000 |  41,939 |  35,000 |  7 |  Company, EducationalInstitution, Artist, Athlete, OfficeHolder, MeanOfTransportation, Building
DBpedia(B) |  280,000 |  42,213 |  35,000 |  7 |  NaturalPlace, Village, Animal, Plant, Album, Film, WrittenWork
Yahoo(F) |  59,518 |  8,879 |  10,489 |  7 |  ArtsAndHumanities, BeautyAndStyle, BusinessAndFinance, ComputersAndInternet, ConsumerElectronics, EducationAndReference, EntertainmnentAndMusic
Yahoo(B) |  59,493 |  8,973 |  10,514 |  7 |  FoodAndDrink, GamesAndRecreation, Health, HomeAndGarden, Pets, PregnancyAndParenting, SocietyAndCulture

Table 4:  Data information used in the experiments.

[C-T] |  IMDB |  SST-2 |  SST-5 |  YRev |  AGNew |  DBp(F) |  DBp(L) |  Yah(F) |  Yah(L) |  Macro |  Micro
---|---|---|---|---|---|---|---|---|---|---|---
All |  85.3 |  82.4 |  43.4 |  51.6 |  75.4 |  64.0 |  73.3 |  47.2 |  69.4 |  65.8 |  65.1
(std) |  3.40 |  3.67 |  2.93 |  1.35 |  2.23 |  3.17 |  3.82 |  1.02 |  2.65 |  |
1% |  75.2 |  70.7 |  38.3 |  51.1 |  - |  48.9 |  37.9 |  23.7 |  17.2 |  45.4 |  47.8
(std) |  23.01 |  13.47 |  6.17 |  1.30 |  - |  10.51 |  22.91 |  1.82 |  2.50 |  |
5% |  92.9 |  82.4 |  45.8 |  52.1 |  - |  59.2 |  58.5 |  35.2 |  51.7 |  59.7 |  60.1
(std) |  0.30 |  2.34 |  2.78 |  1.64 |  - |  6.77 |  7.37 |  9.03 |  14.15 |  |
10% |  91.9 |  82.0 |  35.0 |  50.3 |  - |  67.2 |  68.6 |  37.3 |  57.1 |  61.2 |  63.5
(std) |  0.82 |  3.17 |  4.45 |  3.47 |  - |  6.35 |  3.27 |  2.47 |  6.24 |  |
[T-C] |  IMDB |  SST-2 |  SST-5 |  YRev |  AGNew |  DBp(F) |  DBp(L) |  Yah(F) |  Yah(L) |  Macro |  Micro
All |  92.2 |  79.4 |  36.0 |  48.2 |  81.0 |  62.2 |  78.4 |  51.8 |  73.4 |  67.0 |  66.4
(std) |  2.34 |  5.12 |  3.84 |  3.22 |  1.81 |  4.65 |  7.14 |  1.07 |  1.91 |  |
1% |  76.1 |  78.3 |  39.4 |  50.0 |  - |  49.3 |  34.3 |  21.0 |  17.2 |  45.7 |  46.9
(std) |  23.88 |  6.01 |  5.17 |  2.48 |  - |  13.03 |  19.56 |  3.67 |  2.50 |  |
5% |  93.3 |  81.0 |  41.7 |  48.4 |  - |  55.3 |  67.9 |  56.3 |  55.7 |  62.5 |  61.7
(std) |  0.93 |  2.59 |  4.09 |  4.98 |  - |  1.84 |  4.28 |  6.09 |  12.68 |  |
10% |  92.7 |  74.2 |  36.9 |  49.3 |  - |  63.2 |  75.8 |  41.8 |  64.6 |  62.3 |  64.6
(std) |  1.77 |  13.36 |  6.03 |  5.98 |  - |  6.53 |  6.57 |  4.96 |  3.44 |  |

Table 5:  ZeroDL performances according to the number of training data. ZeroDL
fails to find exact number of clusters in AGNews dataset.

Predicted | Gold | Example
---|---|---
Mixed Sentiment: (...) | VeryNeg |  It ’s hard not to feel you ’ve just watched a feature-length video game with some really heavy back story .
Neg | But it pays a price for its intricate intellectual gamesmanship .
Neutral |  The appearance of Treebeard and Gollum ’s expanded role will either have you loving what you ’re seeing, or rolling your eyes .
Pos |  An utterly compelling ‘ who wrote it ’ in which the reputation of the most famous author who ever lived comes into question .
VeryPos | … a roller-coaster ride of a movie
Ambiguous Sentiment: (...) | VeryNeg |  It ’s difficult to say whether The Tuxedo is more boring or embarrassing – I ’m prepared to call it a draw .
Neg |  Like most Bond outings in recent years , some of the stunts are so outlandish that they border on being cartoonlike .
Neutral | Effective but too-tepid biopic
Pos | But he somehow pulls it off .
VeryPos |  Emerges as something rare , an issue movie that ’s so honest and keenly observed that it does n’t feel like one .

Table 6:  Example of data predicted to newly generated classes in SST-5.
Randomly selected.

3 Data | Method | ClassLabels
---|---|---
3 IMDB | ZeroDL |  |  Negative Sentiment: The list also includes various expressions of negative sentiment towards movies, films, shows, and documentaries. Some examples include (…)
---
Positive Sentiment: The list includes various expressions of positive
sentiment towards movies, films, shows, and documentaries. Some examples
include (…)
Gold |  |  Negative, Positive
---
SST-2 | ZeroDL |  |  Positive Sentiment: All the sentiment labels that express a positive sentiment towards the movie, film, documentary, or subject. For example, (…)
---
Negative or Neutral Sentiment: All the sentiment labels that do not express a
positive sentiment towards the movie, film, documentary, or subject. For
example, (…)
Gold |  |  Negative, Positive
---
Yelp Rev | ZeroDL |  |  Negative Sentiment: This class includes sentences expressing negative sentiments towards a place, food, or experience. Examples include (…)
---
Very Positive Sentiment: This class includes sentences expressing highly
positive sentiments towards a place, food, or experience. Examples include (…)
Mixed Sentiment: This class includes sentences expressing mixed sentiments
towards a place, food, or experience. Examples include (…)
Neutral Sentiment: This class includes sentences expressing neutral sentiments
towards a place, food, or experience. Examples include (…)
Positive Sentiment: This class includes sentences expressing positive
sentiments towards a place, food, or experience. Examples include (…)
Gold |  |  Very Negative, Negative, Neutral, Positive, Very Positive
---
DBp (F) | ZeroDL |  |  Aviation and Transportation: This class includes topics related to aviation, aerospace technology, military history, maritime history, and transportation.
---
Business and Economy: This class includes topics related to business, finance,
industries, companies, and economics.
Sports and Biographies: This class includes topics related to sports,
athletes, and their biographies.
Politics and Government: This class includes topics related to politics,
government, elections, and specific political parties.
Education: This class includes topics related to education, universities,
schools, and specific educational institutions.
History and Architecture: This class includes topics related to history,
architecture, historic sites, castles, and landmarks.
Art and Entertainment: This class includes topics related to art, music,
entertainment, and specific artists or record labels.
Gold |  |  Company, EducationalInstitution, Artist, Athlete, OfficeHolder, MeanOfTransportation, Building
---
DBp (B) | ZeroDL |  |  Science and Technology: This class includes topics related to paleontology, geology, volcanology, space exploration, and academic journals.
---
Music and Entertainment: This class includes topics related to music, album
releases, jazz music, heavy metal music, hip hop music, and entertainment.
Geography and Hydrology: This class includes topics related to geography,
hydrology, rivers, water bodies, and water resources.
Botany and Plant Sciences: This class includes topics related to botany,
horticulture, plant taxonomy, plant conservation, and endangered species.
Literature and Books: This class includes topics related to literature,
novels, fiction, mystery and crime fiction, and academic publications.
Zoology and Entomology: This class includes topics related to zoology,
entomology, moths, butterflies, fish species, and arachnids.
Film and Television: This class includes topics related to film, cinema,
movies, movie reviews, Bollywood, and television.
Gold |  |  NaturalPlace, Village, Animal, Plant, Album, Film, WrittenWork
---
Yah (F) | ZeroDL |  |  Personal Finance and Economics: Topics related to personal finance, credit scores, debt management, taxes, and economics.
---
Health and Wellness: Topics related to health, medicine, fitness, nutrition,
and wellness.
Pop Culture and Entertainment: Topics related to music, movies, TV shows,
books, art, and entertainment.
Technology and Computing: Topics related to computers, technology, software,
internet, telecommunications, and mobile phones.
Miscellaneous: Topics that do not fit neatly into any of the above categories,
such as philosophy, religion, science, and humor.
Fashion and Beauty: Topics related to fashion, clothing, makeup, cosmetics,
hair care, and beauty.
Education and Careers: Topics related to education, academic programs,
scholarships, student loans, careers, and employment.
Gold |  |  ArtsAndHumanities, BeautyAndStyle, BusinessAndFinance, ComputersAndInternet, ConsumerElectronics, EducationAndReference, EntertainmnentAndMusic
---
Yah (B) | ZeroDL |  |  Food and Cooking: This class includes topics related to various cuisines, recipes, food items, and cooking techniques.
---
Home Improvement and DIY: This class includes topics related to home repair,
renovation, decorating, gardening, and DIY projects.
Miscellaneous: This class includes topics that do not fit neatly into any of
the above categories, such as politics, education, art, and entertainment.
Technology and Gaming: This class includes topics related to video games,
computer hardware, software, technology, and internet culture.
Health and Wellness: This class includes topics related to physical and mental
health, nutrition, dieting, weight loss, fitness, exercise, and medical
conditions.
Animals and Pets: This class includes topics related to various animals, pet
care, animal rights, and wildlife.
Religion and Philosophy: This class includes topics related to various
religions, theology, philosophy, and spirituality.
Gold |  |  FoodAndDrink, GamesAndRecreation, Health, HomeAndGarden, Pets, PregnancyAndParenting, SocietyAndCulture
---
3 |  |

Table 7: Additional examples of generated class labels. Class title is marked
as bold and its description is colored as gray.

3 Data | TaskType | Generated Class Labels (Descriptions are omitted)
---|---|---
3 IMDB | sentiment |  |  Negative, Very Positive, Highly Negative, Mixed, Neutral-Positive, Positive, Highly Positive, Neutral-Negative, Extremely Negative, Neutral; [Total 10]
---
topic |  |  Film and Television Influence on Business, Film and Television Influence on Politics, Film and Television Production Companies, Film and Television Influence on Art, Film and Television Productions, Film Analysis or Review, Film and Television Influence on Society and Culture, Film and Television Influence on Technology, Film and Television Recommendations, Film and Television Awards, Film and Television, Film and Television Genres, Film and Television Influence on Society, Film and Television Marketing, Movie Reviews or Film Criticism, Film and Television Critics, Film and Television Technologies, Film and Television Festivals, Film or Media Criticism, Film and Television History, Film and Television Technology Trends, Film and Television Education, Film and Television Influence on Entertainment, Film and Television Influence on Education, Personal Opinion or Review, Film and Television Industry, Film and Television Distribution; [Total 27]
---
SST | sentiment |  |  The text expresses a negative sentiment towards the subject being described, The text expresses a negative or sad sentiment towards the film, The text expresses a negative or sad sentiment, The text has a negative tone, The text expresses a negative or cautionary sentiment, The text expresses a negative or slightly negative sentiment, Negative Sentiment, The text expresses a negative or slightly negative sentiment towards the film, The text expresses a negative sentiment, The text expresses a negative sentiment towards the movie being described, The text has a negative sentiment; [Total 11]
---
topic |  |  Literature and Writing, Media and Entertainment, Mental Health and Psychology, Travel and Adventure, Film and Television, Family and Relationships, Science and Technology, Food and Cooking, Performing Arts, Sports, Education and Learning, Business and Finance, Greetings and Open-Ended Texts, Entertainment; [Total 14]
---
Yelp Rev | sentiment |  |  Positive Sentiment, Highly Negative Sentiment, Neutral to Positive Sentiment, Negative Sentiment, Mixed Sentiment, Neutral Sentiment, Very Positive Sentiment, Neutral to Negative Sentiment; [Total: 8]
---
topic |  |  Automotive, Environment or Nature, Legal or Law, Customer Service or Business, Nightlife or Entertainment, Education or Training, Sports or Fitness, Discrimination or Racism, Religion or Spirituality, Technology or Gadgets, Health or Medical, Travel or Tourism, Education or Learning, Beauty or Personal Care, Customer Reviews or Testimonials, Politics or Government, Food or Cooking, Food or Beverage, Shopping or Retail, Home Improvement or Construction, Science or Technology, Real Estate or Housing, Food Safety or Food Poisoning, Entertainment or Leisure, Arts or Culture, Personal Care or Beauty, Business or Economy, Personal Experiences, Dining Experience or Food Review; [Total 29]
---
AG News | sentiment |  |  Negative: 12 expressions that contain negative sentiment, Positive: 25 expressions that contain positive sentiment, Negative: 12, Sentiment not clear: 3, Mixed: 11 expressions that contain a mix of positive and negative sentiment, Positive: 25, Neutral: 33, Neutral: 33 expressions that do not contain any clear positive or negative sentiment, Sentiment not clear: 3 expressions that do not provide enough context to determine a clear sentiment, Mixed: 11; [Total 10]
---
topic |  |  Same Result with Table 2
---
DBp (F) | sentiment |  |  Neutral, Positive, Negative; [Total 3]
---
topic |  |  Baseball, Aviation, Sports and Biographies, History, Aircraft, Soccer or Football, People and Biographies, Ice Hockey, Education, American Football, General, Aircraft Design, Music or Entertainment, Higher Education or Universities, Healthcare or Hospitals, Football or Soccer; [Total 15]
---
DBp (B) | sentiment |  |  Ambiguous, Neutral, Positive, Romantic, Negative, Mixed, Objective; [Total 6]
---
topic |  |  Botany or Biology (specifically, Plant Science or Taxonomy), Botany or Endangered Species or Conservation Biology, Botany or Horticulture, Botany or Algae, Botany or Brazilian Flora, Botany or Cacti, Botany or Mexican Flora, Botany or Tillandsia species, Botany or Orchids, Botany or Aquatic Plants, Botany or Plant Science, Botany or Tropical Plants, Botany or Hawaiian Flora, Botany or Plant Taxonomy, Botany or Palm Trees [Total 15]
---
Yah (F) | sentiment |  |  Positive, Neutral, Mixed, Informational, Negative [Total 5]
---
topic |  |  Miscellaneous (for topics that do not fit neatly into any specific category), Education and Careers, Makeup and Beauty, Gaming and Technology, Fashion and Clothing, Telecommunications, Housing and Real Estate, Music and Entertainment, Pop Culture and Entertainment, Personal Finance and Credit Scores; [Total 10]
---
Yah (B) | sentiment |  |  Neutral; [Total 1]
---
topic |  |  Health and Medical Concerns, Pop Culture and Entertainment, Mental Health and Psychology, Literature and Writing, Business and Finance, Food and Cooking, Video Games and Technology, Art and Creativity, Philosophy and Ethics, Education and Learning, Humor and Satire, Sports and Fitness, Religion and Theology, Home Improvement and DIY, Science and Technology, Travel and Adventure, Pets and Animals, Politics and Society, Pregnancy and Reproductive Health; [Total 19]
---
3 |  |

Table 8: The examples of generated class labels when no constraints are given;
we experiment with wrong task type and unlimited the number of clusters.


# Optimal Database Allocation in Finite Time with Efficient Communication and
Transmission Stopping over Dynamic Networks

Apostolos I. Rikos, Christoforos N. Hadjicostis, and Karl H. Johansson
Apostolos I. Rikos and K. H. Johansson are with the Division of Decision and
Control Systems, KTH Royal Institute of Technology, SE-100 44 Stockholm,
Sweden. They are also affiliated with Digital Futures, SE-100 44 Stockholm,
Sweden. E-mails<EMAIL_ADDRESS>N. Hadjicostis is with the
Department of Electrical and Computer Engineering, University of Cyprus, 1678
Nicosia, Cyprus. E-mail<EMAIL_ADDRESS>work was supported by the Knut
and Alice Wallenberg Foundation and the Swedish Research Council.

###### Abstract

In this paper, we focus on the problem of data sharing over a wireless
computer network (i.e., a wireless grid). Given a set of available data, we
present a distributed algorithm which operates over a dynamically changing
network, and allows each node to calculate the optimal allocation of data in a
finite number of time steps. We show that our proposed algorithm (i) converges
to the optimal solution in finite time with very high probability, and (ii)
once the optimal solution is reached, each node is able to cease transmissions
without needing knowledge of a global parameter such as the network diameter.
Furthermore, our algorithm (i) operates exclusively with quantized values
(i.e., each node processes and transmits quantized information), (ii) relies
on event-driven updates, and (iii) calculates the optimal solution in the form
of a quantized fraction which avoids errors due to quantization. Finally, we
demonstrate the operation, performance, and potential advantages of our
algorithm over random dynamic networks.

###### Index Terms:

database allocation, optimization, distributed algorithms, quantization,
dynamic network, finite time convergence

##  I Introduction

Wireless computer networks (or wireless grids) comprise of different
electronic devices (or nodes), which share their resources with other devices
in a distributed manner. Various users or devices may request access to one
device’s stored data. In order to reduce the average waiting time for users or
devices who request access, data allocation is the procedure of allocating the
available data to different nodes according to their available memory capacity
such that specific performance objectives are achieved.

In wireless computer networks, data comprise an important resource that needs
to be managed efficiently. Optimal allocation of data can heavily influence
the operational performance of the network [1]. In general, resource
allocation can be formulated as an optimization problem but solving the
optimal allocation problem over dynamic networks with quantized communication
is challenging due to the heterogeneity of the network and the nonlinear
nature of the communication constraints. Centralized solutions consider
gathering the available data to a central scheduler; however, these solutions
are not ideal as they lack scalability and they impose heavy computational and
storage requirements on the central scheduler. For this reason, there has been
interest towards distributed algorithms that solve the optimal allocation
problem [2, 3, 4, 5].

Distributed optimization has received significant attention recently due to
its wide variety of applications [6, 7, 8, 9, 10, 11, 12, 13, 14]. Most works
in the current literature assume that network devices process and exchange
real values and are able to reach asymptotic convergence within some error [2,
5]. In practical applications of wireless computer networks, devices need to
exchange information messages with finite length (i.e., quantized messages)
which allows for a more efficient usage of the available network resources
(e.g., energy, processing power, etc.). Also, they need to operate over
networks which may be dynamic due to changes over the sensing radius of the
various devices [3, 4]. Additionally, in order to preserve available energy
resources, it is desirable for devices to converge in finite time and to stop
transmitting once convergence has been achieved [2, 4]. In this paper we
propose an algorithm that combines all previously mentioned characteristics:
it solves the optimal allocation problem over dynamic networks in finite time,
while exhibiting transmission stopping capabilities.

Main Contributions. We focus on the problem of data sharing over a wireless
computer network (i.e., a wireless grid). We aim to balance the data storage
between nodes by distributively allocating the available data per available
memory in the network. We consider the realistic scenario where nodes process
and exchange quantized information. We also consider that various changes of
each node’s sensing radius result in dynamically changing connections in the
communication network. Our algorithm is analyzed for optimal data allocation
over a wireless computer network. In this scenario, we want to reduce the
average waiting time for users or devices who request access to the stored
data. However, please note that the proposed algorithm could be adopted in a
wide variety of other related applications. The main contributions of the
paper are the following.

  * •

We present a distributed algorithm which solves the optimal data allocation
problem over a dynamic network; see Algorithm 1.

  * •

We show that our algorithm converges in a finite number of time steps, and
each node is able to calculate the exact solution without introducing errors
due to quantization; see Section IV-B.

  * •

Once our algorithm converges to the optimal solution, each node ceases
transmissions without needing knowledge of a global network parameter (e.g.,
the diameter of the network). Note that this allows our algorithm to require
no reinitialization when there is a change over the network (e.g., when a node
enters or leaves the network or when the diameter changes); see Section IV-A.

  * •

We analyze the convergence time of the algorithm and show that it relies on
the time-varying connectivity (which is determined by the time needed to
communicate among pairs of nodes), rather than the size of the network; see
Theorem 1.

  * •

We present simulations of our algorithm where we show its finite time
convergence to the exact solution and its transmission stopping capabilities;
see Section V.

The operation of our proposed algorithm relies on each node’s ability to (i)
directly transmit a set of values, (ii) broadcast its state, and (iii)
remember the sets of nodes which have received the broadcast transmissions.
Initially, each node broadcasts its state, and also remembers the set of nodes
which received the initial broadcast. If the dynamic network changes and a new
neighboring node appears (which did not receive the current state), then the
corresponding node broadcasts again its state and remembers also the new
neighboring node. However, if a node’s state changes, (i) it forgets the set
of nodes which received the previous state values, (ii) broadcast its new
state, and (iii) remembers only nodes which have received the new state. This
allows our proposed algorithm to exhibit finite time convergence and
transmission stopping when operating over dynamically changing communication
networks.

Unlike our work in this paper, most of the current literature comprises of
algorithms which operate with real values and converge asymptotically within
some error [2, 5]. Our paper, along with [4, 3], aims to pave the way for
finite time algorithms, which operate solely with quantized values to address
resource allocation problems. To the authors knowledge, the proposed algorithm
is the first algorithm in the current literature which guarantees finite time
convergence and transmission stopping for the case where the underlying
network is dynamic without needing knowledge of a global parameter such as the
diameter of the network (e.g., see [4]).

##  II NOTATION AND BACKGROUND

The sets of real, rational, integer and natural numbers are denoted by
$\mathds{R},\mathds{Q},\mathds{Z}$ and $\mathds{N}$, respectively. The symbol
$\mathds{Z}_{+}$ denotes the set of nonnegative integers. For any real number
$a\in\mathds{R}$, the floor $\lfloor a\rfloor$ denotes the greatest integer
less than or equal to $a$ while the ceiling $\lceil a\rceil$ denotes the least
integer greater than or equal to $a$.

Graph-Theoretic Notions. Consider a dynamic network of $n$ ($n\geq 2$) nodes
communicating only with their immediate neighbors. The communication topology
can be captured by a dynamic undirected graph, called dynamic communication
graph. A dynamic graph is defined as
$\mathcal{G}[k]=(\mathcal{V},\mathcal{E}[k])$, where
$\mathcal{V}=\\{v_{1},v_{2},\dots,v_{n}\\}$ is the set of nodes and
$\mathcal{E}[k]\subseteq\mathcal{V}\times\mathcal{V}-\\{(v_{j},v_{j})\ |\
v_{j}\in\mathcal{V}\\}$ is the set of edges (self-edges excluded). An edge
from node $v_{i}$ to node $v_{j}$ is denoted by
$m_{ji}\triangleq(v_{j},v_{i})\in\mathcal{E}[k]$, and captures the fact that
node $v_{j}$ and node $v_{i}$ can exchange information ($v_{j}$ can transmit
to $v_{i}$ and $v_{i}$ can transmit to $v_{j}$) at time step $k$. Note here
that if $(v_{j},v_{i})\in\mathcal{E}[k]$ then
$(v_{i},v_{j})\in\mathcal{E}[k]$. At time step $k$, the subset of nodes that
can directly transmit information to node $v_{j}$ is called the set of
neighbors of $v_{j}$ and is represented by
$\mathcal{N}_{j}[k]=\\{v_{i}\in\mathcal{V}\;|\;(v_{j},v_{i})\in\mathcal{E}[k]\\}$.
The cardinality of $\mathcal{N}_{j}[k]$ at time step $k$, is called the degree
of $v_{j}$ and is denoted by $\mathcal{D}_{j}[k]=|\mathcal{N}_{j}^{-}[k]|$.
Given a collection of graphs $\mathcal{G}[k]=(\mathcal{V},\mathcal{E}[k])$ for
$k=1,2,...,m$, where $m\in\mathds{N}$, the union graph is defined as
$\mathcal{G}^{1,2,...,m}_{d}=(\mathcal{V},\cup_{k=1}^{m}\mathcal{E}[k])$. A
collection of graphs is said to be jointly connected, if its corresponding
union graph $\mathcal{G}^{1,2,...,m}$ forms a connected graph (i.e., for each
pair $v_{j},v_{i}\in\mathcal{V}$, $v_{j}\neq v_{i}$, there exists a path111A
path from $v_{i}$ to $v_{j}$ exists between time steps $k,k+1,...,k+\tau$ if
we can find a sequence of vertices $v_{i}\equiv
v_{l_{0}},v_{l_{1}},\dots,v_{l_{t}}\equiv v_{j}$ such that
$(v_{l_{\tau+1}},v_{l_{\tau}})\in\mathcal{E}[k+\tau]$ for
$\tau=0,1,\dots,t-1$. from $v_{i}$ to $v_{j}$).

Node Operation. The operation of each node $v_{j}\in\mathcal{V}$ respects the
quantization of information flow. At time step $k\in\mathds{Z}_{+}$ (where
$\mathds{Z}_{+}$ is the set of nonnegative integers), each node $v_{j}$
maintains the mass variables $y_{j}[k]\in\mathds{Z}$ and
$z_{j}[k]\in\mathds{Z}_{+}$, which are used to communicate with other nodes by
either transmitting or receiving messages; the state variables
$y^{s}_{j}[k]\in\mathds{Z}$, $z^{s}_{j}[k]\in\mathds{Z}_{+}$ and
$q_{j}^{s}[k]=\frac{y_{j}^{s}[k]}{z_{j}^{s}[k]}$, which are used to store the
received messages and calculate result of the optimization operation; the
transmission variables $S\\_br_{j}\in\mathds{N}$ and
$M\\_tr_{j}\in\mathds{N}$, which are used to decide whether $v_{j}$ will
broadcast its state variables or transmit its mass variables via a direct
transmission.

For the case where each node $v_{j}$ is required to perform a direct
transmission, we assume that $v_{j}$ is aware of its out-neighbors and can
directly transmit messages to each out-neighbor separately. In the proposed
distributed algorithm, in order to randomly determine which out-neighbor to
transmit to, each node $v_{j}$ assigns a nonzero probability $b_{lj}[k]$ to
each of its edges $m_{lj}$ where $v_{l}\in\mathcal{N}_{j}[k]$ (note that there
is always a virtual self-edge which means that the probability assigned to the
self-edge is nonzero). For every node, this probability assignment can be
captured by an $n\times n$ column stochastic matrix
$\mathcal{B}[k]=[b_{lj}[k]]$. A simple choice is to set these probabilities to
be equal, i.e.,

$\displaystyle
b_{lj}[k]=\left\\{\begin{array}[]{ll}\frac{1}{\mathcal{D}_{j}^{+}[k]+1},&\mbox{if
$l=j$ or $v_{l}\in\mathcal{N}_{j}[k]$,}\\\
0,&\mbox{otherwise.}\end{array}\right.$

Each nonzero entry $b_{lj}[k]$ of matrix $\mathcal{B}[k]$ represents the
probability of node $v_{j}$ transmitting towards out-neighbor
$v_{l}\in\mathcal{N}_{j}[k]$ through the edge $m_{lj}$.

Modelling of Wireless Grid and Database. A wireless grid is modeled as a set
of $\mathcal{V}$ nodes (or wireless sensors) and each node is denoted as
$v_{i}\in\mathcal{V}$. In most data grids, all participating nodes are
interconnected with undirected communication links. Furthermore, various
changes over the sensing range of each node impose a dynamic nature to the
network topology. This means that the network topology forms a dynamic
undirected graph.

For modelling databases, we borrow notation from [4]. Specifically, the
database to be allocated in the network is $D_{dat}$. The data sets which
consists the database are $d_{j}\in D_{dat}$ (where
$j\in\\{1,\ldots,|D_{dat}|\\}$). The required memory for each data set $d_{j}$
to be stored (which is known before the optimization operation) is $\mu_{j}$.
Thus, the total required memory for database $D_{dat}$ is
$\mu\coloneqq\sum_{v_{i}\in\mathcal{V}}\mu_{j}$. The total load of data at
each node $v_{j}$, due to incoming data in the network is $l_{j}$. The time
period for which the optimization operation is executed (before the next
optimization operation) is $T_{o}$. The total memory of node $v_{j}$ is
$\nu_{j}^{\max}$. The total memory in the network is
$\nu^{\max}\coloneqq\sum_{v_{j}\in\mathcal{V}}\nu_{j}^{\max}$. The amount of
unavailable memory of node $v_{j}$ due to previously stored data is
$\delta_{j}[m]$. The total amount of unavailable memory in the network
$\delta_{\mathrm{tot}}[m]=\sum_{v_{j}\in\mathcal{V}}\delta_{j}[m]$. The amount
of available memory of node $v_{j}$ at optimization step $m$ (i.e., at time
step $mT_{o}$) is
$\nu_{j}^{\mathrm{avail}}[m]\coloneqq\nu_{j}^{\max}-\delta_{j}[m]$. The total
amount of available memory in the network is
$\nu^{\mathrm{avail}}[m]\coloneqq\sum_{v_{j}\in\mathcal{V}}\nu_{j}^{\mathrm{avail}}[m]$.

##  III Problem Formulation

Let us consider a wireless computer network modeled as a dynamic graph
$\mathcal{G}[k]=(\mathcal{V},\mathcal{E}[k])$ with $n=|\mathcal{V}|$ nodes.
Each node $v_{i}$ has a scalar quadratic local cost function
$f_{i}:\mathds{R}^{n}\mapsto\mathds{R}$ (see [8] and references therein)
defined as:

$f_{i}(z)=\dfrac{1}{2}\alpha_{i}(z-\mu_{i})^{2},$ (1)

where $\alpha_{i}>0$, $\mu_{i}\in\mathds{R}$ is the demand of node $v_{i}$ and
$z$ is a global optimization parameter which determines the data to be stored
at each node. The global cost function is the sum of every local cost function
$f_{i}$ (see (1)) in the network, i.e.,

$F(z)=\sum_{v_{i}\in\mathcal{V}}f_{i}(z).$ (2)

The main goal of the nodes is to distributively allocate the available data in
order to calculate $z^{*}$ which minimizes the global cost function in (2) and
is defined as

$\displaystyle
z^{*}=\arg\min_{z\in\mathcal{Z}}\sum_{v_{i}\in\mathcal{V}}f_{i}(z),$ (3)

where $\mathcal{Z}$ is the set of feasible values of parameter $z$. Note that
the solution $z^{*}$ in (3) can be given in closed form as:

$\displaystyle
z^{*}=\frac{\sum_{v_{i}\in\mathcal{V}}\alpha_{i}\mu_{i}}{\sum_{v_{i}\in\mathcal{V}}\alpha_{i}}.$
(4)

Also, note here that if $\alpha_{i}=1$ for all $v_{i}\in\mathcal{V}$, the
solution is the average.

The problem we present in this paper is borrowed from [2, 4], but is adjusted
in the context of data allocation over dynamic wireless computer networks.
Specifically, each node $v_{j}$ aims to calculate the optimal amount of data
to receive $w_{i}^{*}[m]$ at each optimization step $m$, which fulfills

$\displaystyle\frac{w_{i}^{*}[m]+\delta_{i}[m]}{\nu_{i}^{\max}}$
$\displaystyle=\frac{w_{j}^{*}[m]+\delta_{j}[m]}{\nu_{j}^{\max}}$ (5)
$\displaystyle=\frac{\mu[m]+\delta_{\mathrm{tot}}[m]}{\nu^{\max}},\ \forall
v_{i},v_{j}\in\mathcal{V}.$

This means that every node aims to balance its data storage (i.e., the same
percentage of stored data per available memory) during the algorithm’s
execution. In the remainder of this paper, we consider a single optimization
step (i.e., without loss of generality, we drop index $m$). From [2], in order
to fulfill (5), we need:

$\displaystyle
z^{*}=\frac{\sum_{v_{i}\in\mathcal{V}}\nu_{i}^{\max}\frac{\mu_{i}+\delta_{i}}{\nu_{i}^{\max}}}{\sum_{v_{i}\in\mathcal{V}}\nu_{i}^{\max}}=\frac{\mu+\delta_{\mathrm{tot}}}{\nu^{\max}}.$
(6)

Thus, the cost function $f_{i}(z)$ in (1) is given by

$\displaystyle
f_{i}(z)=\frac{1}{2}\nu_{i}^{\max}\left(z-\frac{\mu_{i}+\delta_{i}}{\nu_{i}^{\max}}\right)^{2}.$
(7)

This means that each node computes the optimal amount of data to store and
then it is able to find the amount of data $w_{i}^{*}$ to receive, i.e.,

$\displaystyle
w_{i}^{*}=\frac{\mu+\delta_{\mathrm{tot}}}{\nu^{\max}}\nu_{i}^{\max}-\delta_{i}.$
(8)

In our paper we aim to develop a distributed algorithm which operates over
dynamic networks and during its operation, each node $v_{j}$ does the
following:

  * •

It calculates the optimal solution $w_{j}^{*}$ in (5) at every optimization
step $m$.

  * •

It converges to the optimal solution after a finite number of time steps.

  * •

It processes and transmits quantized values.

  * •

It ceases transmissions once convergence has been achieved without having
knowledge of global parameters (for preserving the available resources of each
node).

##  IV Quantized Data Allocation Algorithm with Finite Transmission
Capabilities

In this section we present a distributed algorithm which solves the problem
described in Section III. The distributed algorithm is detailed below as
Algorithm 1 and allows each node in the network to calculate in finite time
the optimal amount of data to receive. In order to solve the finite time data
allocation problem, we make the following assumptions.

######  Assumption 1.

Let us consider an infinite sequence of undirected graphs
$\mathcal{G}[0],\mathcal{G}[1]$, $\mathcal{G}[2]$, …, $\mathcal{G}[k]$, …,
describing a dynamic graph. There is a finite window length $l\in\mathds{N}$
and an infinite sequence of time instants $t_{0}$, $t_{1}$, …, $t_{m}$, …,
where $t_{0}=0$, such that for any $m\in\mathds{Z}_{+}$, we have
$0<t_{m+1}-t_{m}<l<\infty$ and the union graph
$\mathcal{G}^{t_{m},...,t_{m+1}-1}$, is equal to the nominal undirected graph
$\mathcal{G}$ which is assumed to be connected. Furthermore, the diameter of
the connected union graph $\mathcal{G}^{t_{m},...,t_{m+1}-1}$ is denoted as
$D^{un}$ and is the longest shortest path between any two nodes
$v_{j},v_{i}\in\mathcal{V}$ (note that $D^{un}$ is also the diameter of the
nominal graph $\mathcal{G}$).

######  Assumption 2.

Each node $v_{j}$ has a unique ID. This ID is used to distinguish node $v_{j}$
from other nodes in the network.

######  Assumption 3.

The time horizon $T_{o}$ at step $m$, is chosen such that
$\mu[m]\leq\nu^{\mathrm{avail}}[m]$. This means that the total amount of data
to be allocated at a specific optimization step $m$ is smaller or equal to the
total available memory of the network.

Assumption 1 is a necessary network condition so that each node $v_{j}$ is be
able to calculate the quantized average of each node’s quantized state after a
finite number of time steps. Assumption 2 is a necessary condition in order
for each node to cease transmissions once the optimal allocation is calculated
after a finite number of time steps. Assumption 3 is a necessary condition so
that the total demand of data storage does not exceed the total available
memory in the network. Note that $T_{o}$ can be chosen appropriately to
fulfill this requirement. Furthermore, note that in case Assumption 3 does not
hold, some data will not be allocated due to the lack of available storing
memory in the system.

We now describe the main operations of Algorithm 1. The initialization
involves the following steps:

Initialization: Each node $v_{j}\in\mathcal{V}$ does the following: (i) it
initiates its mass variables, (ii) it initiates its transmission variables,
and (iii) it sets its state variables to be equal to the mass variables. Then,
it broadcasts the values of its state variables to every neighbor. Finally, it
initializes set $S_{j}$, to contain the out-neighbors to which it transmitted
its state variables at time step $k=0$.

The iteration involves the following steps:

Iteration - Step $1$. Probability Assignment and Receiving: Each node
$v_{j}\in\mathcal{V}$ assigns a nonzero probability to each of its edges
during every time step $k$. The sum of the assigned nonzero probabilities is
equal to one, during every time step $k$. Then, it receives from every
neighbor (i) the transmitted set of state variables, and (ii) the transmitted
set of mass variables (if no set of mass variables is received from a specific
neighbor, $v_{j}$ assumes it received mass variables equal to zero from this
neighbor).

Iteration - Step $2$. Transmission Conditions According to Mass and State
Variables: If node $v_{j}$ received at least a set of mass variables or state
variables during Iteration - Step $1$, it checks the following conditions:

  * $\bullet$

If the received set of state variables is “greater” (in the way clarified
later in this section) than the current set of state variables, it sets its
state variables to be equal to the received (greater) set of state variables
and decides to broadcast its updated state variables.

  * $\bullet$

If the stored set of mass variables is greater than the state variables it
sets its state variables equal to the mass variables and decides to broadcast
its updated state variables.

  * $\bullet$

If the set of state variables is greater than the set of mass variables and
the fraction of its mass variables is not equal to the fraction of its state
variables, then it decides to directly transmit its mass variables to a
randomly chosen neighbor.

Then, if it decided to broadcast its state variables, it updates the stored
set $S_{j}$ to be equal to the current set of out-neighbors (in order to
remember which neighbors received the current state variables).

Iteration - Step $3$. Transmission Conditions According to Dynamic Network: At
each time step $k$, each node $v_{j}$ checks whether the current set of
neighbors is not included in the stored set $S_{j}$. Note here that the stored
set $S_{j}$ denotes the neighbors which have received (or will receive) the
current set of state variables. In case, there is one (or multiple)
neighbor(s) who is (are) not included in the set $S_{j}$, node $v_{j}$ decides
to broadcast its state variables so that this one neighbor (or multiple
neighbors) receives the updated set of state variables.

Iteration - Step $4$. Transmitting: Each node $v_{j}$ checks its transmission
variables. It transmits its mass variables via a direct transmission, or
broadcasts its state variables. Then, it sets its tramsmission variables equal
to zero and repeats the operation.

The details of the dynamic algorithm with transmission stopping capabilities
can be seen in Algorithm 1.

Algorithm 1 Optimal Data Allocation Algorithm with Efficient Communication and
Transmission Stopping

Input: A set of graphs $\mathcal{G}[k]=(\mathcal{V},\mathcal{E}[k])$ with
$n=|\mathcal{V}|$ nodes and $m[k]=|\mathcal{E}[k]|$ edges for which Assumption
1 holds.
Initialization: Each node $v_{j}\in\mathcal{V}$ does the following:

  * 1)

Sets $z_{j}[0]:=l_{j}+\delta_{j}$, $y_{j}[0]=\nu_{j}^{\max}$,
$z^{s}_{j}[0]=1$, $y^{s}_{j}[0]=y_{j}[0]$,
$q^{s}_{j}[0]=y^{s}_{j}[0]/z^{s}_{j}[0]$ and $S\\_br_{j}=0$, $M\\_tr_{j}=0$.

  * 2)

Broadcasts $z^{s}_{j}[0]$, $y^{s}_{j}[0]$ to every $v_{l}\in\mathcal{N}_{j}$.

  * 3)

Sets $S=\mathcal{N}_{j}[0]$.

Iteration: For $k=0,1,2,\dots$, each node $v_{j}\in\mathcal{V}$ does the
following:

  * 1)

Assigns a nonzero probability $b_{lj}[k]$ to each of its edges $m_{lj}$, where
$v_{l}\in\mathcal{N}_{j}[k]$, as follows

$\displaystyle
b_{lj}[k]=\left\\{\begin{array}[]{ll}\frac{1}{\mathcal{D}_{j}[k]+1},&\mbox{if
$l=j$ or $v_{l}\in\mathcal{N}_{j}[k]$,}\\\ 0,&\mbox{if $l\neq j$ and
$v_{l}\notin\mathcal{N}_{j}[k]$.}\end{array}\right.$

  * 2)

Receives $y^{s}_{i}[k]$, $z^{s}_{i}[k]$ from every
$v_{i}\in\mathcal{N}_{j}[k]$ (if no message is received, it sets
$y^{s}_{i}[k]=0$, $z^{s}_{i}[k]=0$).

  * 3)

Receives $y_{i}[k]$, $z_{i}[k]$ from each $v_{i}\in\mathcal{N}_{j}[k]$ and
sets

$y_{j}[k+1]=y_{j}[k]+\sum_{v_{i}\in\mathcal{N}_{j}[k]}w_{ji}[k]y_{i}[k],$
$z_{j}[k+1]=z_{j}[k]+\sum_{v_{i}\in\mathcal{N}_{j}[k]}w_{ji}[k]z_{i}[k],$

where $w_{ji}[k]=1$ if a message with $y_{i}[k]$, $z_{i}[k]$ is received from
in-neighbor $v_{i}$, otherwise $w_{ji}[k]=0$.

  * 4)

If $w_{ji}[k]\neq 0$ or $z^{s}_{i}[k]\neq 0$ for some
$v_{i}\in\mathcal{N}_{j}^{-}[k]$ then

    * 4a)

Calls Algorithm 1.A.

    * 4b)

Event Trigger Conditions $1$: If $S_{j}\ \cap\
\mathcal{N}_{j}^{+}[k]\neq\emptyset,$
then node $v_{j}$ sets $S\\_br_{j}=1$, and
$S_{j}=S_{j}\cup\mathcal{N}_{j}[k]$.

    * 4c)

If $M\\_tr_{j}=1$ then node $v_{j}$ chooses $v_{l}\in\mathcal{N}_{j}[k]$
randomly according to $b_{lj}[k]$ and transmits $y_{j}[k]$, $z_{j}[k]$. Then,
node $v_{j}$ sets $y_{j}[k]=0$, $z_{j}[k]=0$, $M\\_tr_{j}=0$.

    * 4d)

If $S\\_br_{j}=1$ then, node $v_{j}$ broadcasts $z^{s}_{j}[k+1]$,
$y^{s}_{j}[k+1]$ to every $v_{l}\in\mathcal{N}_{j}$. Then, it sets
$S\\_br_{j}=0$.

  * 5)

Repeats (increases $k$ to $k+1$ and goes back to Step $1$).

Output: Sets $w^{*}_{j}+\delta_{j}=(\nu_{j}^{\max}/q^{s}_{j}[k])$ and (5)
holds for every $v_{j}\in\mathcal{V}$.

Algorithm 1.A Event-Triggered Conditions for Algorithm 1 (for each node
$v_{j}$)

Input
$y^{s}_{j}[k]$, $z^{s}_{j}[k]$, $q^{s}_{j}[k]$, $y_{j}[k+1]$, $z_{j}[k+1]$,
$S\\_br_{j}$, $M\\_tr_{j}$, $S_{j}$, $\mathcal{N}_{j}[k]$, and the received
$y^{s}_{i}[k]$, $z^{s}_{i}[k]$ from every $v_{i}\in\mathcal{N}_{j}[k]$.
Execution

  * $\bullet$

Event Trigger Conditions $1$: If
Condition $(i)$: $z^{s}_{i}[k]>z^{s}_{j}[k]$, or
Condition $(ii)$: $z^{s}_{i}[k]=z^{s}_{j}[k]$ and $y^{s}_{i}[k]>y^{s}_{j}[k]$,
then node $v_{j}$ sets

$z^{s}_{j}[k+1]=\max_{v_{i}\in\mathcal{N}_{j}[k]}z^{s}_{i}[k],\ \ \text{and}$
$y^{s}_{j}[k+1]=\max_{v_{i}\in\\{v_{i^{\prime}}\in\mathcal{N}_{j}[k]|z^{s}_{i^{\prime}}[k]=z^{s}_{j}[k+1]\\}}y^{s}_{i}[k],$

and also sets $q^{s}_{j}[k+1]=\frac{y^{s}_{j}[k+1]}{z^{s}_{j}[k+1]}$, and
$S\\_br_{j}=1$.

  * $\bullet$

Event Trigger Conditions $2$: If
Condition $(i)$: $z_{j}[k+1]>z^{s}_{j}[k+1]$, or
Condition $(ii)$: $z_{j}[k+1]=z^{s}_{j}[k+1]$ and $y_{j}[k+1]>y^{s}_{j}[k+1]$,
then node $v_{j}$ sets $z^{s}_{j}[k+1]=z_{j}[k+1]$,
$y^{s}_{j}[k+1]=y_{j}[k+1]$, and
$q^{s}_{j}[k+1]=\frac{y^{s}_{j}[k+1]}{z^{s}_{j}[k+1]}$ and $S\\_br_{j}=1$.

  * $\bullet$

Event Trigger Conditions $3$: If
Condition $(i)$: $0<z_{j}[k+1]<z^{s}_{j}[k+1]$ or
Condition $(ii)$: $z_{j}[k+1]=z^{s}_{j}[k+1]$ and $y_{j}[k+1]<y^{s}_{j}[k+1]$,
then node $v_{j}$ sets $M\\_tr_{j}=1$.

  * $\bullet$

Event Trigger Conditions $4$: If $0<z_{j}[k+1]$ and

$\dfrac{y_{j}[k+1]}{z_{j}[k+1]}=\dfrac{y^{s}_{j}[k+1]}{z^{s}_{j}[k+1]},$

then node $v_{j}$ sets $M\\_tr_{j}=0$.

  * $\bullet$

Event Trigger Conditions $5$: If $S\\_br_{j}=1$
then node $v_{j}$ sets $S=\mathcal{N}_{j}[k]$.

Output
$y^{s}_{j}[k]$, $z^{s}_{j}[k]$, $q^{s}_{j}[k]$, $S\\_br_{j}$, $M\\_tr_{j}$,
$S_{j}$.

######  Remark 1.

In Definition 2, each node $v_{j}$ has a unique ID in order to cease
transmissions once the optimal allocation is calculated after a finite number
of time steps. To the authors knowledge this is the first algorithm which
operates over dynamic networks in which nodes are able to cease transmissions
without any global parameter such as the network diameter. However, note that
if nodes have knowledge of the parameter $l$ (see Definition 1), then they do
not need to have unique IDs. Specifically, every time their state variables
are updated (see Algorithm 1.A) they can broadcast their state variables for
$l$ time steps. From Definition 1, every $l$ time steps, there is a link from
node $v_{j}$ to every neighboring node. As a result, if nodes broadcast their
state variables for $l$ time steps, every neighbor will receive the updated
states at least once and the algorithm will converge to the optimal solution
in finite time.

###  IV-A Operation over Dynamic Graphs

We now analyze the functionality of Algorithm 1 over dynamic networks. We
consider the following two definitions which are important for our subsequent
development.

######  Definition 1.

Consider a set of graphs $\mathcal{G}[k]=(\mathcal{V},\mathcal{E}[k])$,
$k=0,1,2,...$, with $n=|\mathcal{V}|$ nodes and $m[k]=|\mathcal{E}[k]|$ edges
for which Assumption 1 holds. During the execution of Algorithm 1, at time
step $k_{0}$, there is at least one node $v_{j^{\prime}}\in\mathcal{V}$, for
which

$z_{j^{\prime}}[k_{0}]\geq z_{i}[k_{0}],\ \forall v_{i}\in\mathcal{V}.$ (9)

Then, among the nodes $v_{j^{\prime}}$ for which (9) holds, there is at least
one node $v_{j}$ for which

$y_{j}[k_{0}]\geq y_{l}[k_{0}],\ \text{where}\ \
v_{j},v_{l}\in\\{v_{j^{\prime}}\in\mathcal{V}\ |\ (\ref{great_z_prop1_det})\
\text{holds}\\}.$ (10)

For notational convenience we will call the pair of mass variables of node
$v_{j}$ for which (9) and (10) hold as the “leading mass” (or “leading masses”
if multiple nodes hold such a pair of values) and the pairs of mass variables
of a node $v_{l}$ for which $z_{l}[k_{0}]>0$ but (9) and (10) do not hold as
the “follower mass” (or “follower masses”).

######  Definition 2.

Consider a set of graphs $\mathcal{G}[k]=(\mathcal{V},\mathcal{E}[k])$,
$k=0,1,2,...$, with $n=|\mathcal{V}|$ nodes and $m[k]=|\mathcal{E}[k]|$ edges
for which Assumption 1 holds. During the execution of Algorithm 1, at time
step $k_{0}$, if two (or more) masses (for which $z\neq 0$) reach a node
simultaneously then we say that they “merge”. This means that the receiving
node “merges” the mass variables it receives by summing their numerators and
their denominators (according to Step $3$ of the Iteration of Algorithm 1).
This way a set of mass variables with a greater denominator is created.

The intuition behind Algorithm 1 can be described through the following three
stages.
Stage $1$: Initially every node assumes that its mass variables are the
leading mass and broadcasts its state variables. After a finite number of time
steps, the state variables of every node in the network are equal to the
leading mass (let us assume the simple scenario where until the state
variables of every node in the network are equal to the leading mass no mass
variables merged, thus the leading mass do not change).
Stage $2$: Once the state variables of every node become equal to the leading
mass, every node transmits its mass variables towards a randomly chosen
neighbor. This means that the mass variables of every node (except the node
whose mass variables are the leading mass) perform a random walk. During their
random walk, the mass variables either merge with the leading mass (which is
not transmitted), or merge between them (if they visit a common node). In the
first case, the leading mass is updated and the corresponding node broadcasts
its updated state variables. In the second case, if two mass variables visit a
common node, the node checks if the merged mass variables are now the leading
mass (note that the node’s state variables are equal to the leading mass from
Stage $1$). If the merged mass variables are the leading mass, then the
corresponding node broadcasts its state variables and stores the mass
variables (i.e., it does not transmit its mass variables). However, if the
merged mass is not the leading mass, then it is transmitted to a randomly
chosen neighbor.
Stage $3$: Once the leading mass is updated (i.e., the mass variables either
merge with the leading mass, or merge between them), the corresponding node
broadcasts its state variables. Thus, after a finite number of time steps, the
state variables of every node in the network become equal to the updated
leading mass, and then Stage $2$ is repeated.

Note here that during the operation of Algorithm 1, there is always a set of
mass variables which is the leading mass. The follower masses perform random
walks until they merge with the leading mass or they merge between them and
become the leading mass. Once the leading mass is updated (i.e., either a
follower mass merges with the leading mass or two follower masses merge
between them and become the leading mass), every node in the network receives
the updated state variables of the node whose mass variables are the leading
mass (see Stage $1$). As a result, after a finite number of time steps (i) the
leading mass becomes equal to the quantized average of the initial states,
(ii) each node sets its state variables equal to the leading mass (i.e., the
average of the initial states), and (iii) once each node’s state becomes equal
to the average of the initial states, transmissions are ceased (since there
are no more updates of the leading mass).

Comparison with Previous Works. It is important to note that Algorithm 1 is
significantly different from the optimal allocation algorithm in [4] and the
quantized average consensus algorithm in [15]. In [4] the authors present a
distributed algorithm for optimally allocating resources over a directed
communication network. The algorithm converges in finite time and exhibits a
fast convergence rate over large scale networks. However, (i) it operates over
static directed networks, (ii) its transmission stopping mechanism requires
knowledge of the diameter of the network (which is a global parameter), and
(iii) it introduces a quantization error (which is upper bounded by the size
of the quantization step) to the final calculated value, due to its operation,
which relies on communication and processing of quantized values. In [15] the
authors propose a distributed algorithm for calculating the average of the
initial states over a directed communication network. This algorithm achieves
deterministic convergence and requires a finite number of time steps upper
bounded by a polynomial function. However, its deterministic finite time
convergence requires (i) the existence of a static directed communication
network (i.e., it is not adjusted to operate over time-varying networks), and
(iii) a large number of time steps, due to its round-robin transmission
strategy. Algorithm 1 operates over dynamic undirected networks. Furthermore,
it incorporates a transmission stopping mechanism, which (i) does not require
knowledge of any global parameter of the network, and (ii) is adjusted to the
dynamic nature of the network (note here that it is the fist transmission
stopping mechanism which operates over time-varying networks). Additionally,
Algorithm 1 convergences almost surely (with probability arbitrarily close to
one) to the optimal solution due to the randomized nature of the directed
transmissions. Finally, Algorithm 1 converges to the optimal solution in
finite time without introducing a quantization error (i.e., the exact optimal
allocation value is calculated in the form of a quantized fraction).

###  IV-B Convergence of Algorithm 1

We now analyze the convergence time of Algorithm 1. We first consider Lemma 1,
mutatis mutandis, which is necessary for our subsequent development.

######  Lemma 1 ([16]).

Consider a sequence of graphs $\mathcal{G}[k]=(\mathcal{V},\mathcal{E}[k])$,
$k=0,1,2,...$, with $n=|\mathcal{V}|$ nodes, $m[k]=|\mathcal{E}[k]|$ edges, so
that Assumption 1 holds for $\mathcal{G}[k]$ over all $k$. At each time step
$k$, suppose that each node $v_{j}$ assigns a nonzero probability $b_{lj}[k]$
to each of its edges $m_{lj}[k]$, where
$v_{l}\in\mathcal{N}_{j}[k]\cup\\{v_{j}\\}$, as follows

$\displaystyle
b_{lj}=\left\\{\begin{array}[]{ll}\frac{1}{1+\mathcal{D}_{j}[k]},&\mbox{if
$l=j$ or $v_{l}\in\mathcal{N}_{j}[k]$,}\\\ 0,&\mbox{if $l\neq j$ and
$v_{l}\notin\mathcal{N}_{j}[k]$.}\end{array}\right.$

At time step $k=0$, node $v_{j}$ holds a “token” while the other nodes
$v_{l}\in\mathcal{V}-\\{v_{j}\\}$ do not. At each time step $k$, each node
$v_{j}$ transmits the “token” (if it has the token, otherwise it performs no
transmission) according to the nonzero probability $b_{lj}[k]$ it assigned to
its edges $m_{lj}[k]$. The probability $P^{D^{un}}_{DT_{i}}$ that the token is
at node $v_{i}$ after $lD^{un}$ time steps satisfies

$P^{lD^{un}}_{DT_{i}}\geq(1+\mathcal{D}_{max})^{-(lD^{un})}>0,$

where $l$ is the time window defined in Assumption 1 (for which the union
graph $\mathcal{G}^{t_{m},...,t_{m+1}-1}_{d}$ is equal to the nominal graph
$\mathcal{G}$ which is connected), and $\mathcal{D}_{max}$ is the maximum
degree of every node in the nominal graph $\mathcal{G}$.

We now consider Lemma 2, which analyzes the probability according to which a
token performing a random walk visits a specific node.

######  Lemma 2.

Consider a sequence of graphs $\mathcal{G}[k]=(\mathcal{V},\mathcal{E}[k])$,
$k=0,1,2,...$, with $n=|\mathcal{V}|$ nodes, $m[k]=|\mathcal{E}[k]|$ edges, so
that Assumption 1 holds for $\mathcal{G}[k]$ over all $k$. At each time step
$k$, suppose that each node $v_{j}$ assigns a nonzero probability $b_{lj}[k]$
to each of its edges $m_{lj}[k]$, where
$v_{l}\in\mathcal{N}_{j}[k]\cup\\{v_{j}\\}$, as follows

$\displaystyle
b_{lj}=\left\\{\begin{array}[]{ll}\frac{1}{1+\mathcal{D}_{j}[k]},&\mbox{if
$l=j$ or $v_{l}\in\mathcal{N}_{j}[k]$,}\\\ 0,&\mbox{if $l\neq j$ and
$v_{l}\notin\mathcal{N}_{j}[k]$.}\end{array}\right.$

At time step $k=0$, node $v_{j}$ holds a “token” while the other nodes
$v_{l}\in\mathcal{V}-\\{v_{j}\\}$ do not. At each time step $k$, each node
$v_{j}$ transmits the “token” (if it has the token, otherwise it performs no
transmission) according to the nonzero probability $b_{lj}[k]$ it assigned to
its edges $m_{lj}[k]$. For any probability $p_{0}$, where $0<p_{0}<1$, there
exists $k_{0}\in\mathds{Z}_{+}$, so that with probability at least $p_{0}$,
the token has visited a specific node $v_{i}$, (where $l$ is the time window
defined in Assumption 1 for which the union graph
$\mathcal{G}^{t_{m},...,t_{m+1}-1}$ is equal to the nominal graph
$\mathcal{G}$ which is connected).

###### Proof.

See Appendix A. ∎

We are now ready to present Theorem 1 which analyzes the finite time
convergence of Algorithm 1.

######  Theorem 1.

Consider a sequence of graphs $\mathcal{G}[k]=(\mathcal{V},\mathcal{E}[k])$,
$k=0,1,2,...$, with $n=|\mathcal{V}|$ nodes, $m[k]=|\mathcal{E}[k]|$ edges, so
that Assumption 1, Assumption 2, and Assumption 3 hold for $\mathcal{G}[k]$
over all $k$. Suppose that each node $v_{j}\in\mathcal{V}$ follows the
Initialization and Iteration steps as described in Algorithm 1, where
$l_{j},\delta_{j},\nu_{j}^{\max}\in\mathds{N}$ for every node
$v_{j}\in\mathcal{V}$ at time step $k=0$. During the operation of Algorithm 1,
for any probability $p_{0}^{\prime}$ (where $0<p_{0}^{\prime}<1$) there exists
$k_{0}^{\prime}\in\mathds{Z}_{+}$, so that with probability at least
$p_{0}^{\prime}$ each node $v_{j}$ is able to (i) calculate the optimal amount
of data $w^{*}_{j}$ (shown in (8)) after a finite number of time steps
$k_{0}$, and (ii) cease transmissions after calculating $w^{*}_{j}$.

###### Proof.

See Appendix B. ∎

##  V Simulation Results

In this section, we present simulation results in order to demonstrate the
operation of Algorithm 1 and its potential advantages. We focus on a random
graph of $20$ nodes and show how the nodes’ states converge to the optimal
solution. Furthermore, we show the total accumulated number of transmissions
and the number transmissions at every time step. To the best of our knowledge,
this is the first work that faces the problem of optimal resource allocation
using quantized values with transmission stopping guarantees over dynamic
networks.

Evaluation over a Dynamic Network of $20$ Nodes. The dynamic network is
comprised of $20$ nodes and the union of the dynamic networks is equal to the
nominal graph after $l=5$ time steps. The nominal graph is assumed to be
connected and has a diameter equal to $3$. At each node $v_{j}$, the total
load of data $l_{j}$ was generated via a random distribution uniformly picked
within the range $[1,50]$. The total load of data in the network is equal to
$504$ (i.e., $\sum_{v_{j}\in\mathcal{V}}l_{j}=504$). For a randomly chosen set
of seven nodes the total memory was set to be $31752$, for a randomly chosen
set of seven nodes the total memory was set to be $63504$, and for a randomly
chosen set of six nodes the total memory was set to be $95256$. Our simulation
results are shown in Fig. 1 and Fig. 2.

In Fig. 1 (A), we can see that each node $v_{j}$ is able to calculate the
exact ratio of memory per data after $29$ time steps. The ratio is equal to
$504/20$ and and is calculated exactly in the form of a quantized fraction
without any errors due to quantized communication and processing. In Fig. 1
(B), we can see that each node $v_{j}$ is able to calculate the optimal amount
of data to receive after $29$ time steps. The amount of data is proportional
to the node’s memory capacity. Specifically, from the result of Fig. 1, each
node calculates the ratio of data per memory and then scales with its
available memory capacity. Specifically, the $7$ nodes with total memory equal
to $31752$, receive $1260$ amount of data. The $7$ nodes with total memory
equal to $63504$, receive $2520$ amount of data (double the amount received by
the nodes with $31752$). Finally, the $6$ nodes with total memory equal to
$95256$, receive $3780$ amount of data.

In Fig. 2 (A), we can see the accumulated total number of transmissions
performed from nodes in the network during the operation of Algorithm 1. The
total number of transmissions performed is equal to $291$ during $29$ time
steps. In Fig. 2 (B), we can see the number of transmissions during the
operation of Algorithm 1 at every time step $k$. We can see, that in the
beginning, the number of transmissions is high. However, after $10$ time
steps, it is decreased and it increases at specific instances due to the
dynamic nature of the communication network. The number of transmissions
performed becomes equal to $0$ after $29$ time steps.

Figure 1: Execution of Algorithm 1 over a random dynamic graph comprised of
$20$ nodes where the union of the dynamic graphs is equal to the nominal graph
after $l=5$ time steps. (A): During Algorithm 1 every node calculates the
amount of data per memory after $29$ time steps. (B): Algorithm 1 converges to
the optimal solution after $29$ time steps. Figure 2: Execution of Algorithm 1
over a random dynamic graph comprised of $20$ nodes where the union of the
dynamic graphs is equal to the nominal graph after $l=5$ time steps. (A):
During Algorithm 1 the total number of transmissions performed is equal to
$291$. (B): During Algorithm 1 every node ceases transmissions after $29$ time
steps.

##  VI Conclusions and Future Directions

In this paper, we focused on the problem of optimal data scheduling over a
wireless computing network. We proposed a distributed algorithm which operates
over dynamic networks and converges in finite time. We showed that our
algorithm converges to the exact optimal solution in finite time. Our
algorithm operates with quantized values (i.e., each node processes and
transmits quantized values) and, once it converges to the optimal solution,
each node ceases transmissions. Finally, we have demonstrated the operation of
our algorithm over random dynamic networks and exhorted its finite time
convergence.

Our proposed algorithm operates over dynamic undirected networks, thus its
operation should be extended over dynamic directed networks. Also, designing a
privacy preserving protocol is important in order to protect the privacy of
the node which initially stores the largest amount of data in the network.

##  Appendix A Proof of Lemma 2

The token performs random walk over a dynamic graph $\mathcal{G}[k]$. Since
$b_{lj}[k]\geq(1+\mathcal{D}_{max})^{-1}$ (where $\mathcal{D}_{max}$ is
defined in Lemma 1) and Assumption 1 holds for $\mathcal{G}[k]$ during all
$k$, we have that the probability $P^{lD^{un}}_{DT^{out}}$ that “the token is
at node $v_{i}$ after $lD^{un}$ time steps” is

$P^{lD^{un}}_{DT^{out}}\geq(1+\mathcal{D}_{max})^{-(lD^{un})}>0.$ (11)

This is mainly due to the fact that every $l$ time steps, each edge is active
for at least one time step. Since the nominal graph $\mathcal{G}_{d}$ is
connected, it has a path of length at most $D^{un}$ from each node $v_{\ell}$
to each node $v_{i}$. Thus, at the first $l$ steps, we can select the first
edge in this path (at the instant when it is active) and use self loops at the
remaining instants; during the next $l$ time steps, we can select the second
edge on this path and use self loops at the remaining instants; and so forth.
From (11) we have that the probability $P^{lD^{un}}_{N\\_DT^{out}}$ that “the
token is not at node $v_{i}$ after $lD^{un}$ time steps” is
$P^{lD^{un}}_{N\\_DT^{out}}\leq 1-(1+\mathcal{D}_{max})^{-(lD^{un})}.$ By
extending this analysis, we choose $\varepsilon$ (where $0<\varepsilon<1$) for
which it holds that

$\varepsilon\leq 1-2^{\log_{2}{p_{0}}}.$ (12)

We can state that for $\varepsilon$ which fulfills (12) and after $\tau
lD^{un}$ time steps where

$\tau\geq\Big{\lceil}\dfrac{\log{\varepsilon}}{\log{(1-(1+\mathcal{D}^{+}_{max})^{-(lD^{un})})}}\Big{\rceil},$
(13)

the probability $P^{\tau}_{N\\_DT^{out}}$ that “the token has not visited node
$v_{i}$ after $\tau lD^{un}$ time steps” is
$P^{\tau}_{N\\_DT^{out}}\leq[P^{lD^{un}}_{N\\_T^{out}}]^{\tau}\leq\varepsilon.$
As a result, after $\tau lD^{un}$ time steps (where $\tau$ fulfills (13)) the
probability that “the specific token $T_{\lambda}^{out}$ has visited node
$v_{i}$ after $\tau lD^{un}$ time steps” is equal to $1-\varepsilon>p_{0}$,
where $0<p_{0}<1$, and $\varepsilon$ fulfills $\eqref{varepsilon_condition}$.

##  Appendix B Proof of Theorem 1

The intuition of the proof is the following. During the operation of Algorithm
1, let us consider the simple scenario where among the initial nodes’ states
there is only one “leading mass” and $n-1$ “follower masses” (see Definition
1). Initially, each node broadcasts its state variables. From Algorithm 1.A,
after $lD^{un}$ time steps the state variables of every node become equal to
the leading mass (we assume that until the state variables of every node in
the network are equal to the leading mass no mass variables merged, thus the
leading mass did not change). Then, the follower masses perform random walk in
the network. From Lemma 2, after $\tau lD^{un}$ time steps, where $\tau$
fulfills (13), at least one follower mass will merge with the leading mass
with high probability. Then, the node whose mass variables are the updated
leading mass broadcasts its updated state variables. Thus, the previous
process is repeated until all the $n-1$ follower masses merge with the leading
mass.

During the operation of Algorithm 1, let us consider that there is only one
“leading mass” and $n-1$ “follower masses” (the scenario of multiple leading
masses can be proven identically). From Lemma 2, after $lD^{un}+\tau lD^{un}$
time steps, at least one follower mass will merge with the leading mass with
probability at least $1-\varepsilon$, where $\varepsilon$ is defined in
$\eqref{varepsilon_condition}$. This means that after
$(n-1)(lD^{un})+(n-1)(\tau lD^{un})$ time steps, all $n-1$ follower masses
will merge with the leading mass with probability $(1-\varepsilon)^{n-1}$.
Choosing $\varepsilon$ to fulfill

$\varepsilon\leq 1-2^{\frac{\log_{2}{p_{0}^{\prime}}}{n-1}},$ (14)

and $\tau$ to fulfill (13), we have that after $(n-1)(lD^{un})+(n-1)(\tau
lD^{un})$ time steps, all $n-1$ follower masses will merge with the leading
mass with probability $(1-\varepsilon)^{n-1}\geq p_{0}^{\prime}$.

As a result, during the operation of Algorithm 1, after
$(n)(lD^{un})+(n-1)(\tau lD^{un})$ time steps, each node $v_{j}$ is able to
(i) calculate the optimal amount of data $w^{*}_{j}$ (shown in (8)) with
probability $(1-\varepsilon)^{n-1}\geq p_{0}^{\prime}$, and (ii) cease
transmissions after calculating $w^{*}_{j}$. Note here that the cases where
(i) there are initially multiple leading masses, or (ii) follower masses
perform random walk and two or more merge in order to form a new leading mass,
can be proven identically.

## References

  * [1] J. Y. Wang and K. F. Jea, “A near-optimal database allocation for reducing the average waiting time in the grid computing environment,” _Information Sciences_ , vol. 179, no. 21, pp. 3772–3790, 2009.
  * [2] A. Grammenos, T. Charalambous, and E. Kalyvianaki, “CPU scheduling in data centers using asynchronous finite-time distributed coordination mechanisms,” _arXiv preprint arXiv:2101.06139_ , 2020.
  * [3] M. Doostmohammadian, A. Aghasi, M. Pirani, E. Nekouei, U. A. Khan, and T. Charalambous, “Fast-convergent dynamics for distributed allocation of resources over switching sparse networks with quantized communication links,” _arXiv preprint arXiv:2012.08181_ , 2020.
  * [4] A. I. Rikos, A. Grammenos, E. Kalyvianaki, C. N. Hadjicostis, T. Charalambous, and K. H. Johansson, “Optimal CPU scheduling in data centers via a finite-time distributed quantized coordination mechanism,” _in Proceedings of $60^{th}$ IEEE Conference on Decision and Control (CDC)_, pp. 6276–6281, 2021.
  * [5] A. D. Dominguez-Garcia and C. N. Hadjicostis, “Distributed resource coordination in networked systems described by digraphs,” _Systems $\&$ Control Letters_, vol. 82, pp. 33–39, 2015.
  * [6] M. Rabbat and R. D. Nowak, “Distributed optimization in sensor networks,” _Proceedings of $3^{rd}$ International Symposium on Information Processing in Sensor Networks (IPSN)_, pp. 20–27, 2004.
  * [7] K. Tsianos, S. Lawlor, and M. Rabbat, “Consensus-based distributed optimization: Practical issues and applications in large-scale machine learning,” _Proceedings of $50^{th}$ Annual Allerton Conference on Communication, Control, and Computing_, pp. 1543–1550, 2012.
  * [8] T. Yang, X. Yi, J. Wu, Y. Yuan, D. Wu, Z. Meng, Y. Hong, H. Wang, Z. Lin, and K. H. Johansson, “A survey of distributed optimization,” _Annual Reviews in Control_ , vol. 47, pp. 278–305, 2019.
  * [9] L. Xiao and S. Boyd, “Optimal scaling of a gradient method for distributed resource allocation,” _Journal of Optimization Theory and Applications_ , vol. 129, no. 3, pp. 469–488, 2006.
  * [10] A. Nedić, A. Olshevsky, and W. Shi, “Improved convergence rates for distributed resource allocation,” in _Proceedings of $57^{th}$ IEEE Conference on Decision and Control_, 2018, pp. 172–177.
  * [11] B. Johansson, M. Rabi, and M. Johansson, “A randomized incremental subgradient method for distributed optimization in networked systems,” _SIAM J. on Optimization_ , vol. 20, no. 3, pp. 1157–1170, August 2010.
  * [12] A. Nedic, A. Ozdaglar, and P. A. Parrilo, “Constrained consensus and optimization in multi-agent networks,” _IEEE Transactions on Automatic Control_ , vol. 55, no. 4, pp. 922–938, 2010.
  * [13] A. Nedić, A. Olshevsky, and M. G. Rabbat, “Network topology and communication-computation tradeoffs in decentralized optimization,” _Proceedings of IEEE_ , vol. 106, no. 5, pp. 953–976, 2018.
  * [14] A. Cherukuri and J. Cortes, “Distributed generator coordination for initialization and anytime optimization in economic dispatch,” _IEEE Transactions on Control of Network Systems_ , vol. 2, no. 3, pp. 226–237, December 2015.
  * [15] A. I. Rikos, C. N. Hadjicostis, and K. H. Johansson, “Finite time exact quantized average consensus with limited resources and transmission stopping for energy-aware networks,” _arXiv preprint arXiv:2110.00359_ , 2021.
  * [16] A. I. Rikos and C. N. Hadjicostis, “Distributed average consensus under quantized communication via event-triggered mass splitting,” in _Proceedings of $20^{th}$ IFAC World Congress_, 2020, pp. 3019–3024.