Degree 3 Suffices: A Large-Scale Overlay for P2P Networks Export

@incollection{bienkowski08degree3, abstract = {Most peer-to-peer (P2P) networks proposed until now have either logarithmic degree and logarithmic dilation or constant degree and logarithmic dilation. In the latter case (which is optimal up to constant factors), the constant degree is achieved either in expectation or with high probability. We propose the first overlay network, called SkewCCC, with a maximum degree of 3 (minimum possible) and logarithmic dilation. Our approach can be viewed as a decentralized and distorted version of a Cube Connected Cycles network. Additionally, basic network operations such as join and leave take logarithmic time and are very simple to implement, which makes our construction viable in fields other than P2P networks. A very good example is scatternet construction for Bluetooth devices, in which case it is crucial to keep the degree at most 7.}, author = {Bienkowski, Marcin and Brinkmann, Andr\'{e} and Korzeniowski, Miroslaw}, citeulike-article-id = {5891584}, citeulike-linkout-0 = {http://dx.doi.org/10.1007/978-3-540-92221-6_13}, citeulike-linkout-1 = {http://www.springerlink.com/content/d355137117278124}, doi = {10.1007/978-3-540-92221-6_13}, journal = {Principles of Distributed Systems}, keywords = {constant-degree, dilation, p2p, protocols}, pages = {184--196}, posted-at = {2009-10-29 11:43:04}, priority = {2}, title = {Degree 3 Suffices: A Large-Scale Overlay for P2P Networks}, url = {http://dx.doi.org/10.1007/978-3-540-92221-6_13}, year = {2008} }

TY - CHAP ID - bienkowski08degree3 L3 - citeulike-article-id:5891584 N2 - Most peer-to-peer (P2P) networks proposed until now have either logarithmic degree and logarithmic dilation or constant degree and logarithmic dilation. In the latter case (which is optimal up to constant factors), the constant degree is achieved either in expectation or with high probability. We propose the first overlay network, called SkewCCC, with a maximum degree of 3 (minimum possible) and logarithmic dilation. Our approach can be viewed as a decentralized and distorted version of a Cube Connected Cycles network. Additionally, basic network operations such as join and leave take logarithmic time and are very simple to implement, which makes our construction viable in fields other than P2P networks. A very good example is scatternet construction for Bluetooth devices, in which case it is crucial to keep the degree at most 7. JF - Principles of Distributed Systems EP - 196 TI - Degree 3 Suffices: A Large-Scale Overlay for P2P Networks SP - 184 KW - constant-degree KW - dilation KW - p2p KW - protocols AU - Bienkowski, Marcin AU - Brinkmann, André AU - Korzeniowski, Miroslaw PY - 2008/// UR - http://dx.doi.org/10.1007/978-3-540-92221-6_13 ER -