Tight Bounds on the Size of Fault-Tolerant Merging and Sorting Networks with Destructive Faults

DOI10.1137/S0097539796305298zbMath0937.68159OpenAlexW2022085444MaRDI QIDQ4268879

Leighton, Tom, Yuan Ma

Publication date: 28 October 1999

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0097539796305298

zbMATH Keywords

sortinglower boundscircuitsfault-toleranceprobabilistic analysis of algorithmsmergingcomparator networks

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Parallel algorithms in computer science (68W10) Circuits, networks (94C99)

Related Items (7)

Braking the \(\Theta(n\log^ 2 n)\) barrier for sorting with faults ⋮ Recursive merge sort with erroneous comparisons ⋮ Designing reliable algorithms in unreliable memories ⋮ Sorting and searching in faulty memories ⋮ The price of resiliency: a case study on sorting with memory faults ⋮ Approximate minimum selection with unreliable comparisons ⋮ Optimal resilient sorting and searching in the presence of memory faults

This page was built for publication: Tight Bounds on the Size of Fault-Tolerant Merging and Sorting Networks with Destructive Faults