# Inaccessible Neural Language Models Could
Reinvigorate Linguistic Nativism

Patrick Perrine
California Polytechnic State University
1 Grand Ave, San Luis Obispo, CA, 93410
<EMAIL_ADDRESS>
## Abstract

Large Language Models (LLMs) have been making big waves in the machine
learning community within the past few years. The impressive scalability of
LLMs due to the advent of deep learning can be seen as a continuation of
empiricist lingusitic methods, as opposed to rule-based linguistic methods
that are grounded in a nativist perspective. Current LLMs are generally
inaccessible to resource-constrained researchers, due to a variety of factors
including closed source code. This work argues that this lack of accessibility
could instill a nativist bias in researchers new to computational linguistics,
given that new researchers may only have rule-based, nativist approaches to
study to produce new work. Also, given that there are numerous critics of deep
learning claiming that LLMs and related methods may soon lose their relevancy,
we speculate that such an event could trigger a new wave of nativism in the
language processing community. To prevent such a dramatic shift and placing
favor in hybrid methods of rules and deep learning, we call upon researchers
to open source their LLM code wherever possible to allow both empircist and
hybrid approaches to remain accessible.

##  1 Introduction

Large Language Models (LLMs) have been a popular topic of research among the
academic community Srivastava et al. (2022). The promise of a near-general
purpose neural model for a variety of language processing tasks is indeed an
attractive one Xu et al. (2022). Deep learning has made significant
developments in language tasks such as conversational language understanding
Tur et al. (2018), spoken/text-based dialog systems Celikyilmaz et al. (2018),
and natural language generation from images He and Deng (2018). Large Language
models can be viewed as the natural progression away from the rigid rule-based
systems that we’ve had since the 1950’s Chiticariu et al. (2013), continuing
the empiricist mentality of statistical natural language processing without
the potentially costly and context-specific activity of feature engineering
Collobert et al. (2011). However, with large corporations touting their ever-
growing, state-of-the-art models under closed-source code and payment walls,
it could be seen that these large language models are becoming _less
accessible_. Some organizations have acknowledged the potential harms that
deep learning models could cause by establishing ethical frameworks Ashurst et
al. (2022) Weidinger et al. (2022), but there are still growing concerns
regarding accessibility and the result of false/irreproducible science Kapoor
and Narayanan (2022).

This criticism for empiricist methods is not new in linguistics-based science,
in that Chomsky’s Poverty of the Stimulus Argument Stich (1978) has a rich
history of discussion and debate amongst linguists, scientists, and
philosophers Laurence and Margolis (2001). In this work, we will briefly
introduce this debate over language learning between nativists and
empiricists, relate these topics to research in natural language processing,
and disucss how the current state of this research is reinforcing an imbalance
between the two perspectives. We intend to deliver a neutral ground of
analysis, as we agree that a hybrid approach for NLP research can lead to
strong results. The current bias towards the highly-popular, but inaccessible
empiricist methods utilizing LLMs could lead to a new wave of nativism in
natural language processing work, following a large backlash against such
empirical methods.

##  2 Background

We now provide a holistic background on the linguistic and scientific
developments that encompass this issue.

###  2.1 The Three Waves of Modern NLP

We will give a brief background on the three main waves of modern natural
language processing research: the rule-based theories popularized by Noam
Chomsky Chomsky (1965), the statistics-based empiricist experiments Jelinek
(1976), and today’s popular methodology of deep learning for natural language
processing Collobert et al. (2011). The first wave is considered to be under a
nativist perspective Laurence and Margolis (2001), whereas the latter waves
are in support of an empiricist lens Frank et al. (2019).

####  2.1.1 Rule-based NLP

The concept of viewing language as a static system of rules to determine
interpretation has been present as early as the 1830’s Humboldt (1836). Noam
Chomsky popularized this perspective in the domain of linguistics as a
challenge to an existing overbearance of empiricist methods Chomsky (1956b);
Laurence and Margolis (2001).

This rule-based approach to linguistics dominated the field for decades,
following Chomsky’s mutliple works emphasizing and reinforcing this doctrine
Chomsky (1956a, 1957, 1963, 1965); Chomsky and Halle (1968). Being based in
propositional logic and a fixed content, rule-based methods are arguably
rather accessible to researchers with limited resources. These methods
continued to be prevalent in the field until the 1970’s, when statistical
methods were proven to be very useful.

####  2.1.2 Statistical NLP

The roots of statistical language processing stem from Andrey Markov’s efforts
in computing bigram and trigram probabilities Jurafsky and Martin (2022) of
vowel/consonant predictions using a novel as a corpus in 1913 Markov (2006).
This $n$-gram approach was later applied to predicting sequences of English
words Shannon (1948). This popularized the notion of using Markov chains for
use in a variety of applications within and outside of linguistics.

Chomsky specifically challenged this use of finite-state Markov processes, the
processes that formed $n$-gram based approaches, to be useless in serving as a
comprehensive cognitive model of grammatical knowledge in humans Chomsky
(1956b, 1957); Miller and Chomsky (1963). This hindered the progress of
probabilistic approaches in linguistics.

Over a decade later, statistical language processing was revitalized due in
part to a series of successful experiments using $n$-gram models for speech
recognition Baker (1975a, b); Jelinek (1976); Bahl et al. (1983); Jelinek et
al. (1990). These empiricist-based experiments showed that Chomsky’s nativist
theories do not extend to recognizing speech in real time as previously
proposed Chomsky and Halle (1968).

This marked a shift towards looking at language processing through an
empirical lens, where a hypothesis test primarily guides the experimentation
process, rather than theoretical insights Manning and Schutze (1999). After
the successful statistical speech recognition experiments of the mid 1970’s,
statistical NLP reigned as the dominant approach for decades.

####  2.1.3 ML-based NLP

Researchers soon began to use shallow neural networks to reinforce statistical
methodologies in NLP. In the late 2000’s, the advent of deeper neural networks
for NLP began to stir when scalable, hierarchical language models Morin and
Bengio (2005); Mnih and Hinton (2008) and increased computing power became
available for use by researchers.

Alongside these developments, researchers became tiresome of having to hand-
engineer features for neural networks to learn from, as this can be a costly
and rather context-specific task Collobert et al. (2011). In was in the 2010’s
that deep learning became known more globally LeCun et al. (2015), with NLP
being a highly prominent application for deep neural networks. This sparked
the current practice of training large language models in efforts to create a
general model for many language tasks Srivastava et al. (2022). In essence,
the empiricist era of NLP has persisted to today through the evolution of deep
learning practices. Some applications of deep learning outside of language
have even used empiricist terms such as _tabula rasa_ very openly Silver et
al. (2017). The use of deep neural networks for language tasks has been
confirmed to reinforce empircist ideology Frank et al. (2019).

##  3 Deep Learning Can Be Inaccessible

Deep learning as a science has been under fire for a number of reasons. While
there have been encouraging results across many application domains of deep
learning and positive insights about their role in advancing empiricism
Buckner (2018), deep learning has garnered skepticsm from both in and outside
of its community Marcus (2018); Buckner (2019).

These critcisms of deep NLP can stem from a _lack of open sourcing of model
code_ and also data Klein et al. (2017); Fadel et al. (2019); Chen et al.
(2021); Guo et al. (2022); Xu et al. (2022). These issues are not exclusive to
language processing, as other domains have reasons to leave aspects of their
experimentation private or inaccessible when publishing Siegle et al. (2015);
Suresha et al. (2018); Farooq and Hafeez (2020); Zuin et al. (2020); Guo et
al. (2022).

We now focus on issues with closed-source large language models due to their
popularity and the recent claims of greater intelligence (even sentience), as
opposed to other models y Arcas (2022).

##  4 Potential Harms

###  4.1 Potential Harms of Open-Sourcing LLMs

To offer a well-rounded argument in favor of open-sourcing LLMs, we will
briefly cover some intuitions behind close-sourcing them in terms of potential
harms.

LLMs could be repurposed for malicious purposes, particularly in generative
tasks. LLMs have been seen to learn negative human biases/patterns in speech
such as hate speech, discrimination, and the promotion of misinformation
Schramowski et al. (2022). If a powerful, pre-trained LLM is made open source,
then it could be repurposed as an engine to cause harm across the internet at
great scale Weidinger et al. (2022). It could also be argued that open
sourcing LLM code that has been deployed to end-users could pose security
risks Chang et al. (2020).

We counter the argument of potential LLM misuse by malicious parties by
arguing that such models or derivatives of such should not be published in any
form, open or closed source. We argue that LLM experimental papers that
indicate such potential to cause harm at scale should be filtered out at the
publication review stage, something that has been discussed in the deep
learning community as of late Ashurst et al. (2022). We also counter the
security concern argument by saying that this could hold true for all open
source software that is deployable, not just LLMs.

###  4.2 Potential Harms from Continued Close-Sourcing of LLMs

We argue that there are more potential harms in the continued prevalence of
close sourced LLM code than the potential harms of open sourcing them.

####  4.2.1 Nativist Biases

Given that LLM experiments are becoming so large, costly, and complex, it is
difficult to argue that an independent researcher can stake a claim in this
subfield. With top publication venues focusing heavily on empiricist
experimentation Russell and Norvig (2021), researchers outside the typical
corporate scope of research could be incentivized to explore nativist, rule-
based approaches to solve problems in the NLP domain. If it is the empiricist
group’s better interest to foster growth in their methodologies and not
opposing methods, steps should be taken in order to make their approaches
accessible. Also, for hybrid methods to function, an ML-based solution should
be made accessible to combine with the ruleset from the nativist side. This
trend could be fostering a new generation of Chomsky-following nativist NLP
researchers, which would not bode well for empiricists if the public begins to
lose interest in deep learning methods for NLP.

####  4.2.2 Lack of Reproducibility

We mention reproducibility and will further clarify its meaning due to an also
recent, yet broader problem in deep learning research, the reproducibility
crisis Kapoor and Narayanan (2022). Not only are large language models
becoming difficult to reproduce, results from other areas of ML are becoming
difficult to produce de Freitas Pereira et al. (2022); Towers et al. (2022).
Initiatives to measure reproducibility across publication venues have been
created, such as the ML Reproducibility Challenge. LLM experiments have been
specifically reviewed to have a questionable about of reproducibility Crane
(2018); Wieling et al. (2018); Cahyawijaya et al. (2022); Silva et al. (2022).
There is also implied to be a significant amount of computational
irreproducibility of LLM experimentation, given model complexity and data,
however, we leave this exploration for future work.

