Brief announcement: Improving social-network-based Sybil-resilient node admission control

Nguyen Tran; Jinyang Li; Lakshminarayanan Subramanian; Sherman S.M. Chow

doi:10.1145/1835698.1835755

Brief announcement: Improving social-network-based Sybil-resilient node admission control

Nguyen Tran, Jinyang Li, Lakshminarayanan Subramanian, Sherman S.M. Chow

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

We present Gatekeeper, a decentralized protocol that performs Sybil-resilient node admission control based on a social network. Gatekeeper can admit most honest nodes while limiting the number of Sybils admitted per attack edge to O(log k), where k is the number of attack edges. Our result improves over SybilLimit [3] by a factor of log n in the face of O(1) attack edges. Even when the number of attack edges reaches O(n/log n), Gatekeeper only admits O(log n) Sybils per attack edge, similar to that achieved by SybilLimit.

Original language	English (US)
Title of host publication	PODC'10 - Proceedings of the 2010 ACM Symposium on Principles of Distributed Computing
Pages	241-242
Number of pages	2
DOIs	https://doi.org/10.1145/1835698.1835755
State	Published - 2010
Event	29th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, PODC 2010 - Zurich, Switzerland Duration: Jul 25 2010 → Jul 28 2010

Publication series

Name	Proceedings of the Annual ACM Symposium on Principles of Distributed Computing

Other

Other	29th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, PODC 2010
Country/Territory	Switzerland
City	Zurich
Period	7/25/10 → 7/28/10

Keywords

Gatekeeper
Social network
Sybil attack

ASJC Scopus subject areas

Software
Hardware and Architecture
Computer Networks and Communications

Access to Document

10.1145/1835698.1835755

Cite this

Tran, N., Li, J., Subramanian, L., & Chow, S. S. M. (2010). Brief announcement: Improving social-network-based Sybil-resilient node admission control. In PODC'10 - Proceedings of the 2010 ACM Symposium on Principles of Distributed Computing (pp. 241-242). (Proceedings of the Annual ACM Symposium on Principles of Distributed Computing). https://doi.org/10.1145/1835698.1835755

Brief announcement: Improving social-network-based Sybil-resilient node admission control. / Tran, Nguyen; Li, Jinyang ; Subramanian, Lakshminarayanan et al.
PODC'10 - Proceedings of the 2010 ACM Symposium on Principles of Distributed Computing. 2010. p. 241-242 (Proceedings of the Annual ACM Symposium on Principles of Distributed Computing).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Tran, N, Li, J , Subramanian, L & Chow, SSM 2010, Brief announcement: Improving social-network-based Sybil-resilient node admission control. in PODC'10 - Proceedings of the 2010 ACM Symposium on Principles of Distributed Computing. Proceedings of the Annual ACM Symposium on Principles of Distributed Computing, pp. 241-242, 29th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, PODC 2010, Zurich, Switzerland, 7/25/10. https://doi.org/10.1145/1835698.1835755

@inproceedings{4082dc4ca8354331a4a9f9779fe6385f,

title = "Brief announcement: Improving social-network-based Sybil-resilient node admission control",

abstract = "We present Gatekeeper, a decentralized protocol that performs Sybil-resilient node admission control based on a social network. Gatekeeper can admit most honest nodes while limiting the number of Sybils admitted per attack edge to O(log k), where k is the number of attack edges. Our result improves over SybilLimit [3] by a factor of log n in the face of O(1) attack edges. Even when the number of attack edges reaches O(n/log n), Gatekeeper only admits O(log n) Sybils per attack edge, similar to that achieved by SybilLimit.",

keywords = "Gatekeeper, Social network, Sybil attack",

author = "Nguyen Tran and Jinyang Li and Lakshminarayanan Subramanian and Chow, {Sherman S.M.}",

year = "2010",

doi = "10.1145/1835698.1835755",

language = "English (US)",

isbn = "9781605588889",

series = "Proceedings of the Annual ACM Symposium on Principles of Distributed Computing",

pages = "241--242",

booktitle = "PODC'10 - Proceedings of the 2010 ACM Symposium on Principles of Distributed Computing",

note = "29th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, PODC 2010 ; Conference date: 25-07-2010 Through 28-07-2010",

}

TY - GEN

T1 - Brief announcement

T2 - 29th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, PODC 2010

AU - Tran, Nguyen

AU - Li, Jinyang

AU - Subramanian, Lakshminarayanan

AU - Chow, Sherman S.M.

PY - 2010

Y1 - 2010

N2 - We present Gatekeeper, a decentralized protocol that performs Sybil-resilient node admission control based on a social network. Gatekeeper can admit most honest nodes while limiting the number of Sybils admitted per attack edge to O(log k), where k is the number of attack edges. Our result improves over SybilLimit [3] by a factor of log n in the face of O(1) attack edges. Even when the number of attack edges reaches O(n/log n), Gatekeeper only admits O(log n) Sybils per attack edge, similar to that achieved by SybilLimit.

AB - We present Gatekeeper, a decentralized protocol that performs Sybil-resilient node admission control based on a social network. Gatekeeper can admit most honest nodes while limiting the number of Sybils admitted per attack edge to O(log k), where k is the number of attack edges. Our result improves over SybilLimit [3] by a factor of log n in the face of O(1) attack edges. Even when the number of attack edges reaches O(n/log n), Gatekeeper only admits O(log n) Sybils per attack edge, similar to that achieved by SybilLimit.

KW - Gatekeeper

KW - Social network

KW - Sybil attack

UR - http://www.scopus.com/inward/record.url?scp=77956243747&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=77956243747&partnerID=8YFLogxK

U2 - 10.1145/1835698.1835755

DO - 10.1145/1835698.1835755

M3 - Conference contribution

AN - SCOPUS:77956243747

SN - 9781605588889

T3 - Proceedings of the Annual ACM Symposium on Principles of Distributed Computing

SP - 241

EP - 242

BT - PODC'10 - Proceedings of the 2010 ACM Symposium on Principles of Distributed Computing

Y2 - 25 July 2010 through 28 July 2010

ER -

Brief announcement: Improving social-network-based Sybil-resilient node admission control

Abstract

Publication series

Other

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this