Transfer: Schedule when to transfer, random peer oracle

[dbosk]

We can probably do better than random peer sampling.

We can use the private scheduling theory from my Calendar Scheduling paper (CalendarScheduling-paper.pdf). Choosing nodes for the route is a scheduling problem, choose the ones who will be online at times T = {t+i : i \in S}, where S is the desired schedule. (Or rather choose until you have enough nodes that will be online at during T.)

[Adrien-Luxey]

Sure, but it would also require a more complex model, to have more interesting predictions.

Future works.

[Adrien-Luxey]

Here are my references for RPS, sorry I reacted so late: [1]M. Jelasity, S. Voulgaris, R. Guerraoui, A.-M. Kermarrec, et M. van Steen, « Gossip-based Peer Sampling », ACM Trans. Comput. Syst., vol. 25, nᵒ 3, août 2007. [2]S. Voulgaris, D. Gavidia, et M. van Steen, « CYCLON: Inexpensive Membership Management for Unstructured P2P Overlays », Journal of Network and Systems Management, vol. 13, nᵒ 2, p. 197‑217, juin 2005.

The most recent one (Gossip-based Peer Sampling) has a thorough study of the sampling's randomness. Essentially it's quite random, but there are complex properties around clustering coefficients of the output random graph. Anyway, consider it uniform random, it's not much of a problem for the whole lot of industrial applications using it.

[dbosk]

On Sun 29 Apr 2018 09:03:52 GMT, Adrien Luxey wrote:

Anyway, consider it uniform random, it's not much of a problem for the whole lot of industrial applications using it.

Well, that's the difference between reliability and security ;-)

I'll assume that the peer sampling is uniformly random in the theoretical analysis. This means that our scheme is not secure in practice.

[Adrien-Luxey]

Well, that's the difference between reliability and security ;-)

Boom, headshot!

From Gossip-based Peer Sampling (studying "local randomness"):

The results of the randomness tests suggest that the stream of nodes returned by the peer-sampling service is close to uniform random for all the protocol in- stances examined. Given that some widely used pseudo-random number gen- erators fail at least some of these tests, this is a highly encouraging result regarding the quality of the randomness provided by this class of sampling protocols. Based on these experiments we cannot, however, conclude on global random- ness of the resulting graphs. Local randomness, evaluated from a peer’s point of view, is important, however, in a complex large-scale distributed system, where the stream of random nodes returned by the nodes might have compli- cated correlations, merely looking at local behavior does not reveal some key characteristics such as load balancing (existence of bottlenecks) and fault toler- ance. In Section 4 we present a detailed analysis of the global properties of our protocols.

The whole Global Randomness section goes in-depth in in-degree distribution, average path length, clustering coefficient and such. Since they cover several algorithm variations, they get different results. But they show that after 20 cycles of initialization, some algorithms make the views change fast in addition to have them uniformly random.

You can cite this article, really. It's this ref: Jelasity_Voulgaris_Guerraoui_Kermarrec_van_Steen_2007.

There is also byzantine tolerant Peer sampling: [1]G. P. Jesi, A. Montresor, et M. van Steen, « Secure peer sampling », Computer Networks, vol. 54, nᵒ 12, p. 2086‑2098, août 2010.

But we do not survive Byzantine nodes anyway (people can lie on their probability of being online): future works.

[dbosk]

Sounds good, thanks a lot!

On Sun 29 Apr 2018 06:19:20 GMT, Adrien Luxey wrote:

Well, that's the difference between reliability and security ;-) Boom, headshot! You got me here.

From Gossip-based Peer Sampling (studying "local randomness"):

The results of the randomness tests suggest that the stream of nodes returned by the peer-sampling service is close to uniform random for all the protocol in- stances examined. Given that some widely used pseudo-random number gen- erators fail at least some of these tests, this is a highly encouraging result regarding the quality of the randomness provided by this class of sampling protocols. Based on these experiments we cannot, however, conclude on global random- ness of the resulting graphs. Local randomness, evaluated from a peer’s point of view, is important, however, in a complex large-scale distributed system, where the stream of random nodes returned by the nodes might have compli- cated correlations, merely looking at local behavior does not reveal some key characteristics such as load balancing (existence of bottlenecks) and fault toler- ance. In Section 4 we present a detailed analysis of the global properties of our protocols.

The whole Global Randomness goes in-depth in in-degree distribution, average path length, clustering coefficient and such. Since they cover several algorithm variations, they get different results. But they show that after 20 cycles of initialization, some algorithms make the views change fast in addition to have them uniformly random.

You can cite This article, really. It's this ref: Jelasity_Voulgaris_Guerraoui_Kermarrec_van_Steen_2007.

There is also byzantine tolerant Peer sampling: [1]G. P. Jesi, A. Montresor, et M. van Steen, « Secure peer sampling », Computer Networks, vol. 54, nᵒ 12, p. 2086‑2098, août 2010.

But we do not survive Byzantine nodes anyway (people can lie on their probability of being online): future works.

-- You are receiving this because you authored the thread. Reply to this email directly or view it on GitHub: https://github.com/dbosk/p2p-private-cloud/issues/36#issuecomment-385251014

[dbosk]

Actually, the only thing their lying can cause is denial of service (saying p_d = 1 when it's p_d = 0) or unnecessarily large header (saying p_d \approx 0 when it's p_d \approx 1). Right?