article

Free access

Efficient dispersal of information for security, load balancing, and fault tolerance

Author:

Michael O. RabinAuthors Info & Claims

Journal of the ACM (JACM), Volume 36, Issue 2

Pages 335 - 348

https://doi.org/10.1145/62044.62050

Published: 01 April 1989 Publication History

PDF eReader

Abstract

An Information Dispersal Algorithm (IDA) is developed that breaks a file F of length L = ↿ F↾ into n pieces F_i, l ≤ i ≤ n, each of length ↿F_i↾ = L/m, so that every m pieces suffice for reconstructing F. Dispersal and reconstruction are computationally efficient. The sum of the lengths ↿F_i↾ is (n/m) · L. Since n/m can be chosen to be close to l, the IDA is space efficient. IDA has numerous applications to secure and reliable storage of information in computer networks and even on single disks, to fault-tolerant and efficient transmission of information in networks, and to communications between processors in parallel computers. For the latter problem provably time-efficient and highly fault-tolerant routing on the n-cube is achieved, using just constant size buffers.

References

[1]

ASMUTH, C. A., BLAKLEY, G.R. Pooling splitting and restituting information to overcome total failure of some channels of communication. In Proceedings of the 1982 Symposium on Security and Privacy. IEEE Society, New York, 1982, pp. 156-169.

Google Scholar

[2]

BERLEKAMP, E.R. Algebraic coding theory. McGraw-Hill, New York, 1968.

Google Scholar

[3]

HALL, M. Combinatorial Theory. Wiley, New York, 1980.

Google Scholar

[4]

HILLIS, W.D. The Connection Machine. MIT Press, Cambridge, Mass., 1985.

Crossref

Google Scholar

[5]

MIRSKY, L. An Introduction to Linear Algebra. Dover, New York, 1982.

Google Scholar

[6]

PIPPENGER, N. Parallel communication with limited buffers. In Proceedings of the IEEE 25th Symposium on Foundations of Computer Science. IEEE, New York, 1984, pp. 127-136.

Google Scholar

[7]

RABIN, M.O. Probabilistic algorithms in finite fields. SIAM J. Comput. 9, 1980, 273-280.

Google Scholar

[8]

RABIN, i.O. Fingerprinting by random polynomials. Tech. Rep. TR-15-81. Center for Research in Computing Technology. Harvard Univ., Cambridge, Mass., i 98 i.

Google Scholar

[9]

RAGHAVAN, P. Probabilistic construction of deterministic algorithms: Approximating packing integer programs. In Proceedings of the IEEE 27th Symposium on Foundations of Computer Science. lt:t:l:., r~ew York, i 986, pp. i 0- i 8.

Crossref

Google Scholar

[10]

SEITZ, C.L. The cosmic cube. Commun. ACM 28, 1 (Jan. 1985), 22-33.

Crossref

Google Scholar

[11]

SHAMIR, A. How to share a secret. Commun. ACM 22, 11 (Nov. 1979), 612-613.

Crossref

Google Scholar

[12]

llzlilZL, 11. 3. /-~ rnotael Ol )IIVIL; macn}nes anu a companson of various interconnection networks. IEEE Trans. Comput. 28, 12 (1979), 907-917.

Google Scholar

[13]

VALIANT, L. G. A scheme for fast parallel communication. SlAM J. Comput. 11, 2 (1982), 3g/-~ -lt-

Google Scholar

Cited By

View all

Tonkikh AFreitas LKuznetsov PGelles ROlivetti D(2024)Swiper: a new paradigm for efficient weighted distributed protocolsProceedings of the 43rd ACM Symposium on Principles of Distributed Computing10.1145/3662158.3662799(283-294)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3662158.3662799
Haeupler BPatel SRoeyskoe AStein CZuzic GMohar BShinkar IO'Donnell R(2024)Polylog-Competitive Deterministic Local Routing and SchedulingProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649678(812-822)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649678
Qin BLiu JXing XMeng WLiu Y(2024)Mitigating Centralization in Access Control System with Blockchain and Distributed Storage2024 IEEE International Conference on Blockchain (Blockchain)10.1109/Blockchain62396.2024.00051(340-345)Online publication date: 19-Aug-2024
https://doi.org/10.1109/Blockchain62396.2024.00051
Show More Cited By

Index Terms

Recommendations

Efficient Byzantine Fault-Tolerance