There is some hope in the form of positive reproducibility reports in deep
learning Gibson and Cano (2022). However, this growing amount of “bad press”
for deep learning, specifically LLMs, could cause the public to begin
distrusting LLM research. This, again, could trigger a revisiting of Chomsky’s
rule-based theories of language.

####  4.2.3 Issues in NLP Education

Given the previously mentioned issues, this lack of accessibility could affect
the education of NLP methods. If students do not have access to code of LLMs,
it could be difficult for them to learn to implement complex language model
code of their own and learn to keep up with the state of the art. A lack of
reproducibility could also be disenfranchising to a young, empircist NLP
researcher, leading them to pursue nativist approaches. These issues could
reinforce the use of statistical, pre-deep learning techniques in the
classroom, but it is difficult to argue that publication venues are interested
in shallow neural network experimentation at this time.

These issues combine to form an uneven playing field for students to study NLP
in empiricist and hybrid forms. After studying NLP formally, they may be
inclined to commit to nativist methods or even reinforce the popularity of
them at scale.

##  5 Potential Solution

We ask that publication venues merit open source LLM experiments significantly
higher than they do currently. We believe that this would mitigate the issues
discussed previously in this work. There seem to be developments occuring now
in the deep learning publication space to help implement this in a proper form
of governance Ashurst et al. (2022).

##  6 Conclusion

In this work, we provided a comprehensive history of natural language
processing methodologies over roughly the past century. We then used this
narrative to lead into today’s deep learning practices used in language
processing, and current issues in an excessive closed sourcing of code for
LLMs. It is our hope that this work inspires researchers and reviewers to
champion open source language model code in order to pave the way for a more
balanced research space.

## References

  * Ashurst et al. (2022) Carolyn Ashurst, Emmie Hine, Paul Sedille, and Alexis Carlier. 2022.  Ai ethics statements: Analysis and lessons learnt from neurips broader impact statements.  In _2022 ACM Conference on Fairness, Accountability, and Transparency_ , pages 2047–2056.
  * Bahl et al. (1983) Lalit R Bahl, Frederick Jelinek, and Robert L Mercer. 1983.  A maximum likelihood approach to continuous speech recognition.  _IEEE transactions on pattern analysis and machine intelligence_ , (2):179–190.
  * Baker (1975a) James Baker. 1975a.  The dragon system–an overview.  _IEEE Transactions on Acoustics, speech, and signal Processing_ , 23(1):24–29.
  * Baker (1975b) James K. Baker. 1975b.  _Stochastic Modeling as a Means of Automatic Speech Recognition._ Ph.D. thesis, USA.
  * Buckner (2018) Cameron Buckner. 2018.  Empiricism without magic: Transformational abstraction in deep convolutional neural networks.  _Synthese_ , 195(12):5339–5372.
  * Buckner (2019) Cameron Buckner. 2019.  Deep learning: A philosophical introduction.  _Philosophy compass_ , 14(10):e12625.
  * Cahyawijaya et al. (2022) Samuel Cahyawijaya, Alham Fikri Aji, Holy Lovenia, Genta Indra Winata, Bryan Wilie, Rahmad Mahendra, Fajri Koto, David Moeljadi, Karissa Vincentio, Ade Romadhony, et al. 2022.  Nusacrowd: A call for open and reproducible nlp research in indonesian languages.  _arXiv preprint arXiv:2207.10524_.
  * Celikyilmaz et al. (2018) Asli Celikyilmaz, Li Deng, and Dilek Hakkani-Tür. 2018.  Deep learning in spoken and text-based dialog systems.  In _Deep Learning in Natural Language Processing_ , pages 49–78. Springer.
  * Chang et al. (2020) Heng Chang, Yu Rong, Tingyang Xu, Wenbing Huang, Honglei Zhang, Peng Cui, Wenwu Zhu, and Junzhou Huang. 2020.  A restricted black-box adversarial framework towards attacking graph embedding models.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 34, pages 3389–3396.
  * Chen et al. (2021) Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde de Oliveira Pinto, Jared Kaplan, Harri Edwards, Yuri Burda, Nicholas Joseph, Greg Brockman, et al. 2021.  Evaluating large language models trained on code.  _arXiv preprint arXiv:2107.03374_.
  * Chiticariu et al. (2013) Laura Chiticariu, Yunyao Li, and Frederick Reiss. 2013.  Rule-based information extraction is dead! long live rule-based information extraction systems!  In _Proceedings of the 2013 conference on empirical methods in natural language processing_ , pages 827–832.
  * Chomsky (1956a) Noam Chomsky. 1956a.  The logical structure of linguistic theory.  _Synthese_ , 40(2):317–352.
  * Chomsky (1956b) Noam Chomsky. 1956b.  Three models for the description of language.  _IRE Transactions on information theory_ , 2(3):113–124.
  * Chomsky (1957) Noam Chomsky. 1957.  Syntactic structures.  In _Syntactic Structures_. De Gruyter Mouton.
  * Chomsky (1963) Noam Chomsky. 1963.  Formal properties of grammars.  _Handbook of Math. Psychology_ , 2:328–418.
  * Chomsky (1965) Noam Chomsky. 1965.  Aspects of the theory of syntax.  _Multilingual Matters: MIT Press_.
  * Chomsky and Halle (1968) Noam Chomsky and Morris Halle. 1968.  The sound pattern of english.
  * Collobert et al. (2011) Ronan Collobert, Jason Weston, Léon Bottou, Michael Karlen, Koray Kavukcuoglu, and Pavel Kuksa. 2011.  Natural language processing (almost) from scratch.  _Journal of machine learning research_ , 12(ARTICLE):2493–2537.
  * Crane (2018) Matt Crane. 2018.  Questionable answers in question answering research: Reproducibility and variability of published results.  _Transactions of the Association for Computational Linguistics_ , 6:241–252.
  * de Freitas Pereira et al. (2022) Tiago de Freitas Pereira, Dominic Schmidli, Yu Linghu, Xinyi Zhang, Sébastien Marcel, and Manuel Günther. 2022.  Eight years of face recognition research: Reproducibility, achievements and open issues.  _arXiv_ , (2208.04040).
  * Fadel et al. (2019) Ali Fadel, Ibraheem Tuffaha, Mahmoud Al-Ayyoub, et al. 2019.  Arabic text diacritization using deep neural networks.  In _2019 2nd international conference on computer applications & information security (ICCAIS)_, pages 1–7. IEEE.
  * Farooq and Hafeez (2020) Muhammad Farooq and Abdul Hafeez. 2020.  Covid-resnet: A deep learning framework for screening of covid19 from radiographs.  _arXiv preprint arXiv:2003.14395_.
  * Frank et al. (2019) Stefan L Frank, Padraic Monaghan, and Chara Tsoukala. 2019.  Neural network models of language acquisition and processing.  In _Human language: From genes and brain to behavior_ , pages 277–293. MIT Press.
  * Gibson and Cano (2022) Perry Gibson and José Cano. 2022.  Productive reproducible workflows for dnns: A case study for industrial defect detection.  _arXiv preprint arXiv:2206.09359_.
  * Guo et al. (2022) Yinpeng Guo, Liangyou Li, Xin Jiang, and Qun Liu. 2022.  Freetransfer-x: Safe and label-free cross-lingual transfer from off-the-shelf models.  _arXiv preprint arXiv:2206.06586_.
  * He and Deng (2018) Xiaodong He and Li Deng. 2018.  Deep learning in natural language generation from images.  In _Deep Learning in Natural Language Processing_ , pages 289–307. Springer.
  * Humboldt (1836) W von Humboldt. 1836.  Uber die verschiedenheit des menschlichen sprachbaues.  _Berlin: Konigliche Akademie der Wissenschaften_.
  * Jelinek et al. (1990) Fred Jelinek, B Merialdo, S Roukos, M Strauss, et al. 1990.  Self-organized language modeling for speech recognition.  In _Readings in speech recognition_.
  * Jelinek (1976) Frederick Jelinek. 1976.  Continuous speech recognition by statistical methods.  _Proceedings of the IEEE_ , 64(4):532–556.
  * Jurafsky and Martin (2022) Daniel Jurafsky and James H Martin. 2022.  Speech and language processing: An introduction to natural language processing, computational linguistics, and speech recognition (draft of january 12, 2022).
  * Kapoor and Narayanan (2022) Sayash Kapoor and Arvind Narayanan. 2022.  Leakage and the reproducibility crisis in ml-based science.  _arXiv preprint arXiv:2207.07048_.
  * Klein et al. (2017) Guillaume Klein, Yoon Kim, Yuntian Deng, Jean Senellart, and Alexander M Rush. 2017\.  Opennmt: Open-source toolkit for neural machine translation.  _arXiv preprint arXiv:1701.02810_.
  * Laurence and Margolis (2001) Stephen Laurence and Eric Margolis. 2001.  The poverty of the stimulus argument.  _British Journal for the Philosophy of Science_ , 52(2).
  * LeCun et al. (2015) Yann LeCun, Yoshua Bengio, Geoffrey Hinton, et al. 2015.  Deep learning.  _Nature, 521 (7553), 436-444_.
  * Manning and Schutze (1999) Christopher Manning and Hinrich Schutze. 1999.  _Foundations of statistical natural language processing_.  MIT press.
  * Marcus (2018) Gary Marcus. 2018.  Deep learning: A critical appraisal.  _arXiv preprint arXiv:1801.00631_.
  * Markov (2006) Andreĭ Andreevich Markov. 2006.  An example of statistical investigation of the text eugene onegin concerning the connection of samples in chains.  _Science in Context_ , 19(4):591–600.
  * Miller and Chomsky (1963) George A Miller and Noam Chomsky. 1963.  Finitary models of language users. handbook of mathematical psychology, vol. by r. duncan luce, robert r. bush, and eugene galanter, 419–91.
  * Mnih and Hinton (2008) Andriy Mnih and Geoffrey E Hinton. 2008.  A scalable hierarchical distributed language model.  _Advances in neural information processing systems_ , 21.
  * Morin and Bengio (2005) Frederic Morin and Yoshua Bengio. 2005.  Hierarchical probabilistic neural network language model.  In _International workshop on artificial intelligence and statistics_ , pages 246–252. PMLR.
  * Russell and Norvig (2021) Stuart Russell and Peter Norvig. 2021.  _Artificial Intelligence: A Modern Approach_.  Pearson.
  * Schramowski et al. (2022) Patrick Schramowski, Cigdem Turan, Nico Andersen, Constantin A Rothkopf, and Kristian Kersting. 2022.  Large pre-trained language models contain human-like biases of what is right and wrong to do.  _Nature Machine Intelligence_ , 4(3):258–268.
  * Shannon (1948) Claude Elwood Shannon. 1948.  A mathematical theory of communication.  _The Bell system technical journal_ , 27(3):379–423.
  * Siegle et al. (2015) Joshua H Siegle, Gregory J Hale, Jonathan P Newman, and Jakob Voigts. 2015.  Neural ensemble communities: open-source approaches to hardware for large-scale electrophysiology.  _Current opinion in neurobiology_ , 32:53–59.
  * Silva et al. (2022) Marília Costa Rosendo Silva, Felipe Alves Siqueira, João Pedro Mantovani Tarrega, João Vitor Pataca Beinotti, Augusto Sousa Nunes, Miguel de Mattos Gardini, Vinícius Adolfo Pereira da Silva, Nádia Félix Felipe da Silva, and André Carlos Ponce de Leon Ferreira de Carvalho. 2022.  No pattern, no recognition: a survey about reproducibility and distortion issues of text clustering and topic modeling.  _arXiv preprint arXiv:2208.01712_.
  * Silver et al. (2017) David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al. 2017.  Mastering the game of go without human knowledge.  _nature_ , 550(7676):354–359.
  * Srivastava et al. (2022) Aarohi Srivastava, Abhinav Rastogi, Abhishek Rao, Abu Awal Md Shoeb, Abubakar Abid, Adam Fisch, Adam R Brown, Adam Santoro, Aditya Gupta, Adrià Garriga-Alonso, et al. 2022.  Beyond the imitation game: Quantifying and extrapolating the capabilities of language models.  _arXiv preprint arXiv:2206.04615_.
  * Stich (1978) Stephen P Stich. 1978.  Empiricism, innateness, and linguistic universals.  _Philosophical Studies: An International Journal for Philosophy in the Analytic Tradition_ , 33(3):273–286.
  * Suresha et al. (2018) S Suresha, L Kidziński, E Halilaj, GE Gold, and SL Delp. 2018.  Automated staging of knee osteoarthritis severity using deep neural networks.  _Osteoarthritis and Cartilage_ , 26:S441.
  * Towers et al. (2022) David Towers, Matthew Forshaw, Amir Atapour-Abarghouei, and Andrew Stephen McGough. 2022.  Long-term reproducibility for neural architecture search.  _arXiv preprint arXiv:2207.04821_.
  * Tur et al. (2018) Gokhan Tur, Asli Celikyilmaz, Xiaodong He, Dilek Hakkani-Tür, and Li Deng. 2018\.  Deep learning in conversational language understanding.  In _Deep Learning in Natural Language Processing_ , pages 23–48. Springer.
  * Weidinger et al. (2022) Laura Weidinger, Jonathan Uesato, Maribeth Rauh, Conor Griffin, Po-Sen Huang, John Mellor, Amelia Glaese, Myra Cheng, Borja Balle, Atoosa Kasirzadeh, et al. 2022.  Taxonomy of risks posed by language models.  In _2022 ACM Conference on Fairness, Accountability, and Transparency_ , pages 214–229.
  * Wieling et al. (2018) Martijn Wieling, Josine Rawee, and Gertjan van Noord. 2018.  Reproducibility in computational linguistics: are we willing to share?  _Computational Linguistics_ , 44(4):641–649.
  * Xu et al. (2022) Frank F Xu, Uri Alon, Graham Neubig, and Vincent Josua Hellendoorn. 2022.  A systematic evaluation of large language models of code.  In _Proceedings of the 6th ACM SIGPLAN International Symposium on Machine Programming_ , pages 1–10.
  * y Arcas (2022) Blaise Agüera y Arcas. 2022.  Do large language models understand us?  _Daedalus_ , 151(2):183–197.
  * Zuin et al. (2020) Gianluca Zuin, Adriano Veloso, João Cândido Portinari, and Nivio Ziviani. 2020.  Automatic tag recommendation for painting artworks using diachronic descriptions.  In _2020 International Joint Conference on Neural Networks (IJCNN)_ , pages 1–8. IEEE.


# Finite Time Privacy Preserving Quantized Average Consensus with Transmission
Stopping

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<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

Due to their flexibility, battery powered or energy-harvesting wireless
networks are employed in diverse applications. Securing data transmissions
between wireless devises is of critical importance in order to avoid privacy-
sensitive user data leakage. In this paper, we focus on the scenario where
some nodes are curious (but not malicious) and try to identify the initial
states of one (or multiple) other nodes, while some nodes aim to preserve the
privacy of their initial states from the curious nodes. We present a privacy
preserving finite transmission event-triggered quantized average consensus
algorithm. Its operation is suitable for battery-powered or energy-harvesting
wireless network since it guarantees (i) efficient (quantized) communication,
and (ii) transmission ceasing (which allows preservation of available energy).
Furthermore, we present topological conditions under which the proposed
algorithm allows nodes to preserve their privacy. We conclude with a
comparison of our algorithm against other algorithms in the existing
literature.

###### Index Terms:

Event-triggered distributed algorithms, privacy preserving average consensus,
quantized communication, finite-time convergence, finite transmission.

##  I INTRODUCTION

Wireless control networks (WCN) play a major role in important applications
due to their deployment flexibility, [1]. Furthermore, the absence of cables
for data communication means that nodes need to rely on (i) battery storage,
and/or (ii) energy harvesting techniques for their operation. Prolonging the
lifetime of a device is a topic that has also received a lot of attention in
recent years (see [2] and references therein). In this paper, in order to
prolong the lifetime of nodes we rely on (i) event-triggered operation, (ii)
transmission stopping guarantees, and (iii) quantized processing and
communication.

The flexibility of WCN allows them to work unattended in hostile environments
with a limited energy budget. Security and privacy of WCN is a challenging
issue since, during their operation in a potentially hostile environment, they
are exposed to a variety of privacy attacks. Specifically, distributed
coordination algorithms require exchange of collected data between neighboring
nodes. In many occasions there might be nodes in the network that are curious
and aim to extract private and/or sensitive data. Revealing the state of a
node may be undesirable in case the state is private or contains sensitive
information. Efficient (quantized) communication between nodes is a desirable
feature since (i) it is more suitable for the available network resources and
(ii) exhibits advantages and applicability to public-key cryptosystems. For
these reasons, several strategies have been proposed for distributed
coordination by achieving quantized average consensus [3, 4].

Previous Literature. There have been different approaches for dealing with the
problem of calculating the quantized average of the initial states with
privacy preservation guarantees. In [5, 6] the authors present works on
differential privacy. In this work, nodes inject uncorrelated noise into the
exchanged messages. The injection of correlated noise at each time step and
for a finite period of time was proposed in [7]. In [8] the nodes
asymptotically subtract the initial offset values they added in the
computation. The problem of calculating the average of the initial states in a
privacy-preserving manner is discussed in [9] for a continuous time weight
balanced system. In [10] the average of the initial states is calculated in a
privacy preserving manner via a state-decomposition-based approach, whereas
[11] discusses the problem under certain topological conditions. Homomorphic
encryption [12, 13] is another strategy which guarantees privacy preservation.
However, it requires the existence of trusted nodes and imposes heavier
computational requirements. In [14] the authors present an event-based offset
algorithm. This strategy allows the calculation of the exact quantized average
in a finite number of time steps, but requires a large number of time steps
for convergence. Finally, in [15] the authors present an initial zero-sum
offset algorithm. This strategy leads to fast finite time convergence to the
exact average, but requires multiple simultaneous transmissions which increase
significantly the header of the transmitted message.

Main Contributions. In this paper, we present a novel privacy preserving
event-triggered distributed algorithm which (i) achieves average consensus
under privacy constraints with quantized communication, (ii) converges after a
finite number of time steps, and (iii) relies on event-driven operation and
ceases transmissions once convergence has been achieved (which makes it
suitable for battery powered or energy harvesting wireless networks). The main
contributions of our paper are the following.

  * $\bullet$

We present a novel privacy preserving distributed event-triggered algorithm
which operates with quantized values and calculates the exact average of the
initial states under privacy constraints; see Algorithm 1 in Section IV-B.

  * $\bullet$

We show that our proposed privacy preserving algorithm converges after a
finite number of iterations for which we provide a polynomial upper bound.
Furthermore, we show our algorithm’s transmission stopping capabilities; see
Theorem 1 in Section IV-D.

  * $\bullet$

We present the necessary topological conditions that ensure privacy
preservation for the nodes that follow the proposed algorithm; see Proposition
1 in Section IV-E.

  * $\bullet$

We demonstrate our algorithm’s operation and compare its performance against
other finite time privacy preserving algorithms from the current literature;
see Section V.

The proposed privacy preserving algorithm relies on multiple state
decomposition. Specifically, at initialization, each node decomposes its
initial state into multiple substate values. No substate value is equal to the
initial state and each substate value is different than the other substate
values. Furthermore, the average of the substate values is equal to the
initial state. The node utilizes one substate as its initial state. Then, it
injects the other substates to its state at specific instances and transmits
them to a different node each time. This ensures that every neighboring node
receives at least one substate. Thus, the privacy of each node’s initial state
is preserved (at least if one neighboring node is not colluding with curious
nodes).

The operation of our privacy preserving strategy relies on the quantized
averaging algorithm in [16] (which is not privacy preserving). Unlike other
privacy preserving strategies in the current literature (e.g., [7, 8, 17,
18]), the proposed strategy takes full advantage of the finite time operation
and transmission ceasing capability of [16], without requiring global network
parameters. This is mainly because the substate values are integers and the
privacy preserving strategy converts the event trigger conditions in [16]. A
comparison with current works is provided in Section IV-C.

##  II NOTATION AND BACKGROUND

The sets of real, rational, integer and natural numbers are denoted by
$\mathbb{R},\mathbb{Q},\mathbb{Z}$ and $\mathbb{N}$, respectively. The set of
nonnegative integers is denoted by $\mathbb{Z}_{+}$.

Graph-Theoretic Notions. Consider a network of $n$ ($n\geq 2$) agents
communicating only with their immediate neighbors. The communication topology
can be captured by a directed graph (digraph), called communication digraph. A
digraph is defined as $\mathcal{G}_{d}=(\mathcal{V},\mathcal{E})$, where
$\mathcal{V}=\\{v_{1},v_{2},\dots,v_{n}\\}$ is the set of nodes and
$\mathcal{E}\subseteq\mathcal{V}\times\mathcal{V}-\\{(v_{j},v_{j})\ |\
v_{j}\in\mathcal{V}\\}$ is the set of edges (self-edges excluded). A directed
edge from node $v_{i}$ to node $v_{j}$ is denoted by
$m_{ji}\triangleq(v_{j},v_{i})\in\mathcal{E}$, and captures the fact that node
$v_{j}$ can receive information from node $v_{i}$ (but not the other way
around). We assume that the given digraph
$\mathcal{G}_{d}=(\mathcal{V},\mathcal{E})$ is strongly connected (i.e., for
each pair of nodes $v_{j},v_{i}\in\mathcal{V}$, $v_{j}\neq v_{i}$, there
exists a directed path111A directed path from $v_{i}$ to $v_{j}$ exists 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}$ for $\tau=0,1,\dots,t-1$. from
$v_{i}$ to $v_{j}$). The subset of nodes that can directly transmit
information to node $v_{j}$ is called the set of in-neighbors of $v_{j}$ and
is represented by
$\mathcal{N}_{j}^{-}=\\{v_{i}\in\mathcal{V}\;|\;(v_{j},v_{i})\in\mathcal{E}\\}$,
while the subset of nodes that can directly receive information from node
$v_{j}$ is called the set of out-neighbors of $v_{j}$ and is represented by
$\mathcal{N}_{j}^{+}=\\{v_{l}\in\mathcal{V}\;|\;(v_{l},v_{j})\in\mathcal{E}\\}$.
The cardinality of $\mathcal{N}_{j}^{-}$ is called the in-degree of $v_{j}$
and is denoted by $\mathcal{D}_{j}^{-}=|\mathcal{N}_{j}^{-}|$, while the
cardinality of $\mathcal{N}_{j}^{+}$ is called the out-degree of $v_{j}$ and
is denoted by $\mathcal{D}_{j}^{+}=|\mathcal{N}_{j}^{+}|$.

Node Operation. With respect to quantization of information flow, we have that
at time step $k\in\mathbb{Z}_{+}$, each node $v_{j}\in\mathcal{V}$ maintains
(i) the state variables $y^{s}_{j}[k],z^{s}_{j}[k],q_{j}^{s}[k]$ (where
$y^{s}_{j}[k]\in\mathbb{Z}$, $z^{s}_{j}[k]\in\mathbb{Z}_{+}$,
$q_{j}^{s}[k]=\frac{y_{j}^{s}[k]}{z_{j}^{s}[k]}$), (ii) the mass variables
$y_{j}[k],z_{j}[k]$, (where $y_{j}[k]\in\mathbb{Z}$ and
$z_{j}[k]\in\mathbb{Z}_{+}$), (iii) the substate counter $s_{j}$ (where
$s_{j}\in\mathbb{N}$), (iv) the privacy variables $u_{j}^{y}[s_{j}]$,
$u_{j}^{z}[s_{j}]$ (where $u_{j}^{y}[s_{j}]\in\mathbb{Z}$,
$u_{j}^{z}[s_{j}]\in\mathbb{Z}$), (v) the transmission variables $S\\_br_{j}$
and $M\\_tr_{j}$ (where $S\\_br_{j}\in\mathbb{N}$ and
$M\\_tr_{j}\in\mathbb{N}$). Note here that for every node $v_{j}$, the state
variables $y^{s}_{j}[k],z^{s}_{j}[k],q_{j}^{s}[k]$ are used to store the
received messages and calculate the quantized average of the initial values,
the mass variables $y_{j}[k],z_{j}[k]$ are used to communicate with other
nodes by either transmitting or receiving messages, the substate counter
$s_{j}$ is used to transmit the privacy variables, the privacy variables
$u_{j}^{y}[s_{j}]$, $u_{j}^{z}[s_{j}]$ are used to preserve the privacy of the
initial state, and the transmission variables $S\\_br_{j}$, $M\\_tr_{j}$ are
used to decide whether the state variables will be broadcasted or the mass
variables will be transmitted.

Furthermore, we assume that each node is aware of its out-neighbors and can
directly (or indirectly222Indirect transmission could involve broadcasting a
message to all out-neighbors while including in the message header the ID of
the out-neighbor it is intended for.) transmit messages to each out-neighbor;
however, it cannot necessarily receive messages (at least not directly) from
them. In the proposed distributed algorithm, each node $v_{j}$ assigns a
unique order in the set $\\{0,1,...,\mathcal{D}_{j}^{+}-1\\}$ to each of its
outgoing edges $m_{lj}$, where $v_{l}\in\mathcal{N}^{+}_{j}$. More
specifically, the order of link $(v_{l},v_{j})$ for node $v_{j}$ is denoted by
$P_{lj}$ (such that
$\\{P_{lj}\;|\;v_{l}\in\mathcal{N}^{+}_{j}\\}=\\{0,1,...,\mathcal{D}_{j}^{+}-1\\}$).
This unique predetermined order is used during the execution of the proposed
distributed algorithm as a way of allowing node $v_{j}$ to transmit messages
to its out-neighbors in a round-robin333When executing the proposed algorithm,
each node $v_{j}$ transmits to its out-neighbors, one at a time, by following
a predetermined order. The next time it transmits to an out-neighbor, it
continues from the outgoing edge it stopped the previous time and cycles
through the edges in a round-robin fashion according to the predetermined
ordering. fashion.

##  III PROBLEM FORMULATION

Consider a strongly connected digraph
$\mathcal{G}_{d}=(\mathcal{V},\mathcal{E})$, where each node
$v_{j}\in\mathcal{V}$ has an initial (i.e., for $k=0$) quantized value
$y_{j}[0]$ (for simplicity, we take $y_{j}[0]\in\mathbb{Z}$). Furthermore,
consider that the node set $\mathcal{V}$ is partitioned into three subsets.
Specifically, we have (i) the subset of nodes
$v_{j}\in\mathcal{V}_{p}\subset\mathcal{V}$ that wish to preserve their
privacy by not revealing their initial states $y_{j}[0]$ to other nodes, (ii)
the subset of nodes $v_{c}\in\mathcal{V}_{c}\subset\mathcal{V}$ that are
curious and try to identify the initial states $y[0]$ of all or a subset of
nodes in the network, and (iii) the rest of the nodes
$v_{i}\in\mathcal{V}_{n}\subset\mathcal{V}$ that neither wish to preserve
their privacy nor identify the states of any other nodes. We assume that
$\mathcal{V}_{p}\cap\mathcal{V}_{c}=\emptyset$, which means that curious nodes
in $\mathcal{V}_{c}$ collaborate arbitrarily in order to identify the initial
states of other nodes in the network. An example is shown in Fig. 1 (from
[15]).

Figure 1: Example of a digraph with the different types of nodes in the
network: nodes $v_{j_{1}},v_{j_{2}}\in\mathcal{V}_{p}$ wish to preserve their
privacy, node $v_{c}\in\mathcal{V}_{c}$ is curious and wishes to identify the
initial states of other nodes in the network, and node
$v_{\lambda}\in\mathcal{V}_{n}$ is neither curious nor wishes to preserve its
privacy.

Privacy is defined as the ability of an individual node to seclude itself and
thereby express itself selectively. We consider that the information of
interest for each node is its initial state $y_{j}[0]$. We adopt the following
notion of privacy, which aims to ensure that the state $y_{j}[0]$ cannot be
inferred exactly by curious nodes and relates to notions of possible innocence
in theoretical computer science [19, 20] in the sense that there is some
uncertainty about $y_{j}[0]$.

######  Definition 1.

A node $v_{j}\in\mathcal{V}_{p}$ preserves the privacy of its initial state
$y_{j}[0]\in\mathbb{Z}$ if $y_{j}[0]$ cannot be inferred by curious nodes
$v_{c}\in\mathcal{V}_{c}$ at any point during the operation of the algorithm.
This means that curious nodes in $\mathcal{V}_{c}$ cannot determine a finite
range $[\alpha,\beta]$ (where $\alpha<\beta$ and $\alpha,\beta\in\mathbb{R}$)
in which the initial state $y_{j}[0]$ lies in.

In this paper, we develop a distributed algorithm that allows nodes to address
the problems P1, P2 and P3 presented below, while processing and transmitting
quantized information via available communication links.

P1. Every node $v_{j}$ obtains, after a finite number of steps, a fraction
$q_{j}^{s}$ which is equal to the exact average $q$ of the initial states of
the nodes (i.e., there is no quantization error), where

$q=\frac{\sum_{l=1}^{n}{y_{l}[0]}}{n}.$ (1)

Specifically, we argue that there exists $k_{0}$ so that for every $k\geq
k_{0}$ we have

$y^{s}_{j}[k]=\frac{\sum_{l=1}^{n}{y_{l}[0]}}{\alpha}\ \ \text{and}\ \
z^{s}_{j}[k]=\frac{n}{\alpha},$ (2)

where $\alpha\in\mathbb{N}$. This means that

$q^{s}_{j}[k]=\frac{(\sum_{l=1}^{n}{y_{l}[0]})/\alpha}{n/\alpha}\coloneqq q,$
(3)

for every $v_{j}\in\mathcal{V}$ (i.e., for $k\geq k_{0}$ every node $v_{j}$
has calculated $q$ as the ratio of two integer values).

P2. Every node $v_{j}\in\mathcal{V}_{p}$ preserves the privacy of its initial
state $y_{j}[0]$ (i.e., it does not reveal its initial state $y_{j}[0]$ to
other nodes) when it exchanges quantized information with neighboring nodes
while calculating $q$ in (1) (i.e., its state variables $y^{s}_{j}$,
$z^{s}_{j}$, $q^{s}_{j}$ fulfill (2) and (3), respectively).

P3. Every node $v_{j}$ stops performing transmissions towards its out-
neighbors $v_{l}\in\mathcal{N}^{+}_{j}$ once its state variables $y^{s}_{j}$,
$z^{s}_{j}$, $q^{s}_{j}$ fulfill (2) and (3), respectively.

##  IV PRIVACY PRESERVING EVENT-TRIGGERED QUANTIZED AVERAGE CONSENSUS
ALGORITHM WITH FINITE TRANSMISSION CAPABILITIES

In this section we present a distributed algorithm which addresses problems
(P1), (P2), (P3) presented in Section III. Before presenting the main
functionalities of our algorithm, we make the following assumption.

######  Assumption 1.

We assume that each node $v_{j}\in\mathcal{V}$ has knowledge of the maximum
out-degree in the network
$\mathcal{D}_{max}^{+}=\max_{v_{i}\in\mathcal{V}}\mathcal{D}_{j}^{+}$.

Assumption 1 is important for guaranteeting convergence to the average of the
initial states. In case Assumption 1 does not hold, then our algorithm may
converge to a value that is not equal to the average of the initial states
(i.e., our algorithm will simply achieve consensus).

###  IV-A Initialization for Privacy Preserving Algorithm with Multiple State
Decomposition

Our strategy is based on the event-triggered deterministic algorithm in [16]
with some modifications (since the algorithm in [16] is not privacy
preserving). The main difference is the deployment of a mechanism that
decomposes the initial state $y_{j}[0]$ of each node $v_{j}\in\mathcal{V}_{p}$
into $\mathcal{D}_{max}^{+}+2$ substates. The average of the
$\mathcal{D}_{max}^{+}+2$ substates is equal to the initial state $y_{j}[0]$.
Then, each substate is transmitted to a different out-neighbor at a different
time step thus, effectively preserving the privacy of the initial state
$y_{j}[0]$.

In previous works (e.g., [7, 8, 17, 14, 15]), each node
$v_{j}\in\mathcal{V}_{p}$ injects a nonzero offset $u_{j}$ to its initial
state. This means that it sets $\widetilde{y}_{j}[0]=y_{j}[0]+u_{j}$, where
$u_{j}\neq 0$. However, in our case we require each node
$v_{j}\in\mathcal{V}_{p}$ to decompose its initial state $y_{j}[0]$ into
$\mathcal{D}_{max}^{+}+2$ substates whose average is equal to the initial
state. Furthermore, each node $v_{j}$ maintains its substate counter
$s_{j}\in\mathbb{N}$, and its privacy variables
$u_{j}^{y}[s_{j}]\in\mathbb{Z}$, $u_{j}^{z}[s_{j}]\in\mathbb{Z}$. At
initialization, each node $v_{j}\in\mathcal{V}_{p}$ chooses the privacy
variables $u_{j}^{y}[s_{j}]\in\mathbb{Z}$, $u_{j}^{z}[s_{j}]\in\mathbb{Z}$,
for $s_{j}\in\\{0,1,2,...,\mathcal{D}_{max}^{+}+1\\}$, to satisfy the
following constraints:

$\displaystyle u_{j}^{y}[s_{j}]$ $\displaystyle\neq
u_{j}^{y}[s_{j}^{\prime}],\ u_{j}^{y}[s_{j}]\neq y_{j}[0],$
$\displaystyle\forall s_{j},s_{j}^{\prime}$
$\displaystyle\in[0,\mathcal{D}_{max}^{+}+1],\ \text{with}\ s_{j}\neq
s_{j}^{\prime}$ (4a) $\displaystyle u_{j}^{y}[s_{j}]$ $\displaystyle=0,\
\forall\ s_{j}>\mathcal{D}_{max}^{+}+1,$ (4b) $\displaystyle u_{j}^{z}[s_{j}]$
$\displaystyle=1,\ \forall\ s_{j}\in[0,\mathcal{D}_{max}^{+}+1],$ (4c)
$\displaystyle u_{j}^{z}[s_{j}]$ $\displaystyle=0,\ \forall\
s_{j}>\mathcal{D}_{max}^{+}+1,$ (4d)
$\displaystyle\frac{\sum_{s_{j}=0}^{\mathcal{D}_{max}^{+}+1}u_{j}^{y}[s_{j}]}{\mathcal{D}_{max}^{+}+2}=y_{j}[0].$
(4e)

Constraints (4a)–(4e) are explicitly analyzed below:
1. In (4a) each substate $u_{j}^{y}[s_{j}]$ needs to have different value than every other substate $u_{j}^{y}[s_{j}^{\prime}]$ for $s_{j}\neq s_{j}^{\prime}$ and $s_{j},s_{j}^{\prime}\in[0,\mathcal{D}_{max}^{+}+1]$. Furthermore, each substate $u_{j}^{y}[s_{j}]$ needs to have a different value than the initial state $y_{j}[0]$. This is important for not revealing the value of the initial state $y_{j}[0]$ and thus preserving its privacy.
2. In (4b) each node $v_{j}$ stops injecting nonzero offsets after $\mathcal{D}_{max}^{+}+2$ time steps in order not to intervene with the calculation of the quantized average. This allows each node to calculate the exact quantized average of the initial states without any error.
3. In (4c) the substate $u_{j}^{z}[s_{j}]$ which is injected to the network by node $v_{j}$ needs to be equal to $1$ so that (i) the event-triggered conditions of the presented algorithm hold and (ii) the operation of the algorithm leads to the calculation of the exact average.
4. In (4d) each node $v_{j}$ stops injecting nonzero offsets after $\mathcal{D}_{max}^{+}+1$ time steps which allows the calculation of the quantized average without any error.
5. In (4e) the average of the total injected offset in the network by node $v_{j}$ needs to be equal to node $v_{j}$’s initial state $y_{j}[0]$. This means that each node $v_{j}$ creates $\mathcal{D}_{max}^{+}+2$ substates of its initial state which have different $u_{j}^{y}[s_{j}]$ values. These substates allow calculation of the exact quantized average of the initial states without any error.

The above choices imply that each node $v_{j}\in\mathcal{V}_{p}$ generates
$\mathcal{D}_{max}^{+}+2$ substates $u_{j}^{y}[s_{j}]$, $u_{j}^{z}[s_{j}]$ of
its initial state $y_{j}[0]$, for which it holds (i) $u_{j}^{y}[s_{j}]\neq
u_{j}^{y}[s_{j}^{\prime}]$, $s_{j}\neq s_{j}^{\prime}$ and (ii)
$u_{j}^{y}[s_{j}]\neq y_{j}[0]$, for every
$s_{j},s_{j}^{\prime}\in[0,\mathcal{D}_{max}^{+}+1]$. Then, during every time
step $s_{j}\in[0,\mathcal{D}_{max}^{+}+1]$, node $v_{j}$ injects in the
network the substates $u_{j}^{y}[s_{j}]$, $u_{j}^{z}[s_{j}]$. This leads to
the calculation of the exact quantized average in a privacy preserving manner.
Note that if $u_{j}^{y}[s_{j}]\neq y_{j}[0]$, for every
$s_{j}\in[0,\mathcal{D}_{max}^{+}+1]$, does not hold, then the exact quantized
average may be calculated but not in a privacy preserving manner.

######  Remark 1.

Note here that each node $v_{j}\in\mathcal{V}_{p}$ that wishes to preserve its
privacy chooses its privacy variables $u_{j}^{y}[s_{j}]\in\mathbb{Z}$,
$u_{j}^{z}[s_{j}]\in\mathbb{Z}$ according to (4a)–(4e). However, each node
$v_{i}\notin\mathcal{V}_{p}$ which does not wish to preserve its privacy sets
$u_{i}^{y}[s_{j}]=y_{i}[0]$, for every $s_{i}\in[0,\mathcal{D}_{max}^{+}+1]$
and also chooses its privacy variables $u_{i}^{y}[s_{j}]\in\mathbb{Z}$,
$u_{i}^{z}[s_{j}]\in\mathbb{Z}$, according to (4b)–(4e) (i.e., (4a) does not
hold).

###  IV-B Privacy Preserving Finite Transmission Event-Triggered Algorithm

The details of the privacy preserving distributed algorithm with transmission
stopping can be seen in Algorithm 1.

Algorithm 1 Privacy Preserving Finite Transmission Event-Triggered Quantized
Average Consensus

Input: A strongly connected digraph
$\mathcal{G}_{d}=(\mathcal{V},\mathcal{E})$ with $n=|\mathcal{V}|$ nodes and
$m=|\mathcal{E}|$ edges. Each node $v_{j}\in\mathcal{V}$ has an initial state
$y_{j}[0]\in\mathbb{Z}$ and has knowledge of $\mathcal{D}_{max}^{+}$.
Initialization: Each node $v_{j}\in\mathcal{V}$ does the following:

  * 1)

Assigns to each outgoing edge $v_{l}\in\mathcal{N}^{+}_{j}$ a unique order
$P_{lj}$ in the set $\\{0,1,...,\mathcal{D}_{j}^{+}-1\\}$.

  * 2)

Sets counter $s_{j}=0$. Chooses $u^{y}_{j}[k]\neq u^{y}_{j}[k_{1}]$,
$u^{y}_{j}[k]\neq y_{j}[0]$ where $k\neq k_{1}$ for every
$k,k_{1}\in\\{0,1,\ldots,\mathcal{D}_{max}^{+}+1\\}$, and
$u^{y}_{j}[k^{\prime}]=0$ for $k^{\prime}>\mathcal{D}_{max}^{+}+1$ such that
$(\sum_{s_{j}=0}^{\mathcal{D}_{max}^{+}+1}u_{j}^{y}[s_{j}])/(\mathcal{D}_{max}^{+}+2)=y_{j}[0]$.

  * 3)

Chooses $u^{z}_{j}[k]=1$ for $k\in\\{0,1,\ldots,\mathcal{D}_{max}^{+}+1\\}$,
and $u^{z}_{j}[k^{\prime}]=0$ for $k^{\prime}>\mathcal{D}_{max}^{+}+1$.

  * 4)

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

  * 5)

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

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

  * 1)

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

  * 2)

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

$y_{j}[k+1]=y_{j}[k]+\sum_{v_{i}\in\mathcal{N}_{j}^{-}}w_{ji}[k]y_{i}[k],$
$z_{j}[k+1]=z_{j}[k]+\sum_{v_{i}\in\mathcal{N}_{j}^{-}}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$.

  * 3)

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

  * 4)

Sets $M\\_tr_{j}=\max\\{M\\_tr_{j},u^{z}_{j}[s_{j}]\\}$.

  * 5)

If $M\\_tr_{j}=1$ then (i) sets $y_{j}[k]=y_{j}[k]+u^{y}_{j}[s_{j}]$,
$z_{j}[k]=z_{j}[k]+u^{z}_{j}[s_{j}]$ and (ii) chooses
$v_{l}\in\mathcal{N}_{j}^{+}$ according to $P_{lj}$ (in a round-robin fashion)
and transmits $y_{j}[k]$, $z_{j}[k]$. Then, sets $y_{j}[k]=0$, $z_{j}[k]=0$,
$M\\_tr_{j}=0$, $s_{j}=s_{j}+1$.

  * 6)

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

  * 7)

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

Output: (3) 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}$ and the received $y^{s}_{i}[k]$, $z^{s}_{i}[k]$
from every $v_{i}\in\mathcal{N}_{j}^{-}$.
Execution

  * 1)

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 sets

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

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

  * 2)

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 sets $z^{s}_{j}[k+1]=z_{j}[k+1]$, $y^{s}_{j}[k+1]=y_{j}[k+1]$ and sets
$q^{s}_{j}[k+1]=\frac{y^{s}_{j}[k+1]}{z^{s}_{j}[k+1]}$ and $S\\_br_{j}=1$.

  * 3)

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 sets $M\\_tr_{j}=1$.

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

The intuition behind Algorithm 1 is the following. Let us first consider the
notion of “leading mass”. During time step $k$, the set of mass variables
which has the largest $z[k]$ value is the “leading mass”. In case there are
multiple sets of mass variables that have the largest $z[k]$, then the
“leading mass” is the set of mass variables that has the largest $y[k]$ value
among the sets of mass variables with the largest $z[k]$. Note that a formal
definition of the “leading mass” is presented in Section IV-D. Each node
$v_{j}\in\mathcal{V}_{p}$ that would like to preserve its privacy performs the
following steps:
Initialization.
A. Node $v_{j}$ assigns to each outgoing edge a unique order $P_{lj}$ in order
to perform transmissions in a round-robin fashion.
B. Node $v_{j}$ initializes the substate counter $s_{j}$ to zero (i.e.,
$s_{j}=0$) and the set of $(\mathcal{D}_{max}^{+}+2)$ privacy variables
$u_{j}^{y}[s_{j}]$, $u_{j}^{z}[s_{j}]$ according to (4a)–(4e) for
$s_{j}\in[0,\mathcal{D}_{max}^{+}+1]$. For example, suppose that node $v_{j}$
has initial state $y_{j}[0]=4$ and the maximum out-degree in the network is
equal to $3$. This means that it decomposes its initial state in $5$
substates. Specifically, it can (randomly) set $u_{j}^{y}[0]=1$,
$u_{j}^{y}[1]=8$, $u_{j}^{y}[2]=6$, $u_{j}^{y}[3]=2$, $u_{j}^{y}[4]=3$, and
$u_{j}^{z}[0]=1$, $u_{j}^{z}[1]=1$, $u_{j}^{z}[2]=1$, $u_{j}^{z}[3]=1$,
$u_{j}^{z}[4]=1$. Note that the average of the substates $u_{j}^{y}[s_{j}]$,
$s_{j}\in\\{0,1,2,3,4\\}$ is equal to $4$.
C. Node $v_{j}$ utilizes the substates $u_{j}^{y}[0]$, $u_{j}^{z}[0]$ as its
initial state (i.e., it sets $y_{j}[0]=u_{j}^{y}[0]$ and
$z_{j}[0]=u_{j}^{z}[0]$). Then, considers its set of stored mass variables
$y_{j}[0]$, $z_{j}[0]$ to be the “leading mass”. For this reason, it sets its
state variables $z^{s}_{j}[0]$, $y^{s}_{j}[0]$, $q^{s}_{j}[0]$ to be equal to
the stored mass variables $y_{j}[0]$, $z_{j}[0]$, and then broadcasts the
values of its state variables.

Iteration.
A. Node $v_{j}$ receives the (possibly) transmitted state variables from its
in-neighbors and, (ii) receives and stores the (possibly) transmitted mass
variables from its in-neighbors.
B. If node $v_{j}$ received a set of state variables and/or a set of mass
variables from its in-neighbors, then it executes Algorithm 1.A. During
Algorithm 1.A each node checks:
B – Event Trigger Conditions $1$: It checks whether the received set of state
variables is equal to the “leading mass”. If it receives messages from
multiple in-neighbors it checks which set of state variables is the “leading
mass”. If Event Trigger Conditions $1$ hold, it sets its state variables to be
equal to the received set of state variables which is the “leading mass” and
decides to broadcast its updated state variables (i.e., sets its transmission
variable $S\\_br_{j}=1$).
B – Event Trigger Conditions $2$: It checks whether the set of mass variables
it stored is the “leading mass.” If this condition holds, it sets its state
variables to be equal to the stored set of mass variables and decides to
broadcast its updated state variables (i.e., sets its transmission variable
$S\\_br_{j}=1$).
B – Event Trigger Conditions $3$: It checks whether the set of mass variables
it stored is not the “leading mass” (i.e., it checks whether its state
variables are equal to the “leading mass”). If this condition holds, this
means that the mass variables of another node in the network is the “leading
mass” (and the state variables of node $v_{j}$ became equal to the “leading
mass” from Event Trigger Conditions $1$). This means the stored mass variables
is not the “leading mass” and thus $v_{j}$ decides to transmit its stored mass
variables (i.e., sets its transmission variable $M\\_tr_{j}=1$).
C. Node $v_{j}$ sets its transmission variable $M\\_tr_{j}$ to be equal to the
maximum value of $M\\_tr_{j}$ and the substate $u_{j}^{z}[s_{j}]$. This step
is important for the privacy preserving mechanism. Note that the value of the
substate $u_{j}^{z}[s_{j}]$ is equal to $1$ for
$s_{j}\in[0,\mathcal{D}_{max}^{+}+1]$. This means that the value of the
transmission variable $M\\_tr_{j}$ will become equal to $1$ for the first
$\mathcal{D}_{max}^{+}+1$ time steps (since $s_{j}$ becomes equal to $1$
during the Initialization procedure). Thus, node $v_{j}$ will perform
transmissions of the substates $u_{j}^{y}[s_{j}]$, $u_{j}^{z}[s_{j}]$ towards
its out-neighbors.
D. If $M\\_tr_{j}$ is equal to $1$, node $v_{j}$ (i) injects the substates
$u_{j}^{y}[s_{j}]$, $u_{j}^{z}[s_{j}]$ to its mass variables, (ii) transmits
its mass variables towards an out-neighbor according to the unique order
$P_{lj}$, and (iii) increases the substate counter $s_{j}$.
E. If $S\\_br_{j}$ is equal to $1$ node $v_{j}$ broadcasts its state variables
towards every out-neighbor. Then, it repeats the procedure.

###  IV-C Comparison with Previous Works

Algorithm 1 is significantly different than most asymptotic or finite time
algorithms in the current literature (see, e.g., [7, 8, 17, 14, 15]).
Specifically, Algorithm 1 is different from asymptotic algorithms (see, e.g.,
[7, 8, 17]). These algorithms are able to calculate the average of the initial
states in an asymptotic fashion which includes transmission of real valued
messages and results in asymptotic convergence. Furthermore, these algorithms
do not provide finite transmission guarantees. Algorithm 1 is also different
from the finite time algorithms in [14, 15]. In the event-based offset
algorithm in [14], each node $v_{j}$ initially injects a negative valued
quantized offset to its state. Then, it injects a positive valued offset to
its state only when its event-triggered conditions hold. This strategy relies
on transmission of quantized values towards a single out-neighbor (which does
not increase the header of the transmitted message). However, it requires a
significant number of time steps for convergence (since the event-triggered
conditions of each node need to hold for a specific number of instances before
the total offset is injected in the network). Also, [14] does not exhibit
finite transmission guarantees and is not suitable for finite transmission
operation. Specifically, if a distributed stopping protocol is utilized, [14]
may converge and stop before each node injects the total stored offset in the
network (since each node injects a positive valued offset to its state only
when its event-triggered conditions hold). This will result in achieving
consensus but not equal to the average of the initial states. In the initial
zero-sum offset algorithm in [15], each node injects a quantized offset to its
out-neighboring nodes during the algorithm’s initialization steps which leads
to fast convergence. However, it requires multiple simultaneous transmissions
of different quantized values towards every out-neighbor. This increases
significantly the header of the transmitted message and each node keeps
performing transmissions once convergence has been achieved. Furthermore, [15]
does not exhibit finite transmission guarantees. The privacy preserving
strategy of Algorithm 1 takes full advantage of the finite time nature of the
underlying quantized averaging algorithm (which is presented in [16]).
Specifically, each node decomposes its state into multiple substates and
utilizes one substate as its initial state. Then, it transmits each one of the
other substates to a single out-neighbor at specific time steps. This means
that (i) consensus to the exact average of the initial states is reached after
a finite number of iterations, (ii) no initial error is introduced which
allows faster convergence of the algorithm (i.e., no offset is initially
infused in the network by the nodes following the algorithm), (iii) each node
performs directed transmissions towards a single out-neighbor or broadcast
transmissions towards every out-neighbor (which does not increase
significantly the header of the transmitted message), and (iv) every node
ceases transmissions once the average of the initial states is calculated in a
privacy preserving manner.

###  IV-D Convergence Analysis of Algorithm 1

Before analyzing the deterministic convergence of Algorithm 1, we consider the
following setup.

Setup: Consider a strongly connected digraph
$\mathcal{G}_{d}=(\mathcal{V},\mathcal{E})$ with $n=|\mathcal{V}|$ nodes and
$m=|\mathcal{E}|$ edges. 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}.$ (5)

Then, among the nodes $v_{j^{\prime}}$ for which (5) 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}\\}.$ (6)

For notational convenience we will call the mass variables of node $v_{j}$ for
which (5) and (6) hold as the “leading mass” (or “leading masses”).

We now consider the following two lemmas which are necessary for our
subsequent development. Due to space considerations we omit the proofs of the
two lemmas; they will be available in an extended version of our paper.

######  Lemma 1.

If, during time step $k_{0}$ of Algorithm 1, the mass variables of node
$v_{j}$ fulfill (5) and (6), then the state variables of every node
$v_{i}\in\mathcal{V}$ satisfy

$\displaystyle z_{i}^{s}[k_{0}]\leq z_{j}[k_{0}],$ (7)

or

$\displaystyle z_{i}^{s}[k_{0}]=z_{j}[k_{0}]\ \ \text{and}\ \
y_{i}^{s}[k_{0}]\leq y_{j}[k_{0}].$ (8)

######  Lemma 2.

If, during time step $k_{0}$ of Algorithm 1, the mass variables of each node
$v_{j}$ with nonzero mass variables fulfill (5) and (6), then we have only
“leading masses” and no “follower masses”. This means that the “Event Trigger
Conditions $2$” will never hold again for future time steps $k\geq k_{0}$. As
a result, the transmissions that (may) take place will only be via
broadcasting (from “Event Trigger Conditions $1$ and $3$”) for at most $n-1$
time steps and then they will cease.

We now analyze the deterministic convergence of Algorithm 1. Due to space
considerations we provide a sketch of the proof.

######  Theorem 1.

Consider a strongly connected digraph
$\mathcal{G}_{d}=(\mathcal{V},\mathcal{E})$ with $n=|\mathcal{V}|$ nodes and
$m=|\mathcal{E}|$ edges. The execution of Algorithm 1 allows each node
$v_{j}\in\mathcal{V}$ to reach quantized average consensus after a finite
number of time steps $k_{0}$ upper bounded by
$1+\mathcal{D}_{max}^{+}+n^{2}+(n-1)m^{2}$, where $n$ is the number of nodes
and $m$ is the number of edges in the network, and $\mathcal{D}_{max}^{+}$ is
the maximum out-degree in the network. Furthermore, each node stops
transmitting towards its out-neighbors once quantized average consensus is
reached.

###### Proof.

In this proof we will show that there exists $k_{0}\in\mathbb{Z}_{+}$ for
which the mass variables of every node $v_{j}$ (for which $z_{j}[k]>0$)
fulfill (5) and (6), for every $k\geq k_{0}$. This means that for $k\geq
k_{0}$ we have only leading masses. Note here that, during the execution of
Algorithm 1, the leading mass will not fulfill the Event Trigger Conditions
$3$ (in Execution Step $3$ of Algorithm 1.A). This means that the
corresponding node (say $v_{j}$) will not transmit its mass variables to its
out-neighbors $v_{l}\in\mathcal{N}_{j}^{+}$ according to its predetermined
priority. Furthermore, from Lemma 2 we will also show that there exists
$k_{1}>k_{0}$ ($k_{1}\in\mathbb{Z}_{+}$), where for every $k\geq k_{1}$ the
state variables of every $v_{j}\in\mathcal{V}$ fulfill (2) and (3) for
$\alpha\in\mathbb{Z}_{+}$ (i.e., every node has reached quantized consensus)
and thus transmissions cease.

During the Initialization steps of Algorithm 1, each node $v_{j}$ will (i)
decompose its initial state $y_{j}[0]$ into $\mathcal{D}_{max}^{+}+2$
substates $u_{j}^{y}[s_{j}]\in\mathbb{Z}$, for
$s_{j}\in\\{0,1,2,...,\mathcal{D}_{max}^{+}+1\\}$, (ii) set its initial state
$y_{j}[0]$ to be equal to $u_{j}^{y}[0]$, (iii) increase the substate counter
$s_{j}$, and (iv) broadcast its state variables to every out-neighbor. Then,
during Iteration Step $1$, each node will (i) receive and update its state
variables, (ii) receive and update its mass variables, and (iii) call
Algorithm 1.A to check Event Trigger Conditions $1$, Event Trigger Conditions
$2$, and Event Trigger Conditions $3$. However, note here that regardless of
the output of Algorithm 1.A, each node $v_{j}$ will utilize the privacy
preseving strategy for the first $\mathcal{D}_{max}^{+}+1$ time steps (i.e.,
for $k=0,1,...,\mathcal{D}_{max}^{+}$). This means that for the first
$\mathcal{D}_{max}^{+}+1$ time steps of the Iteration procedure, each node
$v_{j}$ will inject to its mass variables the set of substates
$u_{j}^{y}[s_{j}]$, $u_{j}^{z}[s_{j}]$, for
$s_{j}\in\\{0,1,2,...,\mathcal{D}_{max}^{+}\\}$. Then, it will transmit its
mass variables to an out-neighbor according to the order $P_{lj}$. Thus, after
$\mathcal{D}_{max}^{+}+1$ time steps, each node $v_{j}$ will have injected in
the network every set of substates $u_{j}^{y}[s_{j}]$, $u_{j}^{z}[s_{j}]$.

For the analysis of the execution of Algorithm 1 for time steps
$k\geq\mathcal{D}_{max}^{+}+1$, we can use steps similar to the analysis in
the proof of Theorem $1$ in [16]. ∎

###  IV-E Topological Conditions for Privacy Preservation

We now establish necessary topological conditions that ensure privacy for
every $v_{j}\in\mathcal{V}_{p}$ which follows Algorithm 1.

######  Proposition 1.

Consider a fixed strongly connected digraph
$\mathcal{G}_{d}=(\mathcal{V},\mathcal{E})$ with $n=|\mathcal{V}|$ nodes.
Assume that a subset of nodes $v_{j}\in\mathcal{V}_{p}$ follow Algorithm 1
where they choose the set of subsets chosen as in (4a)–(4e). Curious nodes
$v_{c}\in\mathcal{V}_{c}$ will not be able to identify the initial state
$y_{j}[0]$ of $v_{j}\in\mathcal{V}_{p}$, as long as $v_{j}$ has at least one
in- or out-neighbor $v_{\ell}\in\mathcal{V}_{p}$ connected to it that aims to
preserve its privacy.

###### Proof.

In this proof we consider the following cases regarding the topological
conditions for privacy preservation during the execution of Algorithm 1. Then,
we summarize the results and derive the necessary and sufficient topological
conditions for privacy preservation.
A. Every in- and out-neighbor of node $v_{j}$ is curious (i.e.,
$v_{i}\in\mathcal{V}_{c}$, $\forall v_{i}\in\mathcal{N}_{j}^{-}$, and
$v_{l}\in\mathcal{V}_{c}$, $\forall v_{l}\in\mathcal{N}_{j}^{+}$). In this
case, the curious in- and out-neighbors communicate with each other and node
$v_{j}\in\mathcal{V}_{p}$ will not be able to keep its privacy. Specifically,
at Initialization curious nodes will know $u_{j}^{y}[0]$. Then, during the
Iteration procedure, curious nodes will know the messages $v_{j}$ has received
and the messages $v_{j}$ has transmitted. This means that they will be able to
determine the values of $u_{j}^{y}[s_{j}]\in\mathbb{Z}$, for
$s_{j}\in\\{1,2,...,\mathcal{D}_{max}^{+}\\}$. Note that the average of every
$u_{j}^{y}[s_{j}]$, for $s_{j}\in\\{0,1,2,...,\mathcal{D}_{max}^{+}\\}$, is
equal to $v_{j}$’s initial state $y_{j}[0]$. This means that curious nodes
will be able to determine the initial state $y_{j}[0]$. As a result, for the
case where every in- and out-neighbor of node $v_{j}$ is curious, node $v_{j}$
does not preserve the privacy of its initial state.
B. One out-neighbor of node $v_{j}$, say $v_{l^{\prime}}$, is neither curious
nor following the privacy preserving strategy (i.e.,
$v_{l^{\prime}}\in\mathcal{V}_{n}$), and all other in- and out-neighbors of
both nodes $v_{j}$, $v_{l^{\prime}}$ are curious (i.e.,
$v_{i}\in\mathcal{V}_{c}$, $\forall v_{i}\in\mathcal{N}_{j}^{-}$, and
$v_{l}\in\mathcal{V}_{c}$, $\forall
v_{l}\in\mathcal{N}_{j}^{+}\setminus\\{v_{l^{\prime}}\\}$). During the
Initialization procedure, curious nodes will know $y_{l^{\prime}}[0]$. Also,
during the Iteration procedure, curious nodes will know the messages $v_{j}$
has received and the messages $v_{j}$ has transmitted. Furthermore, curious
nodes can infer the input of node $v_{l}$ from its output. Then, they will be
able to extract the messages of node $v_{j}$ (as if a curious node was
directly connected to node $v_{j}$). As a result, for the case where one out-
neighbor of node $v_{j}$ is neither curious nor following the privacy
preserving protocol and every other in- and out-neighbor of node $v_{j}$ is
curious, $v_{j}$ does not preserve the privacy of its initial state.
C. One out-neighbor of node $v_{j}$, say $v_{l^{\prime}}$, is following the
privacy preserving strategy (i.e., $v_{l^{\prime}}\in\mathcal{V}_{p}$) and all
other in- and out-neighbors of both nodes $v_{j}$, $v_{l^{\prime}}$ are
curious (i.e., $v_{i}\in\mathcal{V}_{c}$, $\forall
v_{i}\in\mathcal{N}_{j}^{-}$, and $v_{l}\in\mathcal{V}_{c}$, $\forall
v_{l}\in\mathcal{N}_{j}^{+}\setminus\\{v_{l^{\prime}}\\}$). During the
Iteration procedure, curious nodes will not be able to infer the substates
transmitted from node $v_{j}$ to node $v_{l^{\prime}}$. As a result, curious
nodes will not be able to infer the initial state of node $v_{j}$ and the
initial state of node $v_{l^{\prime}}$. Thus, in this case node $v_{j}$
preserves the privacy of its initial state.
D. The case where one in-neighbor of $v_{j}$, say $v_{i^{\prime}}$, is
following the privacy preserving strategy and every in- and out-neighbors of
both nodes are curious can be analyzed as case C.

