The advances in computational techniques both from a software and hardware viewpoint lead to the development of projects whose complexity could be quite challenging, e.g., biomedical simulations. In order to deal with the increased demand of computational power many collaborative approaches have been proposed in order to apply proper partitioning strategy able to assign pieces of execution to a crowd of workers. In this paper, we address this problem in a peer to peer way. We leverage the idling computational resources of users connected to a network. More in detail, we designed a framework that allows users to share their CPU and memory in a secure and efficient way. The latter allows users help each others by asking the network computational resources when they face high computing demanding tasks. As we do not require to power additional resources for solving tasks (we better exploit unused resources already powered instead), we hypothesize a remarkable side effect at steady state: energy consumption reduction compared with traditional server farm or cloud based executions.
Computer Science is a really young discipline whose several branches grew up at
impressive rates. Hardware cost is continuously decreasing while its performances are
reaching unprecedented levels. Based on the availability of a plethora of powerful
(portable) computing devices, new computing tasks have been designed and new data
management paradigm emerged (e.g., the well known Big Data metaphore [
The word Crowdsourcing was first introduced by Howe [
Many attempts have been made to properly define the very nature of collaborative distributed systems, however the solution to this apparently trivial task is far from being easy. As a matter of fact, all the successful systems (e.g., Wikipedia3, Yahoo! Answers4, Amazon Mechanical Turk5) rely on some assumptions: They should be able to involve project contributors, each contributor should solve a specific task, it is mandatory to effectively evaluate single contributions, and they should properly react to possible misconduct. The above mentioned points calls for a good trade-off between openness of the system and quality of service when designing a collaborative environment.
A well known open source framework that is widely used (mainly) for scientific
purposes is BOINC (Berkeley Open Infrastructure for Network Computing)6. It allows
volunteers to contribute to a wide variety of projects. The computing contribution is
rewarded by credits for getting to a higher rank in a leaderboard. On the opposite side in
recent years a new category of collaborative approaches is born for cryptovalue mining
such as Bitcoin [
More in detail, the novelty of our project is the exploitation of a peer to peer approach for reusing resources that users do not fully exploit to provide services that are currently offered by centralized server farm at an high cost with no customization. In particular, current limitation to high performance computing access (high price and difficult customization of resources), could be overcome by using our framework. Users who may need computing power, can simply ask other users that are not fully exploiting the potential of their computing devices (PC, smartphone, smart TV, etc.).
In order to assess the effectiveness of our solution, we analyzed a typical usage pattern for the big market of imaging and animation: the rendering of 3D scenes by a specialized plugin named MozaikoT M 7. This operation typically engages users computers for several hours. Our experimental analyses evidence that existing solution are slower than our proposal due to their traditional approach to high performance computing and more expensive due to high prices of CPU cycles renting. Our plugin provides high added value to potential customers because it will be faster and cheaper than the competing solution (further details can be found at www.coremuniti.com).
Our solution do not require the continuous purchase of new servers, as users continuously provide (up to date) computational power. Finally, the better re-use of already powered resources could induce a beneficial systemic effect by reducing the overall
4 https://answers.yahoo.com/ 5 https://www.mturk.com 6 https://boinc.berkeley.edu/ 7 We choose this name as Mozaiko is the Esperanto (a universal language) term denoting a Mosaic that is a good metaphore for our approach that partition a complex task in several sub-tasks that will be re-assembled like mosaic tiles energy consumption for complex tasks execution. We plan to further investigate our conjecture in a future work as we are not able at this stage to generalize our early results.
Our Contribution. To summarize, we make the following major contributions: 1) We design and implement a hybrid P2P infrastructure that allows collaboration among users by sharing unexploited computational resources; 2) We define a robust model for task partitioning and assignment to network users; 2
P2P networks features a common goal: the resources of many users and computers can
be used in a collaborative way in order to significantly increase the computing power
available for the users. In “full” P2P networks computers communicate directly each
other thus allowing better bandwidth use. However, there are some inherent drawbacks
to P2P solutions that require some functionalities to be centralized. Those systems can
be used both for data sharing[
Users who want to join our network, will download our software that will install the Coremuniti server on their devices (it is worth noticing that our software is platform independent). By running the node server, denoted in Fig. 1 as N SA (Node Server Agent), users can easily set the amount of CPU time they are willing to share with other users in the network. As they allow task execution, they will be rewarded by credits. We point out, that our software is executed in parallel with user own activities without any interaction with them. On the opposite side, users who need additional computing power to complete specialized tasks (in this paper we present the 3D Rendering case study) can install the specific software that is denoted in Fig. 1 as N CA that stands for Node Client Agent (i.e., Mozaiko for the rendering case study). As they start a new computing intensive task, they simply issue a request to the network for gathering the required resources. Two cases may occur: 1) they have previously gained (a portion of) the required credits for running the task (e.g., because they acted as servers) or 2) they have bought the required credits. In order, to guarantee a high level of service, we perform the subtask assignment step at the central server. More in detail, to fully take advantage from the capability of our network, we partition the (possibly huge) task in a suitable number of (much smaller) subtasks that can be quickly executed by the server peers.
As subtasks are completed, we check their correctness and reward the participating peers. In the following, we describe our model for subtask assignment that guarantees efficient execution for clients and gave to all peers (even if they have limited computing power) the possibility to be rewarded. Interesting enough, users that are not going to ask for task execution have the chance to accumulate credits that can be redeemed by coins or gadgets. As it will be shown in the experimental section, the latter features makes our framework a more convenient choice w.r.t to other collaborative systems such as cryptovalue miners. Indeed, in the early stage of development of our system we performed some preliminary user analysis by asking 500 students at University of Calabria their interest in joining the network. After specifying our rewarding model all of them agreed to join the network and they are currently beta testing the software. Due to space limitation, we will not describe the architecture details and in hat follows we will describe the most interesting part of our system, i.e. subtask assignment. 3
In this section, we describe our mathematical model for assigning subtask execution to resource providers whose objective is to minimize the expected completion time for the overall task. More in detail, as explained above, when a user asks the network for additional resources, the project s/he is going to execute is partitioned in several subtasks that can be completed using a limited amount of computational resources by every node connected to our P2P network . The obtained results are then combined for producing the project output much as much fast as possible than single machine execution.
The model assumes the presence of a set of available resource providers RP = frp1; : : : ; rpng, and of a function c : RP ! N N , that assigns to every resource provider rp a pair htmin; tmaxi, where tmin (resp. tmax) is the minimum (resp. maximum) execution time required by the resource node to complete a subtask.
Furthermore, we leverage a credit assignment function which is based on the “usefulness” of the result yielded by the resource providers. Specifically, let st be a subtask whose execution was assigned c credits and which was assigned to the resource providers rpi1 ; : : : rpix . We order the resource providers rpi1 ; : : : rpix ascending w.r.t. their completion times and store them in a sequence RPst. Resource providers which did not terminate their subtask are put at the end of the sequence RPst ordered according to the percentage of the subtask they completed.
When at least three resource providers completed their work, we assign 130c of the total credits, paid by the client for running the subtask on the network, to the first three resource providers in RPst, i.e., the resource providers which “step up on the podium” for returning st result. Moreover, we distribute the remaining 1c0 credits among the other resource provider in RPst as follows. For each j 2 [4::x] we assign to RPst[j] the credits given by the following formula 10 c Compl(RPst[j]) Px k=4 Compl(RPst[k]) ; where Compl(rp) is the percentage of the subtask st which was completed by rp.
Tasks assignment aims at finding an assignment for resource provider to tasks which minimize the expected completion time while guaranteeing that:
2. every resource provider which is assigned a subtask have the possibility to be among the first three resource providers completing the subtask.
Subtask assignment proceeds in two phases. First an initial assignment of the various subtask to resource is yielded (Algorithm 1). Next, at regular intervals, the systems checks for the overall completion of the project and assigns resource providers that are available to new subtasks (Algorithm 2).
Let st be a subtask and RP = frp1; : : : ; rpkg be the set of resource providers
assigned to st. The expected completion time of st given RP is denoted as ECst;RP
and is computed as follows. Let t# and t" be two vectors reporting, respectively,
the minimum and maximum completion times of the resource providers in RP in
increasing order. Let t0 denote the value t#[
F 3(x))dx = t0 + Rtt000 (1
Fi3(x))dx = t0 + Pik=01 FtFii3(ti; ti+1);
F 3(x))dx = where Fi3(x) is the probability that at least three resource providers complete their work before x time limit given that ti x ti+1 and F Fi3(ti; ti+1) is equal to Rttii+1 (1 Fi3(x))dx. It is easy to see that F Fi3(ti; ti+1) can be easy derived form the minum and maximum completion times associated to every resource providers by the function c.
Example 1. Consider the case that a set of four resource providers RP = frp1; : : : ; rp4g was assigned to st where c(rp1) = h1; 5i; c(rp2) = h2; 7i; c(rp3) = h6; 7i and
ECst;RP = 4 + R45(1 F03(x))dx + R56(1 F13(x))dx + R67(1 F23(x))dx =
The initial subtask assignment is computed by running Algorithm 1. It works in two phases. First an initial assignment of resource providers to tasks is yielded by assigning a resource provider at a time to the subtask which minimize the maximum expected completion time of all the tasks, considering resource providers in ascending order of their expected completion time (lines 2-8). Next the initial assignment is revised by swapping pairs of resource providers between tasks. The algorithm iteratively selects a pair of assignments hst0; rp0i; hst00; rp00i which once swapped provide the greatest decrease of the maximum expected completion time (lines 9-12). Finally, the subtask assignment is returned.
Input: Resource provider sequence RP of size n Input: Subtask sequence ST of size k < n3 Output: Tasks assignment SA 1: SA = ; 2: RP = orderOnExpCompl(RP) 3: for i = 1 to n do 4: st = selectBestFreeST(ST ; SA; RP[i]) 5: if st 6= null then 6: SA = SA [ hst; RP[i]i 7: end if 8: end for 9: repeat 10: (hst0; rp0i; hst00; rp00i) = selectBestCandidatePair(SA) 11: SA = SA fhst0; rp0i; hst00; rp00ig [ fhst0; rp00i; hst00; rp0ig 12: until existsACandidatePair(SA) 13: return SA
Function orderOnExpCompl takes as input a sequence of resource providers RP and returns RP ordered ascending w.r.t. the expected resource provider completion time. Function selectBestFreeST returns, given a resource provider rp and a subtask assignemnt SA, the subtask st 2 ST such that M axECP (SA[fhst; rpig) is the minimum, i.e., st = arg minst2ST (M axECP (SA[fhst; rpig)), such that M axECP (SA[ fhst; rpig) < M axECP (SA), null otherwise. Since in the initial step of the algorithm it may happen that there is some subtask st in ST such that jSA(st)j = x < 3, for each subtask st satisfying this constraint, when computing M axECT function selectBestFreeST assumes that 3 x fake resource providers have been assigned to st, where the minimum and maximum completion times of these fake resource providers are max 1 and max, respectively, where max is a constant value (much) greater than the maximum completion time of every the resource provider in RP.
Function selectBestCandidatePair returns a pair of assignments hst; rpi and hst0; rp0i in SA such that there not exist assignment hst00; rp00i and hst ; rp i in SA such that MaxECP (SA fhst; rpi; hst0; rp0ig[fhst; rp0i; hst0; rpig) > MaxECP (SA fhst00; rp00i; hst ; rp ig[ fhst00; rp i; hst ; rp00ig). Function existsACandidatePair returns true if there is a pair of assignments hst; rpi and hst0; rp0i in SA such that MaxECP (SA fhst; rpi; hst0; rp0ig [ fhst; rp0i; hst0; rpig) < MaxECP (SA). Moreover, both functions selectBestCandidatePair and existsACandidatePair consider only pairs of assignments hst; rpi and hst0; rp0i in SA such that swapping rp and rp0 guarantees that the probability that rp (resp. rp0) is among the first three resource providers assigned to st0 (resp. st) that complete st is greater than zero.
Our central server runs Algorithm 2 at fixed intervals, in order to check for the overall completion of the project and assigns resource providers, that have completed the assigned tasks, to further tasks whose results are not yet available. Before running this algorithm the system updates the statistics of resource providers which are assigned to a subtask yielding up to date values for the minimum and maximum completion times. Essentially Algorithm 2 first orders the available resource providers ascending w.r.t. their expected completion times and next iteratively assigns each resource provider rp to the subtask st selected by invoking function selectBest. Function selectBest returns, given a resource provider rp and a subtask assignemnt SA, the subtask st 2 ST such that M axECP (SA [ hst; rpi) is the minimum, i.e., st = arg minst2ST (M axECP (SA[hst; rpi)), and is such that M axECP (SA[fhst; rpig) < M axECP (SA), null otherwise. 4
In this paper, we proposed a hybrid peer to peer architecture for computational resource sharing. By our network users can provide their unexploited computational resource to those users who run computational demanding tasks and they are rewarded for their collaboration. In order to guarantee the efficiency and effectiveness of the computation process, we design a task partitioning and assignment algorithm that reduce the execution times while allowing satisfactory revenues for resource providers.
The authors thank the Calabria region that fully funded the project development and the EU commission that awarded our project with a seal of excellence.
Algorithm 2 Incremental Assignment Input: Available resource providers sequence RP of size n Input: Subtask sequence ST Input: Initial Subtasks assignment SA Input: Subtasks and Resource Providers constraints ST C Output: Revised Subtasks assignment SA 1: RP = orderOnExpCompl(RP ) 2: for i = 1 to n do 3: st = selectBest(ST ; SA; RP [i]) 4: if st 6= null then 5: SA = SA [ hst; RP [i]i 6: end if 7: end for