×

Resilient consensus for multi-agent systems subject to differential privacy requirements. (English) Zbl 1429.93329

Summary: We consider multi-agent systems interacting over directed network topologies where a subset of agents is adversary/faulty and where the non-faulty agents have the goal of reaching consensus, while fulfilling a differential privacy requirement on their initial conditions. To address this problem, we develop an update law for the non-faulty agents. Specifically, we propose a modification of the so-called mean-subsequence-reduced (MSR) algorithm, the differentially private MSR (DP-MSR) algorithm, and characterize three important properties of the algorithm: correctness, accuracy and differential privacy. We show that if the network topology is \((2f+1)\)-robust, then the algorithm allows the non-faulty agents to reach consensus despite the presence of up to \(f\) faulty agents and we characterize the accuracy of the algorithm. Furthermore, we also show in two important cases that our distributed algorithm can be tuned to guarantee differential privacy of the initial conditions and the differential privacy requirement is related to the maximum network degree. The results are illustrated via simulations.

MSC:

93D50 Consensus
93A16 Multi-agent systems
93B70 Networked control
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Abbas, W.; Laszka, A.; Koutsoukos, X., Improving network connectivity and robustness using trusted nodes with application to resilient consensus, IEEE Transactions on Control of Network Systems, 5, 4, 2036-2048 (2018) · Zbl 1515.93059
[2] Albert, R.; Jeong, H.; Barabási, A.-L., Error and attack tolerance of complex networks, Nature, 406, 6794, 378 (2000)
[3] di Bernardo, M.; Fiore, D.; Russo, G.; Scafuti, F., Convergence, consensus and synchronization of complex networks via contraction theory, (Lü, J.; Yu, X.; Chen, G.; Yu, W., Complex systems and networks. Complex systems and networks, Understanding complex systems (2016), Springer: Springer Berlin, Heidelberg), 313-339
[4] Dibaji, S. M.; Ishii, H., Resilient consensus of second-order agent networks: Asynchronous update rules with delays, Automatica, 81, 123-132 (2017) · Zbl 1372.93011
[5] Dibaji, S. M.; Ishii, H.; Tempo, R., Resilient randomized quantized consensus, IEEE Transactions on Automatic Control, 63, 8, 2508-2522 (2018) · Zbl 1423.93013
[6] Dolev, D., The byzantine generals strike again, Journal of Algorithms, 3, 1, 14-30 (1982) · Zbl 0495.68093
[7] Dörfler, F.; Bullo, F., Synchronization in complex networks of phase oscillators: A survey, Automatica, 50, 6, 1539-1564 (2014) · Zbl 1296.93005
[8] Durrett, R., Probability: Theory and examples (2010), Cambridge University Press · Zbl 1202.60001
[9] Dwork, C.; Kenthapadi, K.; McSherry, F.; Mironov, I.; Naor, M., Our data, ourselves: Privacy via distributed noise generation, (Eurocrypt, Vol. 4004 (2006), Springer), 486-503 · Zbl 1140.94336
[10] Dwork, C.; McSherry, F.; Nissim, K.; Smith, A., Calibrating noise to sensitivity in private data analysis, (Proc. of the 3rd theory of cryptography conference (2006)), 265-284 · Zbl 1112.94027
[11] Fiore, D.; Russo, G., Resilient and private consensus in multi-agent systems, (Proc. of the european control conference (2019)), (in press)
[12] Fiore, D.; Russo, G.; di Bernardo, M., Exploiting nodes symmetries to control synchronization and consensus patterns in multiagent systems, IEEE Control Systems Letters, 1, 2, 364-369 (2017)
[13] Griggs, W.; Russo, G.; Shorten, R., Leader and leaderless multi-layer consensus with state obfuscation: An application to distributed speed advisory systems, IEEE Transactions on Intelligent Transportation Systems, 19, 3, 711-721 (2018)
[14] Han, S.; Topcu, U.; Pappas, G. J., Differentially private convex optimization with piecewise affine objectives, (Proc. of the 53rd IEEE conference on decision and control (2014)), 2160-2166
[15] Huang, M., Stochastic approximation for consensus: a new approach via ergodic backward products, IEEE Transactions on Automatic Control, 57, 12, 2994-3008 (2012) · Zbl 1369.93694
[16] Huang, M.; Dey, S.; Nair, G. N.; Manton, J. H., Stochastic consensus over noisy networks with Markovian and arbitrary switches, Automatica, 46, 10, 1571-1583 (2010) · Zbl 1204.93107
[17] Huang, M.; Manton, J. H., Coordination and consensus of networked agents with noisy measurements: Stochastic algorithms and asymptotic behavior, SIAM Journal on Control and Optimization, 48, 1, 134-161 (2009) · Zbl 1182.93108
[18] Huang, M.; Manton, J. H., Stochastic consensus seeking with noisy and directed inter-agent communication: Fixed and randomly varying topologies, IEEE Transactions on Automatic Control, 55, 1, 235-241 (2010) · Zbl 1368.94002
[19] Huang, Z.; Mitra, S.; Dullerud, G., Differentially private iterative synchronous consensus, (Proc. of the 2012 ACM workshop on privacy in the electronic society (2012)), 81-90
[20] Huang, Z.; Mitra, S.; Vaidya, N., Differentially private distributed optimization, (Proc. of the 2015 international conference on distributed computing and networking (2015)), 4:1-4:10
[21] Kieckhafer, R.; Azadmanesh, M., Reaching approximate agreement with mixed-mode faults, IEEE Transactions on Parallel and Distributed Systems, 5, 1, 53-63 (1994)
[22] Lamport, L.; Shostak, R.; Pease, M., The Byzantine generals problem, ACM Transactions on Programming Languages and Systems, 4, 3, 382-401 (1982) · Zbl 0483.68021
[23] Le Ny, J.; Pappas, G. J., Differentially private filtering, IEEE Transactions on Automatic Control, 59, 2, 341-354 (2014) · Zbl 1360.93701
[24] LeBlanc, H. J.; Koutsoukos, X. D., Consensus in networked multi-agent systems with adversaries, (Proc. of the 14th ACM international conference on hybrid systems: Computation and control (2011)), 281-290 · Zbl 1361.68276
[25] LeBlanc, H. J.; Koutsoukos, X. D., Low complexity resilient consensus in networked multi-agent systems with adversaries, (Proc. of the 15th ACM international conference on hybrid systems: Computation and control (2012)), 5-14 · Zbl 1361.68277
[26] LeBlanc, H. J.; Zhang, H.; Koutsoukos, X.; Sundaram, S., Resilient asymptotic consensus in robust networks, IEEE Journal on Selected Areas in Communications, 31, 4, 766-781 (2013)
[27] Mo, Y.; Murray, R. M., Privacy preserving average consensus, IEEE Transactions on Automatic Control, 62, 2, 753-765 (2017) · Zbl 1364.91048
[28] Monteil, J.; Russo, G., On the design of nonlinear distributed control protocols for platooning systems, IEEE Control Systems Letters, 1, 1, 140-145 (2017)
[29] Nozari, E.; Tallapragada, P.; Cortés, J., Differentially private average consensus: obstructions, trade-offs, and optimal algorithm design, Automatica, 81, 221-231 (2017) · Zbl 1372.93027
[30] Nozari, E.; Tallapragada, P.; Cortes, J., Differentially private distributed convex optimization via functional perturbation, IEEE Transactions on Control of Network Systems, 5, 1, 395-408 (2018) · Zbl 1507.90131
[31] Pasqualetti, F.; Bicchi, A.; Bullo, F., Consensus computation in unreliable networks: A system theoretic approach, IEEE Transactions on Automatic Control, 57, 1, 90-104 (2012) · Zbl 1369.93042
[32] Ren, W.; Beard, R. W., Consensus seeking in multiagent systems under dynamically changing interaction topologies, IEEE Transactions on Automatic Control, 50, 5, 655-661 (2005) · Zbl 1365.93302
[33] Russo, G.; di Bernardo, M., Solving the rendezvous problem for multi-agent systems using contraction theory, (Proceedings of the 48h IEEE conference on decision and control (CDC) held jointly with 2009 28th Chinese control conference (2009)), 5821-5826
[34] Senejohnny, D.; Tesi, P.; De Persis, C., A jamming-resilient algorithm for self-triggered network coordination, IEEE Transactions on Control of Network Systems, 5, 3, 981-990 (2018) · Zbl 1515.93117
[35] Su, L.; Vaidya, N. H., Reaching approximate byzantine consensus with multi-hop communication, Information and Computation, 255, 352-368 (2017) · Zbl 1371.68029
[36] Sundaram, S.; Hadjicostis, C. N., Distributed function calculation via linear iterative strategies in the presence of malicious agents, IEEE Transactions on Automatic Control, 56, 7, 1495-1508 (2011) · Zbl 1368.93140
[37] Tseng, L.; Vaidya, N. H., A note on fault-tolerant consensus in directed networks, ACM SIGACT News, 47, 3, 70-91 (2016)
[38] Usevitch, J.; Panagou, D., R-robustness and (r, s)-robustness of circulant graphs, (Proc. of the 56th IEEE conference on decision and control (2017)), 4416-4421
[39] Vaidya, N. (2012). Matrix representation of iterative approximate Byzantine consensus in directed graphs. arXiv preprint arXiv:1203.1888; Vaidya, N. (2012). Matrix representation of iterative approximate Byzantine consensus in directed graphs. arXiv preprint arXiv:1203.1888
[40] Vaidya, N.; Tseng, L.; Liang, G., Iterative approximate byzantine consensus in arbitrary directed graphs, (Proceedings of the 2012 ACM symposium on principles of distributed computing (2012)), 365-374 · Zbl 1301.68168
[41] Zhang, H.; Fata, E.; Sundaram, S., A notion of robustness in complex networks, IEEE Transactions on Control of Network Systems, 2, 3, 310-320 (2015) · Zbl 1370.90057
[42] Zhang, H.; Sundaram, S., Robustness of information diffusion algorithms to locally bounded adversaries, (Proc. of the American control conference (2012)), 5855-5861
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.