Article

PeerReview: practical accountability for distributed systems

Authors:

Andreas Haeberlen,

Petr Kouznetsov,

Peter DruschelAuthors Info & Claims

SOSP '07: Proceedings of twenty-first ACM SIGOPS symposium on Operating systems principles

Pages 175 - 188

https://doi.org/10.1145/1294261.1294279

Published: 14 October 2007 Publication History

Abstract

We describe PeerReview, a system that provides accountability in distributed systems. PeerReview ensures that Byzantine faults whose effects are observed by a correct node are eventually detected and irrefutably linked to a faulty node. At the same time, PeerReview ensures that a correct node can always defend itself against false accusations. These guarantees are particularly important for systems that span multiple administrative domains, which may not trust each other.PeerReview works by maintaining a secure record of the messages sent and received by each node. The record isused to automatically detect when a node's behavior deviates from that of a given reference implementation, thus exposing faulty nodes. PeerReview is widely applicable: it only requires that a correct node's actions are deterministic, that nodes can sign messages, and that each node is periodically checked by a correct node. We demonstrate that PeerReview is practical by applying it to three different types of distributed systems: a network filesystem, a peer-to-peer system, and an overlay multicast system.

Supplementary Material

JPG File (1294279.jpg)

Download
11.26 KB

index.html (index.html)

Slides from the presentation

Download
.93 KB

ZIP File (p175-slides.zip)

Supplemental material for PeerReview: practical accountability for distributed systems

Download
20.77 MB

Audio only (1294279.mp3)

Download
12.27 MB

Video (1294279.mp4)

Download
169.29 MB

References

[1]

A. S. Aiyer, L. Alvisi, A. Clement, M. Dahlin, J.-P. Martin, and C. Porth. BAR fault tolerance for cooperative services. In Proc. SOSP'05, Oct 2005.

Digital Library

[2]

L. Alvisi, D. Malkhi, E. T. Pierce, and M. K. Reiter. Fault detection for Byzantine quorum systems. IEEE Trans. Parallel Distrib. Syst., 12(9):996--1007, 2001.

Digital Library

[3]

R. Arends, R. Austein, M. Larson, D. Massey, and S. Rose. RFC 4033: DNS security introduction and requirements. http://www.ietf.org/rfc/rfc4033.txt, Mar 2005.

[4]

K. Argyraki, P. Maniatis, O. Irzak, and S. Shenker. An accountability interface for the Internet. In Proc. 14th ICNP, Oct 2007.

[5]

E. Barker, W. Barker, W. Burr, W. Polk, and M. Smid. Recommendation for key management. NIST Special Publication 800--57, revised Mar 2007.

[6]

H. Barringer, A. Goldberg, K. Havelund, and K. Sen. Rule-based runtime verification. In Proc. VMCAI'04, Jan 2004.

[7]

R. A. Bazzi and G. Neiger. Simplifying fault-tolerance: Providing the abstraction of crash failures. J. ACM, 48(3):499--554, 2001.

Digital Library

[8]

G. Bracha. Asynchronous Byzantine agreement protocols. Information and Computation, 75(2):130--143, Nov 1987.

Digital Library

[9]

G. Bracha and S. Toueg. Asynchronous consensus and broadcast protocols. Journal of the ACM, 32(4), 1985.

Digital Library

[10]

M. Castro. Practical Byzantine Fault Tolerance. PhD thesis, MIT LCS, Jan 2001.

[11]

M. Castro, P. Druschel, A. Ganesh, A. Rowstron, and D. S. Wallach. Secure routing for structured peer-to-peer overlay networks. In Proceedings of OSDI'02, Boston, MA, Dec 2002.

Digital Library

[12]

M. Castro, P. Druschel, A.-M. Kermarrec, A. Nandi, A. Rowstron, and A. Singh. SplitStream: High-bandwidth multicast in cooperative environments. In Proceedings of SOSP'03, Oct 2003.

Digital Library

[13]

M. Castro and B. Liskov. Practical Byzantine fault tolerance and proactive recovery. ACM Trans. Comput. Syst., 20(4):398--461, 2002.

Digital Library

[14]

M. Castro, R. Rodrigues, and B. Liskov. BASE: Using abstraction to improve fault tolerance. ACM Trans. Comput. Syst., 21(3):236--269, 2003.

Digital Library

[15]

T. D. Chandra and S. Toueg. Unreliable failure detectors for reliable distributed systems. Journal of the ACM, 43(2):225--267, Mar 1996.

Digital Library

[16]

B.-G. Chun, P. Maniatis, S. Shenker, and J. Kubiatowicz. Attested append-only memory: Making adversaries stick to their word. In Proc. SOSP, Oct 2007.

Digital Library

[17]

B. A. Coan. A compiler that increases the fault tolerance of asynchronous protocols. IEEE Trans. Computers, 37(12):1541--1553, 1988.

Digital Library

[18]

L. P. Cox and B. D. Noble. Samsara: Honor among thieves in peer-to-peer storage. In Proceedings of SOSP, Oct 2003.

Digital Library

[19]

D. E. Denning. An intrusion-detection model. IEEE Trans. on Software Engineering, 13(2):222--232, 1987.

Digital Library

[20]

R. Dingledine, M. J. Freedman, and D. Molnar. Peer-to-Peer: Harnessing the Power of Disruptive Technologies, chapter Accountability. O'Reilly and Associates, 2001.

[21]

J. R. Douceur. The Sybil attack. In Proceedings of IPTPS, Mar 2002.

Digital Library

[22]

A. Doudou, B. Garbinato, R. Guerraoui, and A. Schiper. Muteness failure detectors: Specification and implementation. In EDCC, pages 71--87, 1999.

Digital Library

[23]

T. Garfinkel, M. Rosenblum, and D. Boneh. Flexible OS support and applications for trusted computing. In Proc. HotOS'03, May 2003.

Digital Library

[24]

A. Haeberlen, P. Kouznetsov, and P. Druschel. PeerReview: Practical accountability for distributed systems. Technical Report 2007--3, Max Planck Institute for Software Systems.

[25]

A. Haeberlen, P. Kouznetsov, and P. Druschel. The case for Byzantine fault detection. In Proceedings of HotDep, Nov 2006.

Digital Library

[26]

A. Haeberlen, A. Mislove, and P. Druschel. Glacier: Highly durable, decentralized storage despite massive correlated failures. In Proc. NSDI, May 2005.

Digital Library

[27]

M. Jelasity, A. Montresor, and O. Babaoglu. Detection and removal of malicious peers in gossip-based protocols. In Proceedings of FuDiCo, Jun 2004.

[28]

S. D. Kamvar, M. T. Schlosser, and H. Garcia-Molina. The EigenTrust algorithm for reputation management in p2p networks. In Proc. 12th International WWW Conference, May 2003.

Digital Library

[29]

D. R. Karger, E. Lehman, F. T. Leighton, R. Panigrahy, M. S. Levine, and D. Lewin. Consistent hashing and random trees: Distributed caching protocols for relieving hot spots on the world wide web. In STOC, 1997.

Digital Library

[30]

S. T. Kent, C. Lynn, J. Mikkelson, and K. Seo. Secure border gateway protocol (S-BGP) -- real world performance and deployment issues. In NDSS, 2000.

[31]

K. P. Kihlstrom, L. E. Moser, and P. M. Melliar-Smith. Byzantine fault detectors for solving consensus. The Computer Journal, 46(1):16--35, 2003.

[32]

C. Ko, G. Fink, and K. Levitt. Automated detection of vulnerabilities in privileged programs using execution monitoring. In Proceedings of the 10th Computer Security Application Conference, Dec 1994.

[33]

L. Lamport. Using time instead of timeout for fault-tolerant distributed systems. ACM Trans. Prog. Lang. Syst., 6(2):254--280, 1984.

Digital Library

[34]

L. Lamport, R. Shostak, and M. Pease. The Byzantine generals problem. ACM Trans. Program. Lang. Syst., 4(3):382--401, 1982.

Digital Library

[35]

B. W. Lampson. Computer security in the real world. In Proc. Annual Computer Security Applications Conference, Dec 2000.

[36]

P. Laskowski and J. Chuang. Network monitors and contracting systems: competition and innovation. In Proc. SIGCOMM'06, pages 183--194, Sep 2006.

Digital Library

[37]

J. Li, M. Krohn, D. Mazières, and D. Sasha. Secure untrusted data repository (SUNDR). In Proceedings of OSDI 2004, Dec 2004.

Digital Library

[38]

D. Malkhi and M. K. Reiter. Unreliable intrusion detection in distributed computations. In CSFW, pages 116--125, 1997.

Digital Library

[39]

P. Maniatis and M. Baker. Secure history preservation through timeline entanglement. In Proc. of the 11th USENIX Security Symposium, Jan 2002.

Digital Library

[40]

A. Mislove, A. Post, A. Haeberlen, and P. Druschel. Experiences in building and operating ePOST, a reliable peer-to-peer application. In Proceedings of EuroSys 2006, Apr 2006.

Digital Library

[41]

A. Nandi, T.-W. Ngan, A. Singh, P. Druschel, and D. Wallach. Scrivener: Providing incentives in cooperative content distribution systems. In Proc. Middleware Conference, Nov 2005.

Digital Library

[42]

M. Naor and K. Nissim. Certificate revocation and certificate update. In Proc. USENIX Security Symposium, pages 217--228, 1998.

Digital Library

[43]

G. Neiger and S. Toueg. Automatically increasing the fault-tolerance of distributed systems. In PODC, pages 248--262, 1988.

Digital Library

[44]

D. Oppenheimer, A. Ganapathi, and D. A. Patterson. Why do internet services fail, and what can be done about it? In Proc. USITS'03, Mar 2003.

Digital Library

[45]

M. C. Pease, R. E. Shostak, and L. Lamport. Reaching agreement in the presence of faults. J. ACM, 27(2):228--234, 1980.

Digital Library

[46]

PeerReview project homepage. http://peerreview.mpi-sws.mpg.de/.

[47]

H. V. Ramasamy, A. Agbaria, and W. H. Sanders. A parsimonious approach for obtaining resource-efficient and trustworthy execution. IEEE Trans. on Dependable and Secure Comp., 4(1):1--17, Jan 2007.

Digital Library

[48]

P. Reynolds, O. Kennedy, E. G. Sirer, and F. B. Schneider. Securing BGP using external security monitors. Technical Report 2006--2065, Cornell University, Computing and Inform. Science, Dec 2006.

[49]

F. B. Schneider. Implementing fault-tolerant services using the state machine approach: a tutorial. ACM Computing Surveys, 22(4):299--319, 1990.

Digital Library

[50]

B. Schneier and J. Kelsey. Cryptographic support for secure logs on untrusted machines. In Proc. 7th USENIX Security Symposium, pages 53--62, Jan 1998.

Digital Library

[51]

A. Singh, T.-W. Ngan, P. Druschel, and D. Wallach. Eclipse attacks on overlay networks: Threats and defenses. In Proceedings of INFOCOM, Apr 2006.

[52]

T. K. Srikanth and S. Toueg. Simulating authenticated broadcasts to derive simple fault-tolerant algorithms. Distributed Computing, 2(2):80--94, 1987.

Digital Library

[53]

Sun Microsystems Inc. RFC 1094: Network file system protocol specification. http://www.ietf.org/rfc/rfc1094.txt, Mar 1989.

Digital Library

[54]