From the four cases A – D we considered, we have that a node
$v_{j}\in\mathcal{V}_{p}$ is able to preserve its privacy if it has at least
one in- or out-neighbor (say $v_{i^{\prime}}$ or $v_{l^{\prime}}$) who also
wants to preserve its privacy and follows the proposed privacy preserving
strategy. Furthermore, it is important to note that curious nodes will not be
able to determine (i) the values of the messages transmitted from
$v_{i^{\prime}}$ to $v_{j}$, and (ii) the values of the messages transmitted
from $v_{j}$ to $v_{l^{\prime}}$. This means that curious nodes will not be
able to determine a finite range $[\alpha,\beta]$ (where $\alpha<\beta$ and
$\alpha,\beta\in\mathbb{R}$) in which the initial state $y_{j}[0]$ lies in (as
already mentioned in Definition 1). ∎

######  Remark 2.

Note here that decomposing the initial state of every
$v_{j}\in\mathcal{V}_{p}$ into $\mathcal{D}_{max}^{+}+2$ substates is
essential for privacy preservation. The first set of substates is used as
$v_{j}$’s initial state. Then, $v_{j}$ transmits the rest
$\mathcal{D}_{max}^{+}+1$ substates towards its out-neighbors. This means that
$v_{j}$ transmits at least one set of privacy variables to every out-neighbor.
As a result, if $v_{l^{\prime}}\in\mathcal{V}_{p}$ (where
$v_{l^{\prime}}\in\mathbb{N}_{j}^{+}$), then $v_{l^{\prime}}$ receives (and
sums with its own mass variables) at least one set of $v_{j}$’s privacy
variables before it transmits every set of its own privacy variables towards
its out-neighbors.

In the above analysis, we are interested in whether the curious nodes can
exactly infer the value of another node. The case where a set of curious nodes
attempts to “estimate” the initial values is outside the scope of this paper
and will be considered as a future direction.

##  V SIMULATION RESULTS

In this section, we illustrate the behavior of Algorithm 1 and the advantages
of its operation. We analyze the scenario of $1000$ randomly generated
digraphs of $20$ nodes each where, the initial quantized state of each node
remained the same (for each one of the $1000$ randomly generated digraphs);
thus, the average of the nodes’ initial states remained equal to $q=13.4$.

Figure 2: Execution of Algorithm 1 averaged over $1000$ random digraphs of
$20$ nodes. Top figure: Average values of node state variables plotted against
the number of iterations (averaged over $1000$ random digraphs of $20$ nodes).
Middle Figure: Average total number of transmissions plotted against the
number of iterations (averaged over $1000$ random digraphs of $20$ nodes).
Bottom Figure: Average number of nodes performing transmissions plotted
against the number of iterations (averaged over $1000$ random digraphs of $20$
nodes).

In Fig. 2, we illustrate Algorithm 1 over a random digraph of $20$ nodes where
the average of the initial states is $q=13.4$. We show the average number of
time steps needed for quantized average consensus to be reached, the average
number of transmissions accumulated until each time step, and the average
number of nodes performing transmissions at each time step. We observe that
Algorithm 1 converges after $180$ time steps, with the average total number of
transmissions performed until $180$ time step being equal to $808.4$.
Additionally, we observe that the average number of nodes performing time
steps at each iteration becomes almost equal to zero after $50$ time steps,
and becomes eventually equal to zero after $180$ time steps.

Figure 3: Comparison between Algorithm 1, the event-based offset algorithm in
[14], and the initial zero-sum offset algorithm in [15]. Top figure: Average
values of node state variables plotted against the number of iterations for
Algorithm 1 (averaged over $1000$ random digraphs of $20$ nodes). Middle
Figure: Average values of node state variables plotted against the number of
iterations for the event-based offset algorithm in [14] (averaged over $1000$
random digraphs of $20$ nodes). Bottom Figure: Average values of node state
variables plotted against the number of iterations for the initial zero-sum
offset algorithm in [15] (averaged over $1000$ random digraphs of $20$ nodes).

In Fig. 3 we plot the node state variables averaged over $1000$ randomly
generated digraphs of $20$ nodes each, where the average of the initial states
is $q=13.4$. We compare Algorithm 1 against (i) the event-based offset
algorithm in [14] (see middle of Fig. 3), and (ii) the initial zero-sum offset
algorithm in [15] (see bottom of Fig. 3). In [14] (case (i)), the initial
offset for every node $v_{j}$ is $u_{j}\in[-100,-50]$ and the offset adding
steps are $L_{j}\in[20,40]$ during the execution. In [15] (case (ii)), the
initial offset for every node $v_{j}$ is $u_{j}\in[-100,100]$ and the offsets
are $u^{(l)}_{j}\in[-20,20]$, for every $v_{l}\in\mathcal{N}_{j}^{+}$. We
observe that Algorithm 1 converges after $185$ time steps and again
significantly outperforms the event-based offset algorithm in [14] which
converges after $362$ time steps. Furthermore, it is interesting to note that
Algorithm 1 requires almost the same time steps as the initial zero-sum offset
algorithm [15] which converges after $186$ time steps. However, note again
that in [15] each node performs multiple simultaneous transmissions of
different quantized values during the Initialization operation, as mentioned
in Section IV-C. Finally, note that neither [14] nor [15] exhibit finite
transmission capabilities. This makes Algorithm 1 the first algorithm in the
current literature in which each node (i) achieves the exact quantized average
of the initial states, (ii) terminates its transmission operation, and (iii)
preserves the privacy of its initial state.

##  VI CONCLUSIONS

In this paper, we presented a privacy-preserving event-triggered quantized
average consensus algorithm. The algorithm allows each node in the network to
calculate the exact quantized average of the initial states in the form of a
quantized fraction without revealing its initial quantized state to other
nodes. The privacy-preserving strategy takes full advantage of the algorithm’s
event-based nature and finite transmission capabilities and allows each node
to cease transmissions once convergence has been achieved without knowledge of
any global parameter (i.e., network diameter). We also analyzed the
algorithm’s finite time convergence and presented an upper bound on the
required number of time steps. Then, we presented necessary and sufficient
topological conditions under which the proposed algorithm allows nodes to
preserve their privacy. Finally, we demonstrated the performance of our
proposed algorithm and compared it against other algorithms in the existing
literature.

In the future, we plan to extend the algorithm’s operation to guarantee
privacy preservation for the case where curious nodes attempt to “estimate”
the initial values of other nodes.

## References

  * [1] P. Park, S. C. Ergen, C. Fischione, C. Lu, and K. H. Johansson, “Wireless network design for control systems: A survey,” _IEEE Communications Surveys & Tutorials_, vol. 20, no. 2, pp. 978–1013, 2018.
  * [2] S. Knorn, S. Dey, A. Ahlen, and D. E. Quevedo, “Optimal energy allocation in multisensor estimation over wireless channels using energy harvesting and sharing,” _IEEE Transactions on Automatic Control_ , vol. 64, no. 10, pp. 4337–4344, 2019.
  * [3] M. E. Chamie, J. Liu, and T. Basar, “Design and analysis of distributed averaging with quantized communication,” _IEEE Transactions on Automatic Control_ , vol. 61, no. 12, pp. 3870–3884, December 2016.
  * [4] A. I. Rikos and C. N. Hadjicostis, “Event-triggered quantized average consensus via ratios of accumulated values,” _IEEE Transactions on Automatic Control_ , vol. 64, no. 10, pp. 4035–4049, Oct. 2020.
  * [5] J. Cortés, G. E. Dullerud, S. Han, J. L. Ny, S. Mitra, and G. J. Pappas, “Differential privacy in control and network systems,” _in IEEE Conference on Decision and Control_ , pp. 4252–4272, 2016.
  * [6] E. Nozari, P. Tallapragada, and J. Cortés, “Differentially private average consensus: Obstructions, trade-offs, and optimal algorithm design,” _Automatica_ , vol. 81, pp. 221–231, 2017.
  * [7] N. Manitara and C. N. Hadjicostis, “Privacy-preserving asymptotic average consensus,” _in European Control Conference_ , pp. 760–765, 2013.
  * [8] Y. Mo and R. M. Murray, “Privacy preserving average consensus,” _IEEE Transactions on Automatic Control_ , vol. 62, no. 2, pp. 753–765, 2017\.
  * [9] N. Rezazadeh and S. S. Kia, “Privacy preservation in a continuous-time static average consensus algorithm over directed graphs,” _in American Control Conference (ACC)_ , pp. 5890–5895, 2018.
  * [10] Y. Wang, “Privacy-preserving average consensus via state decomposition,” _IEEE Transactions on Automatic Control_ , vol. 64, no. 11, pp. 4711–4716, 2019.
  * [11] I. L. D. Ridgley, R. A. Freeman, and K. M. Lynch, “Private and hot-pluggable distributed averaging,” _IEEE Control Systems Letters_ , vol. 4, no. 4, pp. 988–993, 2020.
  * [12] C. N. Hadjicostis, “Privary preserving distributed average consensus via homomorphic encryption,” in _IEEE Conference on Decision and Control_ , Dec. 2018, pp. 1258–1263.
  * [13] C. N. Hadjicostis and A. D. Dominguez-Garcia, “Privacy-preserving distributed averaging via homomorphically encrypted ratio consensus,” _IEEE Transactions on Automatic Control_ , vol. 65, no. 9, pp. 3887–3894, 2020.
  * [14] A. I. Rikos, T. Charalambous, K. H. Johansson, and C. N. Hadjicostis, “Privacy-preserving event-triggered quantized average consensus,” in _IEEE Conference on Decision and Control_ , 2020, pp. 6246–6253.
  * [15] ——, “Distributed event-triggered algorithms for finite-time privacy-preserving quantized average consensus,” _arXiv preprint arXiv:2102.06778_ , 2021.
  * [16] 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:2003.14183_ , 2021.
  * [17] T. Charalambous, N. E. Manitara, and C. N. Hadjicostis, “Privacy-preserving average consensus over digraphs in the presence of time delays,” _in Allerton Conference on Communication, Control, and Computing_ , pp. 238–245, 2019\.
  * [18] N. E. Manitara, A. I. Rikos, and C. N. Hadjicostis, “Privacy-preserving distributed average consensus in finite time using random gossip,” _arXiv preprint arXiv:2111.04642_ , 2021.
  * [19] M. K. Reiter and A. D. Rubin, “Crowds: Anonymity for web transactions,” _ACM Transactions on Information and System Security (TISSEC)_ , vol. 1, pp. 66–92, 1998.
  * [20] K. Chatzikokolakis and C. Palamidessi, “Probable innocence revisited,” _Theoretical Computer Science_ , vol. 367, no. 1-2, pp. 123–138, 2006.