Asynchronous non-bayesian learning in the presence of crash failures

Lili Su, Nitin H. Vaidya

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

This paper addresses the problem of non-Bayesian learning in multi-agent networks, where agents repeatedly collect local observations about an unknown state of the world, and try to collaboratively detect the true state through information exchange. We focus on the impact of failures and asynchrony – two fundamental factors in distributed systems – on the performance of consensus-based non-Bayesian learning. In particular, we assume the networked agents may suffer crash faults, and messages delay can be arbitrarily long but finite. 1. We characterize the minimal global identifiability of the network for any consensus-based non-Bayesian learning to work. 2. Finite time convergence rate is obtained. 3. As part of our convergence analysis, we obtain a generalization of a celebrated result by Wolfowitz and Hajnal to submatrices, which might be of independent interest.

Original languageEnglish (US)
Title of host publicationStabilization, Safety, and Security of Distributed Systems - 18th International Symposium, SSS 2016, Proceedings
EditorsFranck Petit, Borzoo Bonakdarpour
PublisherSpringer
Pages352-367
Number of pages16
ISBN (Print)9783319492582
DOIs
StatePublished - 2016
Event18th International Symposium on Stabilization, Safety, and Security of Distributed Systems, SSS 2016 - Lyon, France
Duration: Nov 7 2016Nov 10 2016

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10083 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other18th International Symposium on Stabilization, Safety, and Security of Distributed Systems, SSS 2016
Country/TerritoryFrance
CityLyon
Period11/7/1611/10/16

Keywords

  • Asynchrony
  • Crash failures
  • Distributed learning

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'Asynchronous non-bayesian learning in the presence of crash failures'. Together they form a unique fingerprint.

Cite this