M. Waldman and D. Mazières. Tangler: a censorship-resistant publishing system based on document entanglements. In Proc. 8th ACM conf. on Comp. and Comm. Security, pages 126--135, 2001.

Digital Library

[55]

K. Walsh and E. G. Sirer. Experience with an object reputation system for peer-to-peer filesharing. In Proc. NSDI, May 2006.

Digital Library

[56]

J. Yin, J.-P. Martin, A. Venkataramani, L. Alvisi, and M. Dahlin. Separating agreement from execution for Byzantine fault tolerant services. In Proc. SOSP, pages 253--267, Oct 2003.

Digital Library

[57]

A. R. Yumerefendi and J. S. Chase. Trust but verify: Accountability for internet services. In ACM SIGOPS European Workshop, 2004.

Digital Library

[58]

A. R. Yumerefendi and J. S. Chase. The role of accountability in dependable distributed systems. In Proceedings of HotDep, Jun 2005.

Digital Library

[59]

A. R. Yumerefendi and J. S. Chase. Strong accountability for network storage. In FAST, 2007.

Digital Library

Cited By

Li JXiao YLi SLi T(2025)Designing accountable IoT systems to overcome IoT storage limitationComputers & Security10.1016/j.cose.2024.104118148(104118)Online publication date: Jan-2025
https://doi.org/10.1016/j.cose.2024.104118
Civit PDzulfikar MGilbert SGuerraoui RKomatovic JVidigueira MKuznetsov PGelles ROlivetti D(2024)DARE to Agree: Byzantine Agreement With Optimal Resilience and Adaptive CommunicationProceedings of the 43rd ACM Symposium on Principles of Distributed Computing10.1145/3662158.3662792(145-156)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3662158.3662792
Ranchal-Pedrosa AGramoli V(2024)ZLB: A Blockchain to Tolerate Colluding Majorities2024 54th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN)10.1109/DSN58291.2024.00032(209-222)Online publication date: 24-Jun-2024
https://doi.org/10.1109/DSN58291.2024.00032
Show More Cited By

Index Terms

PeerReview: practical accountability for distributed systems
1. Software and its engineering
  1. Software organization and properties
    1. Extra-functional properties
      1. Software fault tolerance
    2. Software system structures
      1. Distributed systems organizing principles
        Organizing principles for web applications

Recommendations

PeerReview: practical accountability for distributed systems
SOSP '07

We describe PeerReview, a system that provides accountability in distributed systems. PeerReview ensures that Byzantine faults whose effects are observed by a correct node are eventually detected and irrefutably linked to a faulty node. At the same time,...
Secure network provenance
SOSP '11: Proceedings of the Twenty-Third ACM Symposium on Operating Systems Principles

This paper introduces secure network provenance (SNP), a novel technique that enables networked systems to explain to their operators why they are in a certain state -- e.g., why a suspicious routing table entry is present on a certain router, or where ...
Reliable data-center scale computations
LADIS '10: Proceedings of the 4th International Workshop on Large Scale Distributed Systems and Middleware

Neither of the two broad classes of fault models considered by traditional fault tolerance techniques --- crash and Byzantine faults --- suit the environment of systems that run in today's data centers. On the one hand, assuming Byzantine faults is ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SOSP '07: Proceedings of twenty-first ACM SIGOPS symposium on Operating systems principles

October 2007

378 pages

ISBN:9781595935915

DOI:10.1145/1294261

General Chair:
Thomas C. Bressoud
Denison University, USA
,
Program Chair:
M. Frans Kaashoek
Massachusetts Institute of Technology, USA

ACM SIGOPS Operating Systems Review Volume 41, Issue 6
SOSP '07
December 2007
363 pages
ISSN:0163-5980
DOI:10.1145/1323293
Issue’s Table of Contents

Copyright © 2007 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: 14 October 2007

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

SOSP07

Sponsor:

SOSP07: ACM SIGOPS 21st Symposium on Operating Systems Principles 2007

October 14 - 17, 2007

Washington, Stevenson, USA

Acceptance Rates

Overall Acceptance Rate 131 of 716 submissions, 18%

Upcoming Conference

SOSP '25

Sponsor:
sigops

ACM SIGOPS 31st Symposium on Operating Systems Principles

October 13 - 16, 2025

Seoul , Republic of Korea

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

255
Total Citations
View Citations
2,080
Total Downloads

Downloads (Last 12 months)109
Downloads (Last 6 weeks)12

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Li JXiao YLi SLi T(2025)Designing accountable IoT systems to overcome IoT storage limitationComputers & Security10.1016/j.cose.2024.104118148(104118)Online publication date: Jan-2025
https://doi.org/10.1016/j.cose.2024.104118
Civit PDzulfikar MGilbert SGuerraoui RKomatovic JVidigueira MKuznetsov PGelles ROlivetti D(2024)DARE to Agree: Byzantine Agreement With Optimal Resilience and Adaptive CommunicationProceedings of the 43rd ACM Symposium on Principles of Distributed Computing10.1145/3662158.3662792(145-156)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3662158.3662792
Ranchal-Pedrosa AGramoli V(2024)ZLB: A Blockchain to Tolerate Colluding Majorities2024 54th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN)10.1109/DSN58291.2024.00032(209-222)Online publication date: 24-Jun-2024
https://doi.org/10.1109/DSN58291.2024.00032
Stokkink QPouwelse J(2023)A Local-First Approach for Green Smart ContractsDistributed Ledger Technologies: Research and Practice10.1145/3607196Online publication date: 3-Jul-2023
https://dl.acm.org/doi/10.1145/3607196
Chen ZFan LLiu SVukolić MWang XZhang J(2023)Bridging the Gap of Timing Assumptions in Byzantine ConsensusProceedings of the 24th International Middleware Conference10.1145/3590140.3629114(178-191)Online publication date: 27-Nov-2023
https://dl.acm.org/doi/10.1145/3590140.3629114
Castañeda ARodríguez GOshman RNolin AHalldorsson MBalliu A(2023)Asynchronous Wait-Free Runtime Verification and Enforcement of LinearizabilityProceedings of the 2023 ACM Symposium on Principles of Distributed Computing10.1145/3583668.3594563(90-101)Online publication date: 19-Jun-2023
https://dl.acm.org/doi/10.1145/3583668.3594563
Graf MKüsters RRausch D(2023)AUC: Accountable Universal Composability2023 IEEE Symposium on Security and Privacy (SP)10.1109/SP46215.2023.10179384(1148-1167)Online publication date: May-2023
https://doi.org/10.1109/SP46215.2023.10179384
Nemoto JYamada H(2023)The Case for Lazy Byzantine Fault Detection for Transactional Database Systems2023 IEEE 43rd International Conference on Distributed Computing Systems Workshops (ICDCSW)10.1109/ICDCSW60045.2023.00005(13-18)Online publication date: 18-Jul-2023
https://doi.org/10.1109/ICDCSW60045.2023.00005
Yoon M(2023)AccountNet: Accountable Data Propagation Using Verifiable Peer Shuffling2023 IEEE 43rd International Conference on Distributed Computing Systems (ICDCS)10.1109/ICDCS57875.2023.00050(48-61)Online publication date: Jul-2023
https://doi.org/10.1109/ICDCS57875.2023.00050
Ranchal-Pedrosa AGramoli V(2023)Basilic: Resilient-Optimal Consensus Protocols with Benign and Deceitful Faults2023 IEEE 36th Computer Security Foundations Symposium (CSF)10.1109/CSF57540.2023.00002(91-106)Online publication date: Jul-2023
https://doi.org/10.1109/CSF57540.2023.00002
Show More Cited By

View Options

Get Access

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