We present two asynchronous Byzantine fault-tolerant state machine replication (BFT) algorithms, which improve previous algorithms in terms of several metrics. First, they require only 2f+1 replicas, instead of the usual 3f+1. Second, the trusted ...
Redundancy Does Not Imply Fault Tolerance: Analysis of Distributed Storage Reactions to File-System Faults
Special Issue on FAST 2017 and Regular Papers

We analyze how modern distributed storage systems behave in the presence of file-system faults such as data corruption and read and write errors. We characterize eight popular distributed storage systems and uncover numerous problems related to file-...
Fault tolerance on star graphs
PAS '95: Proceedings of the First Aizu International Symposium on Parallel Algorithms/Architecture Synthesis

Fault tolerance capability is one of the advantages of multiprocessor systems. We prove that the fault tolerance of star graphs is 2n-5 with restriction to the forbidden faulty set. We propose an algorithm for examining the connectivity of star graphs ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Journal of the ACM Volume 36, Issue 2

April 1989

225 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/62044

Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 April 1989

Published in JACM Volume 36, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1,062
Total Citations
View Citations
8,241
Total Downloads

Downloads (Last 12 months)312
Downloads (Last 6 weeks)44

Reflects downloads up to 13 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Tonkikh AFreitas LKuznetsov PGelles ROlivetti D(2024)Swiper: a new paradigm for efficient weighted distributed protocolsProceedings of the 43rd ACM Symposium on Principles of Distributed Computing10.1145/3662158.3662799(283-294)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3662158.3662799
Haeupler BPatel SRoeyskoe AStein CZuzic GMohar BShinkar IO'Donnell R(2024)Polylog-Competitive Deterministic Local Routing and SchedulingProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649678(812-822)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649678
Qin BLiu JXing XMeng WLiu Y(2024)Mitigating Centralization in Access Control System with Blockchain and Distributed Storage2024 IEEE International Conference on Blockchain (Blockchain)10.1109/Blockchain62396.2024.00051(340-345)Online publication date: 19-Aug-2024
https://doi.org/10.1109/Blockchain62396.2024.00051
Guo CMa MLi XWang G(2024)The Rabin numbers of enhanced hypercubesJournal of Parallel and Distributed Computing10.1016/j.jpdc.2024.104905191(104905)Online publication date: Sep-2024
https://doi.org/10.1016/j.jpdc.2024.104905
Carrizales-Espinoza DSanchez-Gallegos DGonzalez-Compean JCarretero J(2024)StructMeshFuture Generation Computer Systems10.1016/j.future.2024.05.033159:C(353-369)Online publication date: 1-Oct-2024
https://dl.acm.org/doi/10.1016/j.future.2024.05.033
Lafourcade PMallordy LOlivier-Anclin CRobert L(2024)Secure Keyless Multi-party Storage SchemeComputer Security – ESORICS 202410.1007/978-3-031-70896-1_14(279-298)Online publication date: 6-Sep-2024
https://doi.org/10.1007/978-3-031-70896-1_14
Hall-Andersen MSimkin MWagner B(2024)FRIDA: Data Availability Sampling from FRIAdvances in Cryptology – CRYPTO 202410.1007/978-3-031-68391-6_9(289-324)Online publication date: 18-Aug-2024
https://dl.acm.org/doi/10.1007/978-3-031-68391-6_9
Mehak Mahato D(2024)Hop-Constrained Oblivious Routing Using Prim’s-Sollin’s AlgorithmAdvanced Information Networking and Applications10.1007/978-3-031-57942-4_43(444-452)Online publication date: 10-Apr-2024
https://doi.org/10.1007/978-3-031-57942-4_43
Reyes‐Anastacio HGonzalez‐Compeán JSosa‐Sosa VMarcelín‐Jiménez RMorales‐Sandoval M(2024)Kulla‐RIV: A composing model with integrity verification for efficient and reliable data processing servicesSoftware: Practice and Experience10.1002/spe.332854:8(1516-1542)Online publication date: 11-Mar-2024
https://doi.org/10.1002/spe.3328
Roy BRoy A(2023)IoT-Applicable Generalized Frameproof Combinatorial DesignsIoT10.3390/iot40300204:3(466-485)Online publication date: 21-Sep-2023
https://doi.org/10.3390/iot4030020
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

References

Cited By

Index Terms

Recommendations

Efficient Byzantine Fault-Tolerance

Redundancy Does Not Imply Fault Tolerance: Analysis of Distributed Storage Reactions to File-System Faults

Fault tolerance on star graphs

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations