Ordered and delayed adversaries and how to work against them on a shared channel

DOI10.1007/S00446-018-0341-7zbMATH Open1452.68270arXiv1706.08366OpenAlexW2963490172WikidataQ129265393 ScholiaQ129265393MaRDI QIDQ2010599FDOQ2010599

Authors: Marek Klonowski, Dariusz R. Kowalski, Jarosław Mirek 

Publication date: 27 November 2019

Published in: Distributed Computing (Search for Journal in Brave)

Abstract: In this work we define a class of ordered adversaries causing distractions according to some partial order fixed by the adversary before the execution, and study how they affect performance of algorithms. We focus on the Do-All problem of performing t tasks on a shared channel consisting of p crash-prone stations. The channel restricts communication: no message is delivered to the alive stations if more than one station transmits at the same time. The performance measure for the Do-All problem is work: the total number of available processor steps during the whole execution. We address the question of how the ordered adversaries controlling crashes of stations influence work performance of Do-All algorithms. The first presented algorithm solves Do-All with work O(t+psqrt{t}log p) against the Linearly-Ordered adversary, restricted by some pre-defined linear order of crashing stations. Another algorithm runs against the Weakly-Adaptive adversary, restricted by some pre-defined set of f crash-prone stations (it can be seen as restricted by the order being an anti-chain of crashing stations). The work done by this algorithm is O(t+psqrt{t}+pmin{p/(p-f),t}log p). Both results are close to the corresponding lower bounds from [CKL]. We generalize this result to the class of adversaries restricted by a partial order with a maximum anti-chain of size k and complement with the lower bound. We also consider a class of delayed adaptive adversaries, who could see random choices with some delay. We give an algorithm that runs against the 1-RD adversary (seeing random choices of stations with one round delay), achieving close to optimal O(t+psqrt{t}log^2 p) work complexity. This shows that restricting adversary by even 1 round delay results in (almost) optimal work on a shared channel.

Full work available at URL: https://arxiv.org/abs/1706.08366

Recommendations

• Restrained medium access control on adversarial shared channels
• Adversarial queuing on the multiple-access channel
• Adversarial queuing on the multiple access channel
• An efficient rational secret sharing protocol resisting against malicious adversaries over synchronous channels
• Adversarial multiple access channels with individual injection rates
• Building oblivious transfer on channel delays
• Asynchronous Secure Communication Tolerating Mixed Adversaries
• A Model for Adversarial Wiretap Channels
• Security against covert adversaries: Efficient protocols for realistic adversaries

zbMATH Keywords

randomized algorithmsdistributed algorithmstime complexitycrash failuresmultiple-access channeldelayed adversariesdo-allordered adversariesperforming tasksshared channeltransmission energy complexitywork complexity

Mathematics Subject Classification ID

Applications of game theory (91A80) Reliability, testing and fault tolerance of networks and computer systems (68M15) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Distributed algorithms (68W15) Distributed systems (68M14)

Cites Work

• Probability Inequalities for Sums of Bounded Random Variables
• On selection problem in radio networks
• A decomposition theorem for partially ordered sets
• A jamming-resistant MAC protocol for single-hop wireless networks
• Log-Logarithmic Selection Resolution Protocols in a Multiple Access Channel
• A lower bound on the time needed in the worst case to resolve conflicts deterministically in multiple access channels
• An $\Omega(D\log (N/D))$ Lower Bound for Broadcast in Radio Networks
• An asymptotically fast nonadaptive algorithm for conflict resolution in multiple-access channels
• Efficient algorithms for leader election in radio networks
• A perspective on multiaccess channels
• Performing Work Efficiently in the Presence of Faults
• Title not available (Why is that?)
• Randomization helps to perform independent tasks reliably
• Time-optimal message-efficient work performance in the presence of faults
• Efficient parallel algorithms can be made robust
• Performing work in broadcast networks
• Efficient gossip and robust distributed computation
• Title not available (Why is that?)
• Title not available (Why is that?)
• Performing tasks on synchronous restartable message-passing processors
• Development of the ALOHANET
• Performing work with asynchronous processors
• How to Scale Exponential Backoff: Constant Throughput, Polylog Access Attempts, and Robustness
• Broadcasting spanning forests on a multiple-access channel
• Approximating the Size of a Radio Network in Beeping Model

Cited In (2)

• Randomization helps to perform independent tasks reliably
• Not a COINcidence: sub-quadratic asynchronous Byzantine agreement WHP

This page was built for publication: Ordered and delayed adversaries and how to work against them on a shared channel

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2010599)