More Web Proxy on the site http://driver.im/

research-article

DepSpace: a byzantine fault-tolerant coordination service

Authors:

Alysson Neves Bessani,

Eduardo Pelison Alchieri,

Miguel Correia,

Joni Silva FragaAuthors Info & Claims

Eurosys '08: Proceedings of the 3rd ACM SIGOPS/EuroSys European Conference on Computer Systems 2008

Pages 163 - 176

https://doi.org/10.1145/1352592.1352610

Published: 01 April 2008 Publication History

Abstract

The tuple space coordination model is one of the most interesting coordination models for open distributed systems due to its space and time decoupling and its synchronization power. Several works have tried to improve the dependability of tuple spaces through the use of replication for fault tolerance and access control for security. However, many practical applications in the Internet require both fault tolerance and security. This paper describes the design and implementation of DepSpace, a Byzantine fault-tolerant coordination service that provides a tuple space abstraction. The service offered by DepSpace is secure, reliable and available as long as less than a third of service replicas are faulty. Moreover, the content-addressable confidentiality scheme developed for DepSpace bridges the gap between Byzantine fault-tolerant replication and confidentiality of replicated data and can be used in other systems that store critical data.

References

[1]

M. Abd-El-Malek, G. Ganger, G. Goodson, M. Reiter, and J. Wylie. Fault-scalable Byzantine fault-tolerant services. In Proceedings of the 20th ACM Symposium on Operating Systems Principles - SOSP'05, Oct. 2005.

Digital Library

[2]

M. K. Aguilera, A. Merchant, M. Shah, A. Veitch, and C. Karamanolis. Sinfonia: A new paradigm for building scalable distributed systems. In Proceedings of the 21st ACM Symposium on Operating Systems Principles - SOSP'07, Oct. 2007.

Digital Library

[3]

J. Albrecht, C. Tuttle, A. C. Snoeren, and A. Vahdat. Loose synchronization for large-scale networked systems. In Proceedings of the 2006 Usenix Annual Technical Conference - Usenix'06, 2006.

Digital Library

[4]

A. Avizienis, J.-C. Laprie, B. Randell, and C. Landwehr. Basic concepts and taxonomy of dependable and secure computing. IEEE Transactions on Dependable and Secure Computing, 1(1):11--33, Mar. 2004.

Digital Library

[5]

D. E. Bakken and R. D. Schlichting. Supporting fault-tolerant parallel programing in Linda. IEEE Transactions on Parallel and Distributed Systems, 6(3):287--302, Mar. 1995.

Digital Library

[6]

A. N. Bessani, M. Correia, J. S. Fraga, and L. C. Lung. Sharing memory between Byzantine processes using policy-enforced tuple spaces. In Proceedings of 26th IEEE International Conference on Distributed Computing Systems - ICDCS 2006, July 2006.

Digital Library

[7]

A. N. Bessani, M. Correia, J. S. Fraga, and L. C. Lung. Decoupled quorum-based Byzantine-resilient coordination in open distributed systems. Technical Report DI-FCUL TR 07-9, Dep. of Informatics, University of Lisbon, May 2007.

[8]

M. Burrows. The chubby lock service. In Proceedings of 7th Symposium on Operating Systems Design and Implementations - OSDI 2006, Nov. 2006.

[9]

N. Busi, R. Gorrieri, R. Lucchi, and G. Zavattaro. SecSpaces: a data-driven coordination model for environments open to untrusted agents. Electronical Notes in Theoretical Computer Science, 68(3), 2003.

[10]

N. Busi, R. Gorrieri, and G. Zavattaro. On the expressiveness of Linda coordination primitives. Information and Computation, 156(1-2):90--121, Jan. 2000.

Digital Library

[11]

G. Cabri, L. Leonardi, and F. Zambonelli. Mobile agents coordination models for Internet applications. IEEE Computer, 33(2), 2000.

Digital Library

[12]

C. Cachin and S. Tessaro. Asynchronous verifiable information dispersal. In Proceedings of the 24th IEEE Symposium on Reliable Distributed Systems - SRDS 2005, Oct. 2005.

Digital Library

[13]

N. Carriero and D. Gelernter. How to write parallel programs: a guide to the perplexed. ACM Computing Surveys, 21(3):323--357, Sept. 1989.

Digital Library

[14]

M. Castro and B. Liskov. Practical Byzantine fault-tolerance and proactive recovery. ACM Transactions on Computer Systems, 20(4), 2002.

Digital Library

[15]

M. Castro, R. Rodrigues, and B. Liskov. BASE: Using abstraction to improve fault tolerance. ACM Transactions on Computer Systems, 21(3), Aug. 2003.

Digital Library

[16]

T. Chandra, R. Griesemer, and J. Redstone. Paxos made live - an engineering perspective (2006 invited talk). In Proceedings of the 26th ACM Symposium on Principles of Distributed Computing - PODC'07, Aug. 2007.

Digital Library

[17]

Codehaus. Groovy programing language homepage. Avaliable at http://groovy.codehaus.org/, 2006.

[18]

J. Cowling, D. Myers, B. Liskov, R. Rodrigues, and L. Shrira. HQ-Replication: A hybrid quorum protocol for Byzantine fault tolerance. In Proceedings of 7th Symposium on Operating Systems Design and Implementations - OSDI 2006, Nov. 2006.

Digital Library

[19]

C. Dwork, N. A. Lynch, and L. Stockmeyer. Consensus in the presence of partial synchrony. Journal of the ACM, 35(2):288--322, Apr. 1988.

Digital Library

[20]

F. Favarim, J. S. Fraga, L. C. Lung, and M. Correia. GridTS: A new approach for fault-tolerant scheduling in grid computing. In Proceedings of 6th IEEE Symposium on Network Computing and Applications - NCA 2007, July 2007.

[21]

J. S. Fraga and D. Powell. A fault- and intrusion-tolerant file system. In Proceedings of the 3rd International Conference on Computer Security, 1985.

[22]

D. Gelernter. Generative communication in Linda. ACM Transactions on Programing Languages and Systems, 7(1):80--112, Jan. 1985.

Digital Library

[23]

GigaSpaces. GigaSpaces - write once, scale anywere. Avaliable at http://www.gigaspaces.com/, 2007.

[24]

G. R. Goodson, J. J. Wylie, G. R. Ganger, and M. K. Reiter. Efficient Byzantine-tolerant erasure-coded storage. In Proceedings of Dependable Systems and Networks - DSN 2004, June 2004.

Digital Library

[25]

J. Hendricks, G. Ganger, and M. Reiter. Low-overhead Byzantine fault-tolerant storage. In Proceedings of the 21st ACM Symposium on Operating Systems Principles - SOSP'07, Oct. 2007.

Digital Library

[26]

M. Herlihy. Wait-free synchronization. ACM Transactions on Programing Languages and Systems, 13(1):124--149, Jan. 1991.

Digital Library

[27]

M. Herlihy and J. M. Wing. Linearizability: A correctness condition for concurrent objects. ACM Transactions on Programing Languages and Systems, 12(3):463--492, July 1990.

Digital Library

[28]

R. Kotla, L. Alvisi, M. Dahlin, A. Clement, and E. Wong. Zyzzyva: Speculative Byzantine fault tolerance. In Proceedings of the 21st ACM Symposium on Operating Systems Principles - SOSP'07, Oct. 2007.

Digital Library

[29]

S. Lakshmanan, M. Ahamad, and H. Venkateswaran. Responsive security for stored data. IEEE Transactions on Parallel and Distributed Systems, 14(9):818--828, Sept. 2003.

Digital Library

[30]

T. J. Lehman, A. Cozzi, Y. Xiong, J. Gottschalk, V. Vasudevan, S. Landis, P. Davis, B. Khavar, and P. Bowman. Hitting the distributed computing sweet spot with TSpaces. Computer Networks, 35(4):457--472, Mar. 2001.

Digital Library

[31]

M. A. Marsh and F. B. Schneider. CODEX: A robust and secure secret distribution system. IEEE Transactions on Dependable and Secure Computing, 1(1):34--47, Jan. 2004.

Digital Library

[32]

J.-P. Martin and L. Alvisi. Fast Byzantine consensus. IEEE Transactions on Dependable and Secure Computing, 3(3):202--215, July 2006.

Digital Library

[33]

N. H. Minsky, Y. M. Minsky, and V. Ungureanu. Making tuple-spaces safe for heterogeneous distributed systems. In Proceedings of the 15th ACM Symposium on Applied Computing - SAC 2000, 2000.

Digital Library

[34]

R. R. Obelheiro, A. N. Bessani, L. C. Lung, and M. Correia. How practical are intrusion-tolerant distributed systems? DI-FCUL TR 06-15, Dep. of Informatics, University of Lisbon, Sept. 2006.

[35]

F. B. Schneider. Implementing fault-tolerant service using the state machine aproach: A tutorial. ACM Computing Surveys, 22(4), 1990.

Digital Library

[36]

B. Schoenmakers. A simple publicly verifiable secret sharing scheme and its application to electronic voting. In Proceedings of the 19th International Cryptology Conference on Advances in Cryptology - CRYPTO'99, Aug. 1999.

Digital Library

[37]

E. J. Segall. Resilient distributed objects: Basic results and applications to shared spaces. In Proceedings of the 7th IEEE Symposium on Parallel and Distributed Processing - SPDP'95, Oct. 1995.

Digital Library

[38]

A. Shamir. How to share a secret. Communications of ACM, 22(11):612--613, Nov. 1979.

Digital Library

[39]

Sun Microsystems. JavaSpaces service specification. Availiable at http://www.jini.org/standards, 2003.

[40]

P. Verissimo, N. F. Neves, and M. P. Correia. Intrusion-tolerant architectures: Concepts and design. In Architecting Dependable Systems, volume 2677 of LNCS. 2003.

Digital Library

[41]

J. Vitek, C. Bryce, and M. Oriol. Coordination processes with Secure Spaces. Science of Computer Programming, 46(1-2):163--193, Jan. 2003.

Digital Library

[42]

B. White, J. Lepreau, L. Stoller, R. Ricci, S. Guruprasad, M. Newbold, M. Hibler, C. Barb, and A. Joglekar. An integrated experimental environment for distributed systems and networks. In Proceedings of 5th Symposium on Operating Systems Design and Implementations - OSDI 2002, Dec. 2002.

Digital Library

[43]

A. Xu and B. Liskov. A design for a fault-tolerant, distributed implementation of Linda. In Proceedings of the 19th Symposium on Fault-Tolerant Computing - FTCS'89, June 1989.

[44]

J. Yin, J.-P. Martin, A. Venkataramani, L. Alvisi, and M. Dahlin. Separating agreement form execution for Byzantine fault tolerant services. In Proceedings of the 19th ACM Symposium on Operating Systems Principles - SOSP'03, Oct. 2003.

Digital Library

[45]

P. Zielinski. Paxos at war. Technical Report UCAM-CL-TR-593, University of Cambridge Computer Laboratory, June 2004.

Cited By

Carvalho TCasimiro ABessani A(2024)On the Design of Coordination Services for IoT2024 54th Annual IEEE/IFIP International Conference on Dependable Systems and Networks - Supplemental Volume (DSN-S)10.1109/DSN-S60304.2024.00019(38-42)Online publication date: 24-Jun-2024
https://doi.org/10.1109/DSN-S60304.2024.00019
Kurnia FVenkataramani A(2023)Oblivious PaxosProceedings of the 2023 ACM Symposium on Cloud Computing10.1145/3620678.3624647(65-80)Online publication date: 30-Oct-2023
https://dl.acm.org/doi/10.1145/3620678.3624647
Khan MBabay A(2023)Making Intrusion Tolerance Accessible: A Cloud-Based Hybrid Management Approach to Deploying Resilient Systems2023 42nd International Symposium on Reliable Distributed Systems (SRDS)10.1109/SRDS60354.2023.00033(254-267)Online publication date: 25-Sep-2023
https://doi.org/10.1109/SRDS60354.2023.00033
Show More Cited By

Index Terms

DepSpace: a byzantine fault-tolerant coordination service

Recommendations

DepSpace: a byzantine fault-tolerant coordination service
EuroSys '08

The tuple space coordination model is one of the most interesting coordination models for open distributed systems due to its space and time decoupling and its synchronization power. Several works have tried to improve the dependability of tuple spaces ...
Multi-Threshold Byzantine Fault Tolerance
CCS '21: Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security

Classic Byzantine fault tolerant (BFT) protocols are designed for a specific timing model, most often one of the following: synchronous, asynchronous or partially synchronous. It is well known that the timing model and fault tolerance threshold present ...
Responsive Security for Stored Data
ICDCS '03: Proceedings of the 23rd International Conference on Distributed Computing Systems

We present the design of a distributed store that offersvarious levels of security guarantees while tolerating a limitednumber of nodes that are compromised by an adversary.The store uses secret sharing schemes to offer securityguarantees namely ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

Eurosys '08: Proceedings of the 3rd ACM SIGOPS/EuroSys European Conference on Computer Systems 2008

April 2008

346 pages

ISBN:9781605580135

DOI:10.1145/1352592

General Chair:
Joe Sventek
University of Glasgow, UK
,
Program Chair:
Steven Hand
University of Cambridge, UK

ACM SIGOPS Operating Systems Review Volume 42, Issue 4
EuroSys '08
May 2008
321 pages
ISSN:0163-5980
DOI:10.1145/1357010
Issue’s Table of Contents

Copyright © 2008 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 April 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

Eurosys '08

Sponsor:

Eurosys '08: Eurosys 2008 Conference

April 1 - 4, 2008

Glasgow, Scotland UK

Acceptance Rates

Overall Acceptance Rate 241 of 1,308 submissions, 18%

Upcoming Conference

EuroSys '25

Sponsor:
sigops

Twentieth European Conference on Computer Systems

March 30 - April 3, 2025

Rotterdam , Netherlands

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

66
Total Citations
View Citations
737
Total Downloads

Downloads (Last 12 months)11
Downloads (Last 6 weeks)0

Reflects downloads up to 06 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Carvalho TCasimiro ABessani A(2024)On the Design of Coordination Services for IoT2024 54th Annual IEEE/IFIP International Conference on Dependable Systems and Networks - Supplemental Volume (DSN-S)10.1109/DSN-S60304.2024.00019(38-42)Online publication date: 24-Jun-2024
https://doi.org/10.1109/DSN-S60304.2024.00019
Kurnia FVenkataramani A(2023)Oblivious PaxosProceedings of the 2023 ACM Symposium on Cloud Computing10.1145/3620678.3624647(65-80)Online publication date: 30-Oct-2023
https://dl.acm.org/doi/10.1145/3620678.3624647
Khan MBabay A(2023)Making Intrusion Tolerance Accessible: A Cloud-Based Hybrid Management Approach to Deploying Resilient Systems2023 42nd International Symposium on Reliable Distributed Systems (SRDS)10.1109/SRDS60354.2023.00033(254-267)Online publication date: 25-Sep-2023
https://doi.org/10.1109/SRDS60354.2023.00033
Kirti MMaurya AYadav R(2023)A Fault‐tolerant model for tuple space coordination in distributed environmentsConcurrency and Computation: Practice and Experience10.1002/cpe.788436:1Online publication date: 7-Aug-2023
https://doi.org/10.1002/cpe.7884
Amiri MLoo BAgrawal DAbbadi A(2022)QanaatProceedings of the VLDB Endowment10.14778/3551793.355183515:11(2839-2852)Online publication date: 1-Jul-2022
https://dl.acm.org/doi/10.14778/3551793.3551835
Vassantlal RAlchieri EFerreira BBessani A(2022)COBRA: Dynamic Proactive Secret Sharing for Confidential BFT Services2022 IEEE Symposium on Security and Privacy (SP)10.1109/SP46214.2022.9833658(1335-1353)Online publication date: May-2022
https://doi.org/10.1109/SP46214.2022.9833658
Köstler JReiser HHabiger GHauck FHung CHong JBechini ASong E(2021)SmartStreamProceedings of the 36th Annual ACM Symposium on Applied Computing10.1145/3412841.3441904(213-222)Online publication date: 22-Mar-2021
https://dl.acm.org/doi/10.1145/3412841.3441904
Khan MBabay A(2021)Toward Intrusion Tolerance as a Service: Confidentiality in Partially Cloud-Based BFT Systems2021 51st Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN)10.1109/DSN48987.2021.00019(14-25)Online publication date: Jun-2021
https://doi.org/10.1109/DSN48987.2021.00019
Duan SLiu CWang XWu YXu SYesha YZhang H(2020)Intrusion-Tolerant and Confidentiality-Preserving Publish/Subscribe Messaging2020 International Symposium on Reliable Distributed Systems (SRDS)10.1109/SRDS51746.2020.00039(319-328)Online publication date: Sep-2020
https://doi.org/10.1109/SRDS51746.2020.00039
Gregor FOzga WVaucher SPires RLe Quoc DArnautov SMartin ASchiavoni VFelber PFetzer C(2020)Trust Management as a Service: Enabling Trusted Execution in the Face of Byzantine Stakeholders2020 50th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN)10.1109/DSN48063.2020.00063(502-514)Online publication date: Jun-2020
https://doi.org/10.1109/DSN48063.2020.00063
Show More Cited By

View Options

Login options

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

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents