NDLI: Fault-Tolerant Multi-Agent Optimization: Optimal Iterative Distributed Algorithms

Please wait, while we are loading the content...

New Opportunities for PODC?: Massive, Volatile, but Highly Predictable Resources

A Distributed (2+ε)-Approximation for Vertex Cover in O(logδ/ε log log δ) Rounds

Analysing Snapshot Isolation

Deterministic Objects: Life Beyond Consensus

Concurrent Data Structures

Contention Resolution on a Fading Channel

Distributed Strong Diameter Network Decomposition: Extended Abstract

Space Bounds for Reliable Storage: Fundamental Limits of Coding

How Emerging Memory Technologies Will Have You Rethinking Algorithm Design

Information-Theoretic Lower Bounds on the Storage Cost of Shared Memory Emulation

A Faster Distributed Radio Broadcast Primitive: Extended Abstract

Search on a Line with Faulty Robots

Low-Congestion Shortcuts without Embedding

The Greedy Spanner is Existentially Optimal

Recoverable Mutual Exclusion: [Extended Abstract]

Unbeatable Set Consensus via Topological and Combinatorial Reasoning

Reliable Communication over Highly Connected Noisy Networks

Optimal Dynamic Distributed MIS

Specification and Complexity of Collaborative Text Editing

On the Complexity of Reader-Writer Locks: Extended Abstract

Broadcast Extensions with Optimal Communication and Round Complexity

Uniform Deployment of Mobile Agents in Asynchronous Rings

The Coalescing-Branching Random Walk on Expanders and the Dual Epidemic Process

MST in Log-Star Rounds of Congested Clique

A Randomized Concurrent Algorithm for Disjoint Set Union

A Polylogarithmic Gossip Algorithm for Plurality Consensus

Contention Resolution on Multiple Channels with Collision Detection

A Local Constant Factor MDS Approximation for Bounded Genus Graphs

Optimal Mobile Byzantine Fault Tolerant Distributed Storage: Extended Abstract

An Algorithm for Replicated Objects with Efficient Reads

Two-Bit Messages are Sufficient to Implement Atomic Read/Write Registers in Crash-prone Systems

Fault-Tolerant Multi-Agent Optimization: Optimal Iterative Distributed Algorithms

Ant-Inspired Density Estimation via Random Walks: Extended Abstract

Distributed Algorithms for Planar Networks I: Planar Embedding

Self-stabilizing Balls & Bins in Batches: The Power of Leaky Bins [Extended Abstract]

Noisy Rumor Spreading and Plurality Consensus

How Asynchrony Affects Rumor Spreading Time

On Efficient Distributed Construction of Near Optimal Routing Schemes: Extended Abstract

A Markov Chain Algorithm for Compression in Self-Organizing Particle Systems

Are Shared Objects Composable under an Oblivious Adversary?

How Proofs are Prepared at Camelot: Extended Abstract

Brief Announcement: Active Information Spread in Networks

Brief Announcement: Multi-Broadcasting under the SINR Model

Brief Announcement: Labeling Schemes for Power-Law Graphs

Brief Announcement: Local Independent Set Approximation

Rational Consensus: Extended Abstract

Brief Announcement: An Exponential Separation Between Randomized and Deterministic Complexity in the LOCAL Model

Brief Announcement: Deterministic Graph Connectivity in the Broadcast Congested Clique

A Complexity-Based Hierarchy for Multiprocessor Synchronization: [Extended Abstract]

Brief Announcement: A Family of Leaderless Generalized-Consensus Algorithms

Brief Announcement: Proactive Secret Sharing with a Dishonest Majority

Brief Announcement: Certified Universal Gathering in $R^{2}$ for Oblivious Mobile Robots

Brief Announcement: Using Read-k Inequalities to Analyze a Distributed MIS Algorithm

Brief Announcement: Sublinear-Space Distance Labeling Using Hubs

Brief Announcement: A Tight Space Bound for Consensus

Brief Announcement: Data Dissemination in Unified Dynamic Wireless Networks

Brief Announcement: Asynchronous Coordination with Constraints and Preferences

Brief Announcement: Computing in the Presence of Weak Crash Failures

Brief Announcement: Probabilistic Asynchronous Arbitrary Pattern Formation

Brief Announcement: A Key-Value Map for Massive Real-Time Analytics

Brief Announcement: Optimal Leader Election in Multi-Hop Radio Networks

Brief Announcement: Reliable Message Transmission under Partial Knowledge and General Adversaries

Brief Announcement: Oh-RAM! One and a Half Round Read/Write Atomic Memory

Brief Announcement: Pattern Formation Problem for Synchronous Mobile Robots in the Three Dimensional Euclidean Space

Brief Announcement: The Small World of Curious Beings

Brief Announcement: Self-stabilizing Clock Synchronization with 3-bit Messages

Brief Announcement: Space-Time Tradeoffs for Distributed Verification

Fault-Tolerant Multi-Agent Optimization: Optimal Iterative Distributed Algorithms

Content Provider	ACM Digital Library
Author	Su, Lili Vaidya, Nitin H.
Abstract	This paper addresses the problem of distributed multi-agent optimization in which each agent i has a local cost function $h_{i}(x),$ and the goal is to optimize a global cost function that aggregates the local cost functions. Such optimization problems are of interest in many contexts, including distributed machine learning, distributed resource allocation, and distributed robotics. We consider the distributed optimization problem in the presence of faulty agents. We focus primarily on Byzantine failures, but also briey discuss some results for crash failures. For the Byzantine fault-tolerant optimization problem, the ideal goal is to optimize the average of local cost functions of the non-faulty agents. However, this goal also cannot be achieved. Therefore, we consider a relaxed version of the fault-tolerant optimization problem. The goal for the relaxed problem is to generate an output that is an optimum of a global cost function formed as a convex combination of local cost functions of the non-faulty agents. More precisely, there must exist weights $α_{i}$ for i∈N such that $α_{i}$ ≥ 0 and ∑i≥ $Nα_{i}=1,$ and the output is an optimum of the cost function $∑_{i}≥$ N $α_{ihi}(x).$ Ideally, we would like $α_{i}=1/\|N\|$ for all i≥ N, however, this cannot be guaranteed due to the presence of faulty agents. In fact, the maximum number of nonzero weights $(α_{i's})$ that can be guaranteed is \|N\|-f, where f is the maximum number of Byzantine faulty agents. We present an iterative distributed algorithm that achieves optimal fault-tolerance. Specifically, it ensures that at least \|N\|-f agents have weights that are bounded away from 0 (in particular, lower bounded by 1/2\|N\|-f}). The proposed distributed algorithm has a simple iterative structure, with each agent maintaining only a small amount of local state. We show that the iterative algorithm ensures two properties as time goes to ∞: consensus (i.e., output of non-faulty agents becomes identical in the time limit), and optimality (in the sense that the output is the optimum of a suitably defined global cost function).
Starting Page	425
Ending Page	434
Page Count	10
File Format	PDF
ISBN	9781450339643
DOI	10.1145/2933057.2933105
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2016-07-25
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Distributed optimization Byzantine faults Complete net- works Fault-tolerant computing
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in