Guillaume Jourjon

Didier El Baz

Some Solutions for Peer-to-Peer Global Computing

the emergence of Internet and new kind of architecture, like peer-to-peer (P2P) networks, provides great hope for distributed computation. However, the combination of the world of systems and the world of networking cannot be done as a simple melting of the existing solutions of each side. For example, it is quite obvious that one cannot use synchronized algorithms for global computing over large area network. We propose here a non-exhaustive view of problems one could meet when he aims at building P2P architecture for global computing systems, which u s e asynchronous iterative algorithms. We also propose generic solutions for particular problems linked to both computing and networking sides. These problems involve the initialization of the computation (and its dual the conclusion), the task transparency over P2P network, and the routing in such n e t works. Finally a rst computational experiment is presented for an asynchronous auction algorithm applied to the solution of the shortest path problem.

Introduction

Distributed computing allows searchers to simulate their theory as well as it allows solution of large-scale problems. Many n umerical problems can generally be seen as xed-point problems. These problems can be sometimes solved thanks to iterative methods. Furthermore iterative methods can be divided into two di erent groups, synchronous and asynchronous. For thirty y ears computer scientists and mathematicians, see 2, 5 , 4 ] and 14], explore the way to study and im-plement these algorithms over distributed and parallel architectures, but with the emergence of networks for the past twenty y ears a new eld of experimentation is available. After the client/server architecture, new network architecture is born, the P2P network. This kind of networks di ers from the previous, and dominant, architecture by the fact that every computer in the network plays the same role. The rst use of this wide scale architecture was a le sharing system with the success of Napster, but we can notice that this application was just the rst generation of P2P networks, because it used a centralized architecture. Another success of rst generation P2P systems is the project of the Berkeley University, Seti@home These P2P rst generation applications still su er by their centralized architecture and lack of communication between peers, e.g. in Seti there is no communication between peers. The second generation of P2P networks provides a pure decentralized architecture with no central server, which connects peers. The rst and only available type of applications for this generation is le-sharing systems like F reenet or Gnutella 13]. The performances measured over such N e t works (65 Tera ops/sec for Seti) let presume a great capability for computing. Furthermore the improvement done in communication process (Cable. .. ) will allow a n implementation of global computing algorithms. The goal of our work is to set out an overview of the asynchronous iterative algorithms to solve great problems and to exhibit the main problems one can encounter for the implementation of such schemes over a P2P network and the way to solve several of these problems. Section 2 presents gen-eral asynchronous iterative algorithm. The next section presents the main problems such a project has to solve, and sections 4, 5 present solutions for the problems of routing and initial repartition respectively. Eventually the section 6 proposes a general design for such a system, and gives rst results obtained thanks to the implementation of our solution for the shortest path problem solved via an asynchronous auction algorithm.

Parallel Asynchronous Iterations

In this section, we give a brief presentation of parallel asynchronous iterative algorithms. We only present classical parallel asynchronous iterative s c hemes (see 2, 5 , 8, 14] ), but there is possible extension to more general schemes called exible asynchronous iterations (see 9, 1 2 ]). Parallel asynchronous iterative algorithms are generally used in order to compute an approximate solution to the following xed-point problem

x = F (x )
where x is a solution vector of R n and F is a given xed point mapping from R n to R n . L e t E = R n , the following partition of E is made: E = P Ei , for i = 1 t o p, where p is a given natural number which is relevant to the number of processors (peers). Accordingly, the iterate vector is partitioned as follows: x = x 1 : : : x p where each x i is called a blockcomponent. Each block-component x i is assigned to a given peer. The xed-point mapping is decomposed similarly: F = F 1 : : : F p . Asynchronous iterative algorithms generate successive approximations of the block-components of the iterate vector x. These approximations are obtained by applying in parallel and repetitively the block-components of the xed-point mapping F, to a given initial approximation x(0). A simple de nition of parallel asynchronous iterative a lgorithms can be given as follows.

De nition 2.1 a p arallel asynchronous iterative algorithm is a successive approximation method whereby several processors cooperate via data exchange to the solution of a given problem, and each processor performs computations, i.e. iterations, at his own pace by using the last available updates.

As a consequence, parallel asynchronous iterative a lgorithms are methods whereby iterations are carried out in parallel by s e v eral processors in arbitrary order and without any synchronization. The restrictions imposed on parallel asynchronous iterative a lgorithms are very weak: no component or blockcomponent of the iterate vector must be abandoned forever and more and more recent updates of the components have to be used as the computation progresses. The advantages of asynchronous iterative algorithms are computation exibility, tolerance to problem data changes (the algorithm adapts itself to a modi ed environment) and fault tolerance (the algorithm works out even if some data are lost). We present n o w a simple illustration of parallel asyn- We note that there is no idle time. We will not give more precisions about this kind of parallel algorithm, for further information we refer to 2, 5 , 9 , 8 , 1 0 , 1 2 , 1 4 ].

In the next section we will present speci c problems concerning the integration of asynchronous iterations over a P2P network.

Problems can be, in a rst time, seen as independent ones. We will enumerate a non-exhaustive list of problems one generally has to solve in P2P system, and in a global computing system. Each o f these problems can have di erent de nitions across literature, that's why w e h a ve to clearly establish de nition of the terms we will use all along the study. More speci c de nitions of the problems we treat can be found in the sequel. We will give a practical explanation and implementation of these properties. Let's rst de ne the network's properties.

The scalability of a P2P network is often described as the principal interest of such a n e t work. However, a unique de nition of it is rarely given. Indeed, the de nition of such a term depends on the scientist's approach o f h i s o wn system.

De nition 3.1 he scalability of a P2P network designed for global computing is its capacity to maintain its e ciencies when peers join or leave the system E ciencies of a system of global computing over P2P network are numerous. Its is the routing e ciency, the search e ectiveness, the algorithm's speed ... Each of these e ciencies can be represented and measured with the help of numerical parameters based on di erent times and costs. We will see in the next sections how this property impacts in the setting of the system. The second de nition, we h a ve t o x o u t , i s t h e task transparency of a P2P network. We rst have to separate the term of transparency and the one of anonymity, because in the literature these two concepts are often dangerously mixed up. Indeed, the concept of anonymity has to be linked with cryptology, which cannot be assimilated as a consequence of the network topology.

If we look at the le sharing P2P system we c a n de ne more precisely what should be transparency in our system. Indeed, in such applications the transparency is equivalent to a local or remote access to each block o f a l e .

De nition 3.2 the transparency can be de ned a s the property to make undistinguished l o cal or remote access to all parts of the task and data set needed f o r computation.

The de nition means that, whatever happens to the network, each peer still online can have access to the entire needed set of components for the computation. This can be translated by the fact that we n e e d t o envision duplication and a good distribution of this set of data and tasks. But if we compare to what is done in sharing le P2P system, the transparency just means that the system has to have an e cient search m e c hanism. (see 6]) Eventually, the last network's property, w e h a ve to de ne, is the robustness. The robustness, in a general overview, is the capacity o f a n y system to keep on stability when an error occurs. The errors in a P2P network are the failures of peers and links between them. These failures can occur for many reasons, one can be attacked, another can just leave the network, or one could have his rst IP router congested? If we w ant to model this with the help of graph theory, an error can be represented by the eviction of a node and all of its incoming and outgoing edge on the representative board, or just the eviction of an edge.

De nition 3.3 the robustness of a P2P network is its capacity to stabilize itself despite the failure o f some of its components (peers and links).

This last de nition is not only a network's de nition, but it is also a computational one. In the following section we will describe two kinds of routing, which are needed in a P2P Global Computing.

Routing in a P2P network

In order to solve the di erent problems we h a ve j u s t presented, we need to set on, in a P2P Global Computing system, two kinds of routing. These two kinds of routing di er one from another in their goal and use. Indeed, the rst routing that we will describe later aims at informing peers about the system's topology. That's why w e name it the initial routing. The second routing aims at allowing e cient searches. It is linked to the transparency problem because as we h a ve already said the transparency can be set on thanks to an e cient search s c heme. This particular routing is the basic routing of a P2P system, as described in 6, 7]. Because of the di erence in the way they are used, one routing is a search routing and the other is a nding host routing, these routings may, in a rst time, be separate in order to keep on clear. But we can easily imagine that someone using any mathematical formula could combine these two kinds of routing in order to keep only one. But we are not sure that it is very useful.

Initial routing

The routing for the initial repartition of the algorithm aims at serving at the global e ciency of the algorithm. In this way w e can think about an algorithm that de nes a metric, which should be calculated thanks to peers' capacity, e ciency, a n d a vailability. These pieces of information could be calculated as an average of all the operation a computer can do per second, for example. Thus, such algorithms are quite complicated and for the moment w e just want to set on a simple routing algorithm mapped on the IP routing experimentations. That's why, in a rst time, we recommend the use of basic algorithm. We can choose a Hop-count algorithm like RIP (see RFC n um 2132) and we h a ve translated it for P2P network. As a result, each p e e r owns a routing table, which c o n tains a list of known peers, the next peer to send data in order to reach another peer, and the number of peers data has to go through before eventually reaching the wanted peer (hop count). We will illustrate in section ve h o w one can use this routing thanks to some algorithms.

Transparency routing

In this subsection, we will discuss about another routing, which di ers from the previous one by its use and information it o ers to peers. This routing aims at allowing peers to proceed e cient searches over the network. It doesn't certainly aim to replace the initial routing it has to be seen as a complementary routing. One of the main di erences between this routing and the previous one is that this routing could, in the case there is no computation on the network, be useless.

The literature proposes several type of routing, which di er one from another following these hypothesis: First, we h a ve to notice that the search in our system is a key words routing (hypothesis 2). Indeed, when a peer would want to search for a part of the data set and tasks needed for the computation, it has to know the name of the problem the set depends on.

The fact that we can use name of problems is a quite important a d v antage for the search mechanism, because it allows more e cient s e a r c h as compared to ooding search s c hemes of P2P systems like G n utella. In order to establish such a kind of routing, we c a n use several solutions. We will use, for example, a transposition of one of them proposed by H. Garcia-Molina, which is called Routing Indices (RI) 7]. The di erence between our solution and Garcia-Molina's one is that our solution locates part of the task and data set instead of the entire document. Routing table for transparency will be established by using the same messages as the initial routing, or by using new messages that we h a ve to add to the system's protocol. In each problem's column, the number, in front of peers' identi er, represents the metric associated to the number of part of the task and data set you could reach i f y ou send a query to the appropriated neighbor. This metric could be dened in many w ays, for further information we refer to 7]. The search routing we h a ve just presented is just an example of this kind of needed routing. We can also set on, for example, a routing that would take advantage of the generally encountered topology. P2P network's topology follows, like I n ternet and many other networks, power-law 1 , 1 1 ] . That's why w e could establish a routing that aims at nding network's super-nodes. Indeed, super-nodes are peers, which o wn more neighbors than other peers. As its possess many neighbors, a super-node also possesses more information for a search. However we think that in a rst time search routing has to be quite simple. Because we rst have to simulate and establish simple routing in order to guarantee that global computing is possible over a P2P network. Once we will have demonstrated that it is possible, then we w ould think about a more e cient routing which w ould need more computational time and cost. We h a ve established two routing, which are the base of a P2P Global Computing system. Now w e will propose solutions for two main problems of a P2P global computing system.

Initialization and updating

In this section we propose simple solution for initialmisation and transfert of the solution.

Initialization

In this subsection, we present a mechanism, we c a l l initialization, that aims at allowing the system so that it owns several properties that would be useful for the computational algorithm. Indeed, if one would want to solve a large-scale problem thanks to an asynchronous iterative algorithm, he has to envision the termination's detection. Thanks to the different s c hemes we propose here, and the scheme proposes in 8], we could easily assure the termination's detection. We h a ve to notice that this partition will be achieved thanks to a unique message that we will call itSetup. This message will di er relatively on the algorithm of partition. For example if one uses the decideAll algorithm, the itSetup message will carry the identi cation of the root, the identi cation of the destination, the identi cation of the next peers the message would be forwarded to, the initial vector X0, and a piece of information (task and data set) that is assigned to the destination peer. In order to study the initialization we suppose that in a rst time the network is static. We h a ve found three simple methods to do this initial partition :

The peer, which initializes the computation or root, splits the xed-point problem into n parts, where n is the number of peers it could reach thanks to is routing table. Then, it sends these parts to peers by name. We call this method the decideAll method.

The root splits the xed-point problem into d parts, where d is its number of neighbors. These d parts could be di erent in size, according to the number of peers reachable by e a c h neighbor. Then, it sends these parts on, and at the neighbor level the algorithm restarts (this method is called di usion). We will see in the sequel a third method that we c a l l the evaluateAndSend one. We rst discuss about the advantages of the two previous methods. The main advantage of the rst method lays in the fact that root, namely the peer that gets all the information, decides of the partition. On the other hand since the network is dynamic, it is possible that the network topology changes, hence it is possible that some peers are no longer reachable by the anticipated path. The di usion method owns the advantage of repartition closer to the network topology. But we c a n also notice that this point m a y b e a d r a wback i f t h e topology possesses cycles. The third method we propose in this study is called evaluateAndSend, and should be squared as follow. The root splits the xed-point problem into m parts, where m is the result of an algorithmic evaluation of the number of peers. This algorithm could be sophisticated as those proposed in 3], or simple as the one used in the decideAll method. After this evaluation, the root splits the problem into m parts then, it sends these parts to its neighbors, each neighbor keeps the received part and processes it if the peer is idle, or keeps the received part and forwards it to one of its neighbor (di erent from the neighbor which sends it previously) otherwise.

We propose now three pseudo-codes for these three algorithms. We can notice that each method we h a ve proposed forwards the message itSetup by using the topology of the network. This is an important feature of the initialization, since thanks to this feature we can build 1 diffusion : 2 input and output unchanged 3 Int d = numberOfNeighbors 4 //evaluation of the neighbors 5 map mapNeighbors = evalNeighbor(d) 6 //this map should contains a key 7 for each neighbor and as value a 8 real number between 0 and 1 9 F d] = SplitPb( mapNeighbors, F) 10 11 for each neighbor i 12 send( i, F i]) 13 // each neighbor repeats this 14 algorithm at the reception of the 15 message itSetup Table 3: algorithm di usion a tree, which i s v ery important for the termination of the asynchronous algorithm. Indeed, we could use in order to detect the termination of the computation the principle presented in 10]. We s h o w n o w h o w one peer can perform update of an iterative algorithm.

Updating

In this subsection, we study updating processes for asynchronous iterative algorithms over P2P network. De nition of asynchronous iterative algorithms compels updating processes to follow rules that could be translated by the fact that moreover the computation goes on, the values of iterate vector's components used in the updating processes have t o b e m o r e a n d m o r e r e c e n t and any iterate vector's component has to be regularly updated. In order to insure these properties, we propose two solutions. Each solution uses a message, which w e will call itNew (iteration end), that will be used to communicate the update of the vector. The rst solution we propose here consists in the propagation of this message to the entire network. We could easily imagine that this solution will have a problem, which is the communication cost. Indeed 4: algorithm evaluateAndSend if the vector owns a great number of components the message itNew could be quite big. Even so we c a n notice that cycles in the propagation of this message could be avoided with a simple test, which c o u l d b e summarized to a backup of the message on each peer. This solution su ers from the fact that broadcasting is often useless, since in the resolution of large scale problems dependencies between vector's components are not global, especially in distributed systems. The second solution consists in a shorter propagation of this message, but in order to insure that each block of the iterate vector is still in updating, we propose that in the initiation phase each p e e r i s a ssigned to regularly control the ongoing updates of a components' block of the iterate vector. We propose to accomplish it the following schemes: Every t seconds each peer veri es that the components' block i t i s i n c harge has been updated since the last veri cation If this block has been updated the peer proceeds in its duty, otherwise it sends a query to the system in order to know if the peer that updates this block is still in computation.

If the searched peer is still on the network, it become a neighbor of the peer, which sends the query, otherwise the rst peer will search f o r t h e data set and task needed for the computation of this block and it will replace the missed peer.

This solution owns two a d v antages. The rst one is its lower communication cost. And the second is its improvement of the robustness of the system. Indeed with this solution we guarantee the detection of the non-updating of a block of component, and in response to this detection we could set on several counter measures, as an automatic search of the associated task and data in order to compute it in another peer.

Design of a rst solution

After seeing all these solutions we propose in this section a rst global architecture for a P2P Global Computing system. We will enumerate a list of needed messages and their role in such a system. The messages we speak about in this solution are as well messages like i n t h e G n utella protocol 13] o r remote method if we use the middleware technology.

General Design

First of all, in P2P networks we h a ve to maintain the topology. I n t h i s g o a l , w e h a ve t o e n vision a pair of messages that aims to verify that the neighborhood of each peer still belongs to the network. We c a l l these two messages ping and pong. The ping message is a kind of question that other peer will answer by sending a pong message. Ping message doesn't contain anything, but pong message could contain routing information if the routing table of the questioned peer has changed since the last ping received message. We can illustrate this scheme as follow. The The second class of messages we will specify is about the algorithm ongoing. We h a ve already spoken about two messages needed for asynchronous iterative algorithms, itSetup and itNew. The message itSetup always owns in its payload the origin vector that peers will update, and part of xedpoint mapping that allows peers to update a block o f component o f t h e v ector. This needed payload could be easily carried out thanks to the XML format, especially for the vector. This payload could, as we h a ve already spoken about, contain more information, like the destination of the message, the source .. . The message itNew owns in its payload the iterate vector or a part of it, depending on the problem and on the updating scheme we could set on. This message will also possess a eld called TTL, for Time To Live. This eld will be used to specify the number of peers the message could go through before its erasing of the network. This message is broadcasted to all neighbors the peer owns. The last and not least class of messages needed for the system concerns search o ver the network. To proceed search o ver a P2P network we need at least three messages, one for sending the request (query), one for the answer (queryHit), and one for the demand of download (push). The query message's payload will be composed of two elds. One of these elds will concern the search criteria, and the other eld will concern the nature of the request. This nature is devised into two categories, the block's one, and the data set and task of a component block. Indeed, as we h a ve already spoken about the search mechanism could be used in order to nd a part of the data set and task, and to improve robustness by setting on an automatic search for a peer, which is supposed to update a blockcomponent, when another peer detects a long nonupdating of this block-component. Furthermore, we have to x out a quantitative criterion for the search for a part of data set and task, for example n peers to go through or m results or both. The queryHit message, like query, will be composed of two elds. One for answer, and one for the nature of the request this message is answering to. The last message is composed of the destination of the message, the source, and the name of the wanted data set or task. These three messages are carried over the network from peer to peers. But when the destination peer receives a push message, it will send the request by using a direct connection and a protocol that could go through rewall, for example HTTP. W e can schematize this scheme as follow: As we h a ve already spoken Figure 4: Search Mechanism about at the beginning of this section, we can build such a system thanks to two kinds of technology, t h e software's one or the middleware's one.We can notice that in the case of an implementation based upon the software technology we could use a tools box like JXTA project.

Numerical experiments

In this section we h a ve presented possible implementations of a P2P global computing system, based on the software or middleware technology. W e h a ve built a middleware architecture following the above c o ncepts, which leads us to design a system based on the model of gure 4, and we present here rst results obtained for an asynchronous auction algorithm applied to the solution of shortest path problem in a network 4]. This algorithm nds all the shortest path from any n o d e i n t h e n e t work to a particular one. The communication of the iterate vector (the price of each node) happens every n iterations (we h a ve picked up n 4000). We used for this implementation CORBA and the Java language. The system we used has been built thanks to the LAN (100Mbps) architecture of our laboratory. W e used several heterogeneous (OS, Processor?) computers in a non-dedicated mode. We tested the above algorithm, for nding shortest path in a network, for several topologies created by BRITE. We studied four particular topologies. All of these topologies follow p o wer-law relationship (model BA in BRITE). These networks were built incrementally, and have g o t a h e a vy tail node placement. The constraints, of all the links created in the network, correspond to the delay of the associated links. Table 5 displays the solution time in second for problems with di erent n umbers of nodes, N, numbers of edges, A, and numbers of peers. We n o t e t h a t the performance of asynchronous auction algorithm is good. The lost of e ciency when the number of peer increases, can be explained thanks to three facts. The rst one is the utilization of CORBA and Java, which is a factor of slowdown. The second factor of slowdown is the architecture, which is not convenient for this particular algorithm because the time of computation is very small as compare to the communication time (we need almost 20000 iterations per peer and the ratio time of communication over time of computation is nearby 3 ). And the last factor, for this lack of performance, is the heterogeneous nature of peers and the non-dedicated use of computers.

Conclusion

We h a ve p r e s e n ted in this work possible solution to build P2P Global Computing systems. Especially, w e show that asynchronous iterative algorithm could be implemented over such a network, thanks to a set of messages. On the other hand synchronous iterative algorithms might be di cultly implemented, because it is supposed that a rendezvous point is established, in order to set a barrier of synchronization.

Concerning the initial repartition of the data set and task, we s h o w that the e ciency of the three algorithms, we h a ve proposed, depends on the network's topology. That's why an e cient c o n trol of this topology, via for example ping/pong mechanism, is critical to improve the global e ciency.

The rst architecture we propose in this document proves that it is possible to build such an architecture easily, in a future work we plan to study an other implementation, which m a y be more e cient (C++, Nombre de Peers N=1000, A=2000 N=1000, A=4000 N=2000, A=4000 N=2000, A=8000

Figure 1 :

 1 Figure 1: Asynchronous iteration

Figure 2 :

 2 Figure 2: Associated network

11 F

 11 peer i], i from 0 to n-2{ 10 send(peer i], appropriatedNeighbor,

  ] = SplitPb (n) 9 for each peer i], i from 0 to n-2{ 10 send(appropriatedNeighbor, F i],) 11 } Table

Figure 3 :

 3 Figure 3: Maintaining topology via ping/ping ping message could, in certain case, be used for state of Peers noti cation (active, inactive, terminated) as

Figure 5 :

 5 Figure 5: A rst architecture. Squares represent CORBA objects with an IDL interfaces and circles represent non-CORBA objects. Arrows represent the calling of the remote methods the orientation of these arrows means for example that the sender calls the itSetup method of the receiver.

Table 1 :

 1 The previous table represents the routing table for Routing table of a peer D

	PJ722 KZ84D XW583d Peer A 20 50 20 Peer B 30 40 10 PeerC 10 30 60

Table 2 :

 2 algorithm decideAll

Table 5 :

 5 First results of the asynchronous shortest path auction algorithm over a P2P Global Computing System. omniORB for example).

	1 5 10 15 20	7.53 5.7 2.45 2.3 2.0	6.39 4.2 2.2 2.02 1.7	14.5 9.5 4.9 4.7 4.6	17.2 11.5 6.1 6.0 5.8