Ordered and delayed adversaries and how to work against them on a shared channel
From MaRDI portal
Publication:2010599
randomized algorithmsdistributed algorithmstime complexitycrash failuresmultiple-access channeldelayed adversariesdo-allordered adversariesperforming tasksshared channeltransmission energy complexitywork complexity
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)
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.
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
Cites work
- scientific article; zbMATH DE number 1306905 (Why is no real title available?)
- scientific article; zbMATH DE number 1979510 (Why is no real title available?)
- scientific article; zbMATH DE number 2013838 (Why is no real title available?)
- A decomposition theorem for partially ordered sets
- A jamming-resistant MAC protocol for single-hop wireless networks
- A lower bound on the time needed in the worst case to resolve conflicts deterministically in multiple access channels
- A perspective on multiaccess 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
- Approximating the size of a radio network in beeping model
- Broadcasting spanning forests on a multiple-access channel
- Development of the ALOHANET
- Efficient algorithms for leader election in radio networks
- Efficient gossip and robust distributed computation
- Efficient parallel algorithms can be made robust
- How to Scale Exponential Backoff: Constant Throughput, Polylog Access Attempts, and Robustness
- Log-Logarithmic Selection Resolution Protocols in a Multiple Access Channel
- On selection problem in radio networks
- Performing Work Efficiently in the Presence of Faults
- Performing tasks on synchronous restartable message-passing processors
- Performing work in broadcast networks
- Performing work with asynchronous processors
- Probability Inequalities for Sums of Bounded Random Variables
- Randomization helps to perform independent tasks reliably
- Time-optimal message-efficient work performance in the presence of faults
Cited in
(2)
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)
