Group Spreading

50 %
50 %
Information about Group Spreading

Published on January 20, 2008

Author: Sibilla


Group Spreading: A Protocol for Provably Secure Distributed Name Service:  Group Spreading: A Protocol for Provably Secure Distributed Name Service Christian Scheideler Dept. of Computer Science Johns Hopkins University Joint work with Baruch Awerbuch Name Service:  Name Service Peer: entity with a unique identity, i.e. identified by (Name(p), IP(p)) Goal: provide name service, i.e. each execution of Lookup(name) returns IP(p) of the peer p with Name(p)=name, or NULL if there is no such peer Name Service:  Name Service Static set of peers. Easiest solution: every peers knows every other peer. Problem: not scalable! Better solution: peers organize in a searchable overlay network of low degree. Chord:  Chord [Stoica, Morris, Karger, Kaashoek, and Balakrishnan ’01] Idea: organize peers in cycle according to hash function h:Names [0,1). 0.58 0.43 0.28 Hypercubic Shortcuts:  Hypercubic Shortcuts +1/2 +1/4 +1/8 +1/16 1 0 fingers x Hypercubic Pointer Structure:  Hypercubic Pointer Structure Lookup Operation:  Lookup Operation Lookup(name): ~log n number of hops Pure Chord cannot handle adversarial peers!! Can also handle dynamic set of peers. Distributed Name Service:  Distributed Name Service Dynamic set of peers, some adversarial. Operations: Join(p): peer p wants to join the system Leave(p): peer p wants to leave the system Lookup(name): returns IP(p) of the peer p with Name(p)=name, or NULL if there is no such peer Goal: Provide provably survivable distributed name service Prerequisites:  Prerequisites Certification authority: certifies (Name,IP) pairs so that collisions are avoided prevents adversarial peers from taking over identity of honest peers cannot prevent adversarial peers from registering (potentially many) own pairs Fighting at this front is fighting the wrong battle! Allow adversary to have infinitely many identities, but resources finite! Correctness:  Correctness Once Join(p) or Leave(p) terminates in p, it is called completed. p is called a member once Join(p) has completed. p ceases to be a member once it initiates Leave(p). Lookup(name) request executed correctly: If an honest peer p with Name(p)= name is currently a member of the system, returns IP(p). Otherwise, if such a peer has never been in the system or completed Leave(p) , returns NULL. Otherwise, returns IP(p) or NULL. Efficiency:  Efficiency Time unit: max time a message needs to travel from one honest peer to another An overlay network operation is called work-efficient if it is completed using a comm volume of at most polylog(n) bits time-efficient if it is completed in at most polylog(n) time units Overlay network maintainance should only need polylog(n) bits of comm per time unit per peer Peer-to-Peer Name Service:  Peer-to-Peer Name Service Idea: randomly distribute peers in overlay network [CAN,Chord,Pastry,…] Strategy: use pseudo-random hash function h:Names [0,1) Problem: adversarial peers a priori indistinguishable from honest peers Peer-to-Peer Name Service:  Peer-to-Peer Name Service Place peer p at h(name(p)) in [0,1): randomly distributes honest peers may not randomly distribute adversarial peers Peer-to-Peer Name Service:  Peer-to-Peer Name Service Problem: adversarial peers can isolate honest peers Chord: connect to direct neighbors closest successor of h(Name(p))+1/2 i Peer-to-Peer Name Service:  Peer-to-Peer Name Service Alternative: Assign each peer p to a random ID(p) in [0,1) Peer-to-Peer Name Service:  Peer-to-Peer Name Service New attempt: Assign each peer p to a random ID(p) Limit lifetime of a peer Peer-to-Peer Name Service:  Peer-to-Peer Name Service So good approach: Assign random IDs Enforce limited lifetime But: How to interconnect the peers? How to generate random IDs? How to enforce limited lifetime? How to implement operations? Peer-to-Peer Name Service:  Peer-to-Peer Name Service How to interconnect the peers? Region approach: each peer has several nodes, each node v maintains rv=log n - loglog n + Q(1) +/- 1/2 +1/4 -1/4 +1/8 -1/8 Region: interval of size 1/2r starting at an integral multiple of 1/2r. 1/2rv = Q(log n / n) 0 1 x Peer-to-Peer Name Service:  Peer-to-Peer Name Service How to generate random IDs? Group approach: each peer maintains Q(log n) nodes, ID of new node generated by region a) b) c) Peer-to-Peer Name Service:  Peer-to-Peer Name Service How to enforce limited lifetime? Lifetime approach: Join operation implemented s.t. it either terminates in Q(log n) steps or does not succeed Honest nodes take median of age views of a node reported by nodes in region Honest nodes cut connections to nodes that are more than L=Q(log n) steps old Peer-to-Peer Name Service:  Peer-to-Peer Name Service How to implement operations? Join(p): p contacts a peer q in the system, q includes Q(log n) nodes for p into the system, from there p inserts entry (Name(p),IP(p)) into relevant region and takes over maintenance of its nodes Leave(p): p deletes entry (Name(p),IP(p)) and leaves the system Lookup(name): region routing, majority decision Assumptions:  Assumptions adversary e/log n - bounded join/leave rate of peers is O(1/log2 N) honest peers have infinite bandwidth (no DOS) assumptions about messages… A peer is honest if it is not under the control of the adversary at any time, it is reliable, and it contacted an honest peer in order to join the network. Related Work:  Related Work Classical distributed computing: Byzantine agreement, two-phase commit, linear overhead Proactive security: uses coding to protect data in dynamic environment, linear overhead Fixed-topology networks: only fail-stop faults, no Byzantine behavior Hash-based P2P networks: hinge on assumption that IDs are random Random or unpredictable placement (Freenet, Gnutella): hard to attack, but hard to find data Related Work:  Related Work [Sit and Morris 2001]: investigate various attacks and defenses including routing attacks, storage and retrieval attacks, DoS, and join/leave attacks [Castro, 2001]: replication algorithm tolerating Byzantine faults as long as 1/3 fraction of replicas faulty [Douceur, 2002]: Sybil attacks (adversaries forge multiple identities) [Castro, Druschel, Ganesh,… 2002]: strategies for secure nodeID assignment, routing table maintenance, and message forwarding BUT: no provably robust overlay construction Comparison:  Comparison Group Spreading: e/log N-bounded adversary Enforced Spreading: e-bounded adversary 1/2 0 fraction of adv nodes e/log N e polylog(N) N Trust-but-Verify Group Spreading Enforced Spreading work overhead Conclusions:  Conclusions It is possible to come up with provably robust overlay network constructions! Analysis hard… Model still unrealistic, but Rome was also not built in one day  Questions???? STOC 2005:  STOC 2005 When: May 22-24, 2005 Where: Baltimore, MD, USA Submission deadline: Nov 4, 5:59 pm EST Web Site:

Add a comment

Related presentations

Related pages

TED: Ideas worth spreading, home of TED Talks, is a global initiative about ideas worth spreading via TEDx, the TED Prize, TED Books, TED Conferences, TED-Ed and more.
Read more

Spreading Epilepsy Awareness Public Group | Facebook

Spreading Epilepsy Awareness has 2,191 members. SPREADING EPILEPSY AWARENESS IS AN OPEN GROUP Everyone can see what you post including those you don't...
Read more

Are group selfies spreading lice among teens? | CTV News

The next time you and your friends cram together for a group selfie, consider this: head lice may be crawling across your shoulders in search of a new home.
Read more

Grouplove – Wikipedia

2013: Spreading Rumours; 2016: Big Mess; EP. 2011: Grouplove; 2014: Ways to Go; 2014: I’m With You; 2015: Under the Covers; Singles. 2010: Colours ...
Read more

Spreading Globally | Kumon Group

Kumon offers learning opportunities in 49 different countries and regions around the world.
Read more

How One San Francisco Group is Spreading the Written Word ...

How One San Francisco Group is Spreading the Written Word for Good . There are dozens of bottles hidden across the city by the bay — they are filled with ...
Read more

Far-right group spreading anti-mosque message in Bendigo

The anti-Islam group that brought controversial Dutch politician Geert Wilders to Australia held a meeting in Bendigo to advise residents how to campaign ...
Read more

TUI Group – Der weltweit führende Touristikkonzern

Zur TUI Group zählen mehr als 300 Hotels, Resorts und Clubs mit rund 210.000 Betten in 24 Ländern, darunter auch so bekannte Marken wie RIU und Robinson.
Read more

Grouplove Official Website: Tour Dates

Grouplove - Big Mess Available Now. Skip directly to content. User Content Moderation Menu. Add Photo; Home; Tour Dates; Store; The new album from ...
Read more