Parallel architectures and algorithms




Peer-to-Peer (P2P) systems

Over the last six years, P2P applications has generated tremendous interest worldwide among both Internet surfers and computer networking professionals. Indeed, since May 1999, when Shawn Fanning launched Napster, the first P2P file-sharing application [NAPSTER], the phenomenon of file-sharing continues its sensational growth and seems to remain an important feature of the Internet for the immediate future. Several instances of P2P architecture exist and offer services from Grid Computing to Distributed and Redundant File Storage systems, from Instant Messaging system to Collaboration systems.

P2P Features

In Peer-to-Peer architectures the applications take advantage of resources, storage, cycles, content, human presence, available at the edges of the Internet allowing peers to leverage their collective power to the "benefit" of all.

Thus, when new peers join the system, not just the load is increased on the system, but also the total power of the system is proportionally expanded. In general, Scalability can be seen as the first characteristics that marks the diversity of P2P architecture from standard client-server. In fact, in the latter case, adding more clients represents solely additional workload for the server(s) and, consequently, less performances for all the clients. Peer-to-Peer systems, in fact, distribute the main costs of sharing data, disk space and bandwidth, across the peers in the network, thus enabling applications to scale without the need for powerful, expensive servers and, consequently, overshadow the capabilities of centralized systems with low costs.

The distributed nature of P2P networks also increases fault-tolerance by enhancing system robustness in case of failures, data can be naturally replicated over multiple peers and, if peers are enabled by a non-centralized technique to find the desired resources without relying on a centralized index server, no single point of failure into the system is present.

Despite a lot of P2P promoters arguing that P2P systems mark a departure from the traditional client-server paradigm, both the systems can and will coexist. In fact, P2P systems will not replace traditional steady and well-rooted services that are accessible via the World Wide Web, but cooperative services based on P2P architecture will play an increasing role within the Internet ecosystem.

Distributed Hash Tables

One of the most important benefits provided by P2P systems is the "Scalability". In a P2P systems, each consumer of the resources also donates resources. Nevertheless, "Scalability" has been recognized as the central challenge in designing such systems.

Unfortunately, the initial designs for P2P systems had significant scaling problems. Thus, the chaotic, ad hoc topologies of the first-generation Peer-to-Peer architectures have been replaced by a set of topologies with an emergent order, provable properties as well as excellent performance. Indeed, several research groups have — independently — proposed the second generation of P2P systems (DHT systems) that support a Distributed Hash Table (DHT) functionality [DR01,ZHSRKJ03,SMLKKDB03,RFHKS01].

Our Contribution

In this environment the main features of our contribution being:

  • [CGHNS04] The proposal of a family of novel Peer-to-Peer overlay networks, based on the Fibonacci number system, retaining all positive aspects that made Chord [SMLKKDB03] – which is one of the most popular DHT system proposed in the literature – a popular topology for routing in P2P networks. The schemes proposed simultaneously improve on the maximum/average number of hops for lookups and the routing table size per node.
  • [CGHS05] The proposal of routing schemes that optimize the average number of hops for lookup requests in Peer-to-Peer overlay networks. This work is inspired by the recently introduced variation of greedy routing, called neighbor-of-neighbor (NoN) [MNW04], which allows an optimal average path length with respect to the degree to be obtained. This strategy does not make use of randomization and as a consequence, the NoN technique can be implemented within these schemes without adding any overhead. Analyzed networks include several popular topologies: Chord, F-Chord(alpha), Hypercube based networks, Symphony, Skip-graphs. The improvement is obtained with no harm to the operational efficiency (e.g. stability, ease of programming, scalability, fault-tolerance) of the considered systems.
  • [CCGHNS08] The proposal of a family of Distributed Hash Table systems with the aim of combining routing efficiency of the randomized networks – average path length O(log n/loglog n) vs. the O(log n) average path length of the deterministic system – with the programmability and start-up efficiency of a uniform system – i.e., a system in which the overlay network is transitive and greedy routing optimal. The proposed family is parameterized with a positive integer c which measures the amount of randomness that is used. Varying the value c, the system goes from the deterministic case (c=1) to an ` "almost uniform" system. Increasing c to relatively low values allows routing with optimal average path length while retaining most of the advantages of a uniform system, such as easy programmability and quick bootstrap of the nodes entering the system. A matching lower bound for the average path length of the family of routing schemes for any c is also given.

Small World networks

Small World (SW) networks occupy a position which is intermediate between completely regular and random graphs. Such networksare characterized by the following main properties:

  • they tend to be large, in the sense that they contain n >> 1 nodes;
  • they tend to be sparse, in the sense that each node is connected to an average of delta << n other nodes;
  • they tend to have short paths (as random graphs);
  • they tend to be clustered (unlike sparse random graphs).

SW networks exhibits several interesting properties that cannot be totally captured by the traditional models: regular graphs, such as a Euclidean lattice, and random graphs (cfr. Erdös and Rényi random graphs).

Navigable graphs

A generic graph G is called navigable, if there exists a simple "greedy" algorithm that finds routes between any source and target using only a polylogarithmic (in the graph size) expected number of hops [M06,F05].

Notice that navigability is an interesting property for a graph. Such graphs, in fact, can be easily used in the development of efficient network infrastructures, such as for ad-hoc systems, where neither flooding nor complex routing protocols are to be used.

Our Contribution

[CG06] Our analysis starts from the Small–World model proposed by Kleinberg: a grid network augmented with directed long-range random inks. The choices of the long-range links are independent from one node to another. In this setting greedy routing and some of its variants have been analyzed and shown to produce paths of polylogarithmic expected length. We start from asking whether all the randomness used in the Kleinberg’s model, for establishing the long-range contacts of the nodes, is indeed necessary to assure the existence of short paths. We are able to decrease the number of random bits, required to establish each node’s long-range link, from Omega(log n) to O(log log n) on a network of size n. Diminishing the randomness in the choice of random links has several benefits; in particular, it implies an increase in the clustering of the graph, thus increasing the resilience of the network.

Internet Based Computing

The goal is to develop a theoretical foundation for the problem of scheduling large computational jobs that have complex inter-task dependencies on Internet-based computing platforms (such as grids and P2P settings). In all of the various modalities of Internet-based computing, the "owner" of a massive job enlists the assistance of remote "workers" in computing the constituent tasks of the job. The motivations of remote workers who participate in Internet-based computing projects range from curiosity (in, say, the famous SETI@home project) to altruism (in, say, the FightAids@home project) to remuneration (in various commercial computational grids) to the promise of reciprocation (in many so-called open computational grids).

What makes Internet-based computing platforms particularly challenging to use efficiently is that the temporal unpredictability that is intrinsic to such platforms precludes the "standard" strategies (such as critical path analysis) that were developed for scheduling complex computations on older platforms (such as multiprocessors and clusters). The temporal unpredictability has two main sources:* Communication takes place over the Internet, therefore may experience unpredictable delays. Remote workers, while usually committed to performing the work that is allocated to them, are seldom dedicated to this work, hence may perform it at an unpredictable rate.

The goal of the proposed new paradigm is so demanding – maximizing the number of eligible tasks at "every" step of the computation – that it is not surprising that many computations do not admit any optimal schedule. For these computations, every allocation strategy "short-changes" some parts of the computation. Somewhat surprisingly, though, large classes of scientific-type computations do admit optimal schedules under this new paradigm. Included here are broad classes of wavefront-oriented and convolutional computations that are studied, along with a variety of such "familiar" computations, in [R04,RY05].

Our Contribution

We extend the Internet Based Computing Theory in three ways:

  1. by expanding significantly the repertoire of dags that the Theory can schedule optimally, and by allowing one sometimes to shortcut the algorithmic process required to find optimal schedules. The expanded repertoire now allows the Theory to schedule optimally, among other dags, a large range of dags that are either "expansive", in the sense that they grow outward from their sources, or "reductive", in the sense that they grown inward toward their sinks. [CMR07]
  2. by an algorithmic shortcuts allow one to "read off" an optimal schedule for a dag from a given optimal schedule for the dag’s dual, which is obtained by reversing all arcs (thereby exchanging the roles of sources and sinks). [CMR07]
  3. by the Sweep Algorithm, a tool that allows one to: (1) schedule using building blocks that are not necessarily connected, and (2) craft schedules that interleave the execution of subdags that have no interdependencies. The augmented scheduling algorithms allow one to craft optimal schedules for previously unschedulable dags. Examples presented include artificial dags that are "close" to ones arising in real computations, as well as a component of a dag that arises in a functional MRI application. [CMR08]

References

  • [NAPSTER] Napster. [1].
  • [DR01] Peter Druschel and Antony Rowstron. "Pastry: Scalable, Decentralized Object Location, and Routing for Large-Scale Peer-to-Peer Systems". In Proceedings of the 18th IFIP/ACM International Conference on Distributed Systems Platforms (Middleware 2001). Heidelberg, Germany}, pages {329–350}. Springer-Verlag Berlin Heidelberg New York, November 2001.
  • [ZHSRKJ03] Ben Y. Zhao, Ling Huang, Jeremy Stribling, Sean C. Rhea, John D. Kubiatowicz, and Anthony D. Joseph. "Tapestry: A Global-scale Overlay for Rapid Service Deployment". In IEEE Journal on Selected Areas in Communications (J-SAC), Special Issue on Recent advances in Service Overlay Networks, Vol. 22, No. 1, pages 41–53, January 2004.
  • [SMLKKDB03] Ion Stoica, Robert Morris, David Liben-Nowell, David R. Karger, M. Frans Kaashoek, Frank Dabek, and Hari Balakrishnan. "Chord: A Scalable Peer-to-Peer Lookup Protocol for Internet Applications". In IEEE/ACM Transactions on Networking (TON), Volume 11, No. 1, pages 17–32, February 2003.
  • [RFHKS01] Sylvia~Paul Ratnasamy, Paul Francis, Mark Handley, Richard Karp, and Scott Shenker. "A scalable content-addressable network". In Proceedings of ACM Special Interest Group on Data Communication (ACM SIGCOMM ’01), San Diego, CA, US, pages 161–172, August 2001.
  • [CGHNS04] Gennaro Cordasco, Luisa Gargano, Mikael Hammar, Alberto Negro, and Vittorio Scarano. "F-Chord: Improved Uniform Routing on chord". In Proceedings of 11th Colloquium on Structural Information and Communication Complexity (Sirocco ’04), Smolenice Castle, Slovakia. Springer-Verlag Berlin Heidelberg New York, ISBN:3-540-22230-8, June 2004.
  • [MNW04] Gurmeet~Singh Manku, Moni Naor, and Udi Wieder. "Know thy Neighbor’s Neighbor: The Power of Lookahead in Randomized P2P Networks". In Proceedings of 36th thirty-sixth annual ACM Symposium on Theory of Computing (STOC ’04), Chicago, IL, USA, pages 54–63, June 2004.
  • [CGHS05] Gennaro Cordasco, Luisa Gargano, Mikael Hammar, and Vittorio Scarano. "Degree-Optimal Deterministic Routing for P2P Systems". In Proceedings of 10th IEEE Symposium on computers and communications (ISCC ’05) La Manga del Mar Menor, Cartagena, SPAIN, pages158–163. IEEE Computer Society, ISBN:0-7695-2373-0, June 2005.
  • [CCGHNS08] Giovanni Chiola, Gennaro Cordasco, Luisa Gargano, Mikael Hammar, Alberto Negro and Vittorio Scarano. "Degree-Optimal Routing for P2P Systems". In Theory of Computing Systems (TOCS),Vol. 45 No. 1, ISSN: 1432-4350, pages 43-63, June 2009.
  • [M06] Jon M. Kleinberg. "Complex Networks and Decentralized Search Algorithm". In International Congress of Mathematicians (ICM) , 2006.
  • [F05] P. Fraigniaud. "A New Perspective on the Small-World Phenomenon: Greedy Routing in Tree-Decomposed Graphs". In 13th Annual European Symposium on Algorithms (ESA), 2005.
  • [CG06] Gennaro Cordasco and Luisa Gargano. "How Much Independent Should Individual Contacts be to Form a Small-World?". In Proc. of The 17th International Symposium on Algorithms and Computation (ISAAC 2006), December 18-20, 2006 – Kolkata, India. (pdf)
  • [R04] A. L. Rosenberg. "On scheduling mesh-structured computations for Internet-based computing". IEEE Trans. Comput.53, 1176–1186.
  • [RY05] A. L. Rosenberg and M.Yurkewych. "Guidelines for scheduling some common computation-dags for Internet-based computing". IEEE Trans. Comput. 54, 428–438.
  • [CMR07] G. Cordasco, G. Malewicz and A. L. Rosenberg. "Advances in IC-Scheduling Theory: Scheduling Expansive and Reductive Dags and Scheduling Dags via Duality". In IEEE Transaction on Parallel and Distributed Systems (TPDS) Vol. 18, No. 11, ISSN: 1045-9219, November 2007.
  • [CMR08] G. Cordasco, G. Malewicz, and A. L. Rosenberg. "Extending IC-Scheduling via the Sweep Algorithm". In Proceedings of 16th Euromicro Conference on Parallel Distributed and network-based Processing (PDP 2008), February 13-15, 2008 – Toulouse, France.
  • [SCR08] M. Sims, G. Cordasco, and A. L. Rosenberg, "On Clustering Tasks in IC-Optimal Dags". In Proc. of International Conference on Parallel Processing (ICPP 2008). September 8&emdash;12, Portland, Oregon, USA.
  • [CR09] G. Cordasco, and A. L. Rosenberg, "On Scheduling Dags to Maximize Area". In Proc. of IEEE International Parallel & Distributed Processing Symposium (IPDPS 2009). May 2009, Rome, Italy.
  • [CG09] Gennaro Cordasco and Luisa Gargano. "Navigable Small&emdash;World Networks with Few Random Bits". In Theoretical Computer Science – Elsevier (TCS), Vol. 410 Issues 47-49, ISSN: 0304-3975, Pages 4975-4988, November 2009.