PaperlayerView exact revision on arXiv

Source-linked AI summary

Resilient Randomized Quantized Consensus

Seyed Mehran Dibaji, Hideaki Ishii, Roberto Tempo

arXiv:1710.06994v1eess.SYcs.SY

TL;DR

Resilient consensus asks normal agents to agree despite malicious agents that may update arbitrarily, while finding the network connectivity needed to withstand attacks. The paper studies quantized MSR-style updates and randomizes quantization and asynchronous update times. It derives robustness-based conditions, including a spanning-tree condition when no malicious agents are present, and reports that randomization is critical while delays can leave normal agents divided.

  • Problem

    Resilient consensus seeks agreement among normal agents despite faulty agents’ arbitrary updates, and the paper addresses the minimum network requirement for resilience beyond the complete-graph settings common in much computer-science work.

    Source: §I · p. 1

  • Method

    The paper studies quantized MSR-style updates that filter extreme neighbor values, using randomized quantization and randomized update times for asynchronous agents.

    Source: §I · pp. 1–2, C. Resiliency Notions and Algorithm · p. 4

  • Results

    The paper derives robustness-based necessary and sufficient consensus conditions across update and delay settings; with no malicious agents, a directed spanning tree is necessary and sufficient for quantized consensus.

    Source: §1 · p. 6, §VII · p. 13

  • Takeaways & Limitations

    Randomization is critical to tight topological conditions, while asynchronous updates and delays can let malicious agents prevent normal agents from reaching consensus.

    Source: §VII · p. 13

Abstract

from arXiv · show

We consider the problem of multi-agent consensus where some agents are subject to faults/attacks and might make updates arbitrarily. The network consists of agents taking integer-valued (i.e., quantized) states under directed communication links. The goal of the healthy normal agents is to form consensus in their state values, which may be disturbed by the non-normal, malicious agents. We develop update schemes to be equipped by the normal agents whose interactions are asynchronous and subject to non-uniform and time-varying time delays. In particular, we employ a variant of the so-called mean subsequence reduced (MSR) algorithms, which have been long studied in computer science, where each normal agent ignores extreme values from its neighbors. We solve the resilient quantized consensus problems in the presence of totally/locally bounded adversarial agents and provide necessary and sufficient conditions in terms of the connectivity notion of graph robustness. Furthermore, it will be shown that randomization is essential both in quantization and in the updating times when normal agents interact in an asynchronous manner. The results are examined through a numerical example.

I. INTRODUCTION

The paper studies resilient consensus for integer-valued agents on directed, non-complete networks, seeking minimum connectivity conditions against malicious updates. It uses MSR-style filtering and examines how randomized quantization, update timing, and communication delays affect those conditions.

I. INTRODUCTION

  • Normal agents discard up to f largest and f smallest neighbor values in a quantized MSR update scheme, with necessary and sufficient network conditions studied for synchronous and asynchronous updates.The paper uses graph robustness to characterize the required network structure.Source: §I · p. 1
  • Randomization is used in quantization and asynchronous update times; randomized updates yield the synchronous case’s necessary-and-sufficient robustness condition, while deterministic updates can fail despite sufficient synchronous-case connectivity.The authors attribute the benefit intuitively to malicious agents having less information about normal agents’ behavior under gossiping.Source: §I · p. 2
  • With time-varying delays, additional connectivity is necessary for resilient consensus under deterministic and probabilistic updating, and a numerical example shows delays can let a malicious agent divide normal agents into groups.Without communication delays, randomization can prevent this type of vulnerability.Source: §I · p. 2
  • When no malicious agents are present, a spanning tree is necessary and sufficient for quantized consensus on directed networks, a result the authors describe as new for this setting.This is a special case of the paper’s main results.Source: §I · p. 2

A. Graph Theory Notions

  • Graph robustness measures how well groups in a network connect through multiple paths and is used to characterize resilient-consensus conditions.The paper uses the more general (r, s)-robustness notion to obtain tight necessary and sufficient conditions.Source: A. Graph Theory Notions · p. 3

B. Consensus among Integer-Valued Agents

For integer-valued agents, the update rule quantizes a weighted-average input, with probabilistic rounding. The setup also permits asynchronous updates and seeks probabilistic global consensus despite misbehaving agents.

B. Consensus among Integer-Valued Agents

  • Agents’ states and control inputs are constrained to integers, and a quantizer maps the real-valued update input to an integer-valued one.The paper motivates this setting by agents’ limited communication and memory.Source: B. Consensus among Integer-Valued Agents · p. 3
  • The quantizer randomly selects the floor or ceiling of its input, with the floor chosen with probability ⌈y⌉−y.The quantizer is described as probabilistic and distributed across agents.Source: B. Consensus among Integer-Valued Agents · p. 3
  • At each time step, any subset of agents may update while agents that do not update retain their previous states; updates are synchronous only when every agent updates at every step.The asynchronous control is represented by zeroing the relevant adjacency weights for agents that do not update.Source: B. Consensus among Integer-Valued Agents · pp. 3–4
  • The objective is probabilistic global consensus under possibly asynchronous local control despite agents that do not follow the prescribed control rule.Networks without malicious agents are included as a special case.Source: B. Consensus among Integer-Valued Agents · p. 4

C. Resiliency Notions and Algorithm

The QW-MSR algorithm gives normal agents a neighbor-local way to resist malicious values, and the synchronous result makes graph robustness an exact condition for almost-sure resilient quantized consensus under the f-total model.

C. Resiliency Notions and Algorithm

  • The paper distinguishes f-total faults, bounded network-wide, from f-local faults, bounded within each normal agent’s neighborhood.The maximum tolerable f depends on network size and topology; the paper gives tight bounds through robust-graph conditions.Source: C. Resiliency Notions and Algorithm · p. 4
  • QW-MSR trims up to f neighbor values above and f below an agent’s state, then updates without identifying malicious agents.Normal agents need only neighbor information and the known upper bound f on malicious agents.Source: C. Resiliency Notions and Algorithm · p. 4

III. RESILIENT CONSENSUS FOR SYNCHRONOUS NETWORKS

A. Characterization Based on Robust Graphs

1. Denote the final values of x

Without malicious agents, a directed spanning tree is exactly the condition for almost-sure quantized consensus. The paper also notes binary-state applicability and leaves convergence-time analysis for this setting to future research.

1. Denote the final values of x

  • When initial states are restricted to 0 and 1, normal agents remain binary and eventually agree; this also holds for all results in the paper.Source: §1 · p. 6
  • Worst-case convergence-time analysis is left for future research because the synchronous network is directed and switches according to the MSR mechanism.Source: §1 · p. 6
  • With no malicious agents, quantized consensus occurs almost surely if and only if the graph has a directed spanning tree.Source: §1 · p. 6

B. Role of Probabilistic Quantization

The paper shows why probabilistic quantization matters: deterministic one-sided rounding can prevent consensus even on robust networks, while randomized quantization is used to move agents out of the relevant boundary sets.

B. Role of Probabilistic Quantization

  • With ceil quantization, agents on a line graph initialized at their indices stay at their initial states, so consensus is impossible despite a spanning tree.The passage also describes a corresponding floor-quantizer failure with initial values n−i.Source: B. Role of Probabilistic Quantization · p. 7
  • In the five-node (2, 2)-robust example with f=1, ceil quantization leaves every normal agent at its initial value; floor quantization also fails with the stated alternative initialization.Source: B. Role of Probabilistic Quantization · p. 7
  • In the robustness proof, always-ceil rounding may leave X1 intact and always-floor rounding may leave X2 intact, motivating randomized quantization.Source: B. Role of Probabilistic Quantization · p. 7

IV. ASYNCHRONOUS NETWORKS: ENHANCING RESILIENCE VIA PROBABILISTIC UPDATES

Asynchronous update timing can create weaknesses that malicious agents exploit, while probabilistic updating is proposed to overcome them. For deterministic asynchronous updates, QW-MSR guarantees almost-sure resilient quantized consensus under a (2f + 1)-robust graph.

A. Deterministic Update Scheme

  • Under the f-total malicious model, deterministic asynchronous QW-MSR reaches resilient quantized consensus almost surely if the graph is (2f + 1)-robust.The result assumes randomized quantization and update schedule (10).Source: A. Deterministic Update Scheme · p. 7
  • Asynchrony makes the sufficient graph-robustness requirement more restrictive because malicious agents gain more ways to deceive normal agents.The text identifies this as the source of the gap between the synchronous and asynchronous conditions.Source: A. Deterministic Update Scheme · p. 7
  • A complete graph that is (3, 3)-robust can still fail to reach consensus under asynchronous updates with agents 1 and 2 malicious.Source: Figure 4 · p. 8

B. Discussion on Synchronous versus Asynchronous

Asynchronous schedules can let malicious agents divide normal agents into separate agreements, even on a complete graph. Randomized update times restore a chance of simultaneous updates, yielding an exact robustness condition without delays; the next section considers delayed information, which malicious agents can also exploit.

B. Discussion on Synchronous versus Asynchronous

  • With six agents, malicious agents 1 and 2 can make normal agents 3–4 and 5–6 converge to different values under asynchronous updates.The graph is complete and (3, 3)-robust; the two pairs agree at either 3 or 4, and either 5 or 6, respectively.Source: B. Discussion on Synchronous versus… · p. 8
  • In the f-total malicious model, consensus is impossible under asynchronous updates with fewer than 4f + 1 nodes, even on a complete graph; synchronously, a complete graph with 2f + 1 nodes is sufficient.Source: B. Discussion on Synchronous versus… · p. 8
  • Random update times give all normal agents a chance to update simultaneously, which supports an (f + 1, f + 1)-robustness condition for resilient consensus.Randomization also prevents malicious agents from predicting update times in advance.Source: B. Discussion on Synchronous versus… · p. 8, C. Probabilistic Update Scheme · p. 8

C. Probabilistic Update Scheme

  • With probabilistic updates and randomized quantization, resilient quantized consensus occurs almost surely if and only if the graph is (f + 1, f + 1)-robust.Source: C. Probabilistic Update Scheme · p. 8

V. RESILIENCE UNDER DELAYED COMMUNICATIONS

  • Delayed neighbor information creates another vulnerability: malicious agents can exploit delays to prevent consensus when the graph is insufficiently robust.Source: §V · p. 9

A. Problem Formulation and Algorithm

The delayed-communication formulation applies QW-MSR to quantized neighbor information that may be stale, while malicious agents retain arbitrary control. Delays are time-varying, non-uniform, and bounded.

A. Problem Formulation and Algorithm

  • Communication delays are time-varying, non-uniform, and bounded, and normal agents need not know the delay bound.Source: A. Problem Formulation and Algorithm · p. 9
  • Malicious agents may choose arbitrary control inputs using current, non-delayed state information from any agent in the network.Source: A. Problem Formulation and Algorithm · p. 9
  • Normal agents use QW-MSR with the most recent delayed neighbor-state information available at each update.Their update is a quantized convex combination of neighbors’ state values, which may be delayed.Source: A. Problem Formulation and Algorithm · p. 9
  • The delay model uses each neighbor’s most recent available information rather than making neighbors wait for matching communication rounds.The round-based alternative can slow overall convergence when one agent’s transmission is delayed.Source: A. Problem Formulation and Algorithm · p. 9

B. Robust Graph Conditions: Deterministic Updates

For deterministic asynchronous updates with delayed information, the paper gives a sufficient robustness condition and a necessary one, leaving a gap. Randomized updates retain the deterministic sufficient condition under delays, where non-uniform delays may prevent randomization from tightening the topology requirement.

B. Robust Graph Conditions: Deterministic Updates

  • With deterministic asynchronous updates and delayed information, (2f + 1)-robustness suffices for almost-sure resilient quantized consensus under the f-total malicious model.The safety interval is determined by Sτ in (16).Source: B. Robust Graph Conditions:… · p. 9
  • For delayed information, almost-sure resilient consensus under QW-MSR requires the graph to be (f + 1, f + 1)-robust.This is a necessary condition under the f-total malicious model.Source: B. Robust Graph Conditions:… · p. 10

C. Effect of Non-uniform Delays and Probabilistic Updates

  • The paper leaves a gap between the delayed-network necessary and sufficient conditions, unlike the no-delay randomized case where (f + 1, f + 1)-robustness is necessary and sufficient.The text relates the gap to malicious agents exploiting non-uniform delays.Source: C. Effect of Non-uniform Delays and… · p. 10
  • Non-uniform delays may let a malicious agent appear to have different states to different normal agents, so randomized update times may not relax the robustness requirement.Source: C. Effect of Non-uniform Delays and… · p. 10
  • Under the f-total malicious model, randomly asynchronous quantized agents using QW-MSR with time-varying delayed information satisfying (11) reach resilient quantized consensus almost surely if the underlying graph is (2f + 1)-robust.The safety interval is determined by S.Source: C. Effect of Non-uniform Delays and… · p. 10

D. Further Results

With no malicious agents, delayed asynchronous quantized consensus has a directed-spanning-tree criterion. The f-local results and numerical examples illustrate how graph robustness bounds resilient consensus.

1) Normal Networks:

  • With no malicious agents, quantized consensus under delayed information occurs almost surely if and only if the graph has a directed spanning tree.The paper equates this condition with (1, 1)-robustness.Source: 1) Normal Networks · p. 10

2) f-Local Malicious Models:

  • For f-local malicious models, (2f + 1)-robustness is sufficient for resilient quantized consensus, while (f + 1, f + 1)-robustness is necessary.The conditions cover deterministic or randomized asynchronous updates, with or without information delays.Source: 2) f-Local Malicious Models · p. 10
  • The stated asynchronous QW-MSR results require at least 4f + 1 nodes in the underlying graph, attained with complete graphs.This minimum applies to f-total and f-local malicious models.Source: 2) f-Local Malicious Models · p. 11

VI. NUMERICAL EXAMPLE

  • A strongly connected but non-(2,2)-robust graph allowed a malicious agent to keep normal agents divided between states 1 and 10, with one agent fluctuating.The normal-only graph has a spanning tree, yet the malicious agent prevents agreement.Source: 1) Synchronous Networks · p. 11

1) Synchronous Networks:

  • On the (2, 2)-robust graph, normal agents reached x*=8 after 17 steps.This simulation illustrates the synchronous result.Source: 1) Synchronous Networks · p. 11

2) Asynchronous Networks without Delay:

The simulations show that robustness requirements depend on update timing and communication delays. In delayed settings, the original graph fails to reach consensus even with randomized updates, whereas a 3-robust graph succeeds.

2) Asynchronous Networks without Delay:

  • Under the QW-MSR algorithm on the original graph G in Fig. 5(a), normal agents did not change their state values at all; the graph met the necessary, but not sufficient, condition.After G was modified to become 3-robust, normal agents agreed on x*=4 after 20 time steps.Source: 2) Asynchronous Networks without Delay · p. 11
  • With probabilistic updates (p = 0.5) on the (2, 2)-robust graph in Fig. 5(a), normal agents reached x*=7 after 28 time steps, showing randomization can relax required network robustness.Source: 2) Asynchronous Networks without Delay · p. 12

3) Asynchronous and Delayed Networks with Deterministic Updates:

4) Asynchronous and Delayed Networks with Randomized Updates:

  • In delayed simulations, a malicious agent used communication delays to hide its jumps and keep normal agents in two groups at 1 and 10.The reported failure was independent of update times, including randomized updates.Source: 4) Asynchronous and Delayed Networks… · p. 12

VII. CONCLUSION

  • The paper derives necessary and sufficient robustness conditions across synchronous, asynchronous, deterministic, randomized, and delayed settings; randomization in quantization and update times is critical to tight topological conditions.It identifies convergence rates and applications to other multi-agent problems with malicious information as future work.Source: §VII · p. 13

APPENDIX: PROOF OF THEOREM 5.1

The proof establishes safety through monotone bounds on normal-agent states, then uses robustness and randomized quantization to show progress toward consensus.

APPENDIX: PROOF OF THEOREM 5.1

  • The normal agents' minimum and maximum state bounds are monotone, keeping their states within the interval S_tau.These bounds establish the proof's safety condition.Source: APPENDIX: PROOF OF THEOREM 5.1 · p. 13
  • Robustness ensures an extreme-state group has a node with enough incoming links from outside, while randomized quantization gives positive probability of moving an extreme state inward.The proof uses (2f + 1)-robustness and argues that the maximum or minimum state can change with positive probability.Source: APPENDIX: PROOF OF THEOREM 5.1 · pp. 13–14
  • Once normal agents reach consensus at x*, the update rule ignores differing values and keeps their states at x*.This establishes the proof's final consensus-preservation condition.Source: APPENDIX: PROOF OF THEOREM 5.1 · p. 14
Loading 1710.06994v1…