A SCALABLE FRAMEWORK FOR WIRELESS DISTRIBUTED COMPUTING
ABSTRACT
We consider a wireless distributed computing system,in which multiple mobile users, connected wirelessly throughan access point, collaborate to perform a computation task.In particular, users communicate with each other via the accesspoint to exchange their locally computed intermediate computationresults, which is known as data shuffling.Weproposea scalable framework for this system, in which the requiredcommunication bandwidth for data shuffling does not increasewith the number of users in the network. The key idea is toutilize a particular repetitive pattern of placing the data set (thusa particular repetitive pattern of intermediate computations),in order to provide the coding opportunities at both the usersand the access point, which reduce the required uplink communicationbandwidth from users to the access point and thedownlink communication bandwidth from access point to usersby factors that grow linearly with the number of users. We alsodemonstrate that the proposed data set placement and codedshuffling schemes are optimal (i.e., achieve the minimum requiredshuffling load) for both a centralized setting and a decentralizedsetting, by developing tight information-theoretic lower bounds.
CONCLUSIONS AND FUTURE DIRECTIONS
In this paper, we proposed a scalable wireless distributedcomputing framework, for both the centralized and the decentralizedsettings, such that the shuffling load does not increasewith the number of participating users. In particular, we use arepetitive placement of the dataset across the users to enablecoding, reducing the shuffling load by a factor that scaleslinearly with the network size.In this paper, we have abstracted out several practical challengesto demonstrate the theoretical feasibility of a scalablewireless distributed computing framework and quantify theresulting gains. Future directions can be to generalize themodel to also incorporate the following important aspects.• Network Heterogeneity. Most mobile networks are het-erogeneous. Different mobile devices have different linkquality, processing power, battery capacity, and QoSrequirement. For example, the proposed coded computingschemes are for a set of mobile users with similaruplink/downlink channel strengths and communicationrates. When users have heterogeneous link capacities,one straightforward solution is to first partition the usersinto groups, such that all users within a group havesimilar channel strength, and then apply the proposedschemes within each group. However, designing theoptimal grouping strategy is a challenging problem thatrequires further exploration. Other than performing thecomputations at the users themselves, the superior computationand storage capacity of a growing number ofedge servers at access points encourage computationoffloading to the edge servers. Another interesting problemis to consider a mobile network of heterogeneoususers with the possibility of performing computations atthe edge servers, and study the optimal scheduling andcommunication schemes Computation Heterogeneity. In many wireless distributedcomputing applications (especially for graph processing),the intermediate computation results have heterogeneoussizes. For example, for a navigation application over ahighly clustered map, some parts of the map generatemuch more useful information than the other parts,resulting in highly skewed intermediate results. In suchscenario, the proposed coding scheme still applies, butthe coding operations are not symmetric as in the caseof homogeneous intermediate results (e.g., one may nowneed to compute the XOR of two data segments withdifferent sizes). Alternatively, we can consider a lowcomplexitygreedy approach, in which we perform thedataset placement to maximize the number of multicastingopportunities that simultaneously deliver usefulinformation to the largest possible number of users.Nevertheless, finding the optimal dataset placement andcoding scheme in the case of heterogeneous computationresults remains a challenging open problem.• Straggling/Failing Users. So far we have assumed thatfor both the centralized and the decentralized settings,once the collaborative computation process starts, allparticipating users are active and reliable until the endof the computation. However, similar to the stragglerproblems in wireline computer clusters,one needs to account for the possibilities of mobile userslosing connectivity, leaving, and joining the applicationin the middle of computation. One approach to deal withstraggling/failing users during the computation processis to assign users coded computation tasks using e.g.,Maximum-Distance-Separable codes (for an example of applying coded computations on matrix multiplication).Using this approach, the successful executionof the mobile application can be achieved by retrievingthe computation results from only a subset of “healthy”users, and this can provide the system with certain levelof robustness to straggling/failing users during the courseof computation.
EXISTING SYSTEM:
The idea of applying coding in shuffling the intermediateresults of MapReduce-like distributed computing frameworkswas recently proposed, for a wireline scenariowhere the computing nodes can directly communicate witheach other through a shared link. In this paper, we considera wireless distributed computing environment, in whichwireless computing nodes communicate via an access point.More specifically, we extend the coded distributed computingframework in in the following aspects.• We extend the wireline setting to a wirelesssetting, and develop the first scalable framework withconstant communication loads for wireless distributedcomputing.• During data shuffling, other than designing codes atthe users for uplink communication, we also designnovel optimum code at the access point for downlinkcommunication.• We consider a decentralized setting that is of vitalimportance for wireless distributed computing, whereeach user has to decide its local storage content independently.We develop optimal decentralized datasetplacement strategy and uplink-downlink communicationscheme to achieve the minimum communication loadsasymptotically.The idea of efficiently creating and exploiting coded multicastingopportunities was initially proposed in the context ofcache networks and extended where caches pre-fetch part of the content in a way toenable coding during the content delivery, minimizing thenetwork traffic. In this paper, we demonstrate that such codingopportunities can also be utilized to significantly reduce thecommunication load of wireless distributed computing applications.However, the proposed coded framework for wirelessdistributed computing differs significantly from the codedcaching problems, mainly in the follow aspects. a central server has the entire datasetand broadcasts coded messages to satisfy users’ demands.In this work, the access point neither stores any part ofthe dataset, nor performs any computation. We designednew codes at both the users and the access point for datashuffling.• The cache contents are placed without knowing the users’demands in the coded caching problems, while here thedataset placement is performed knowing that each userhas her own unique computation request (input).• Our scheme is faced with the challenge of symmetriccomputation enforced by the MapReduce-type structure,i.e., a Map function computes intermediate values for allinputs. Such symmetry is not enforced in coded cachingproblems.
PROPOSED SYSTEM:
Our main contribution is to provide an affirmative answerto this question by developing a framework for wirelessdistributed computing that utilizes redundant computations atthe users, in order to create coding opportunities that reducethe required communication, achieving a scalable design. Thedeveloped framework can be considered as an extension of ourpreviously proposed coded distributed computing frameworkfor a wireline setting,into the wireless distributedcomputing domain. To develop such a framework, we exploitthree opportunities in conjunction:1) Side-Information: When a sub-task has been processedin more than one node, the resulting intermediateoutcomes will be available in all those nodes asside-information. This provides some opportunities forcoding across the results and creates packets that areuseful for multiple nodes.2) Coding: We use coding to develop packets useful tomore than one mobile users. This allows us to exploitthe multicasting environment of the wireless mediumand save communication overhead.3) Multicasting: Wireless medium by nature is a multicastingenvironment. It means that when a signal istransmitted, it can be heard by all the nodes. We exploitthis phenomenon by creating and transmitting signalsthat help several user nodes simultaneously.computing domain. To develop such a framework, we exploitthree opportunities in conjunction:1) Side-Information: When a sub-task has been processedin more than one node, the resulting intermediateoutcomes will be available in all those nodes asside-information. This provides some opportunities forcoding across the results and creates packets that areuseful for multiple nodes.2) Coding: We use coding to develop packets useful tomore than one mobile users. This allows us to exploitthe multicasting environment of the wireless mediumand save communication overhead.3) Multicasting: Wireless medium by nature is a multicastingenvironment. It means that when a signal istransmitted, it can be heard by all the nodes. We exploitthis phenomenon by creating and transmitting signalsthat help several user nodes simultaneously.
REFERENCES
[1] S.Li,Q.Yu,M.A.Maddah-Ali,andA.S.Avestimehr,“Posterabstract:A scalable coded computing framework for edge-facilitated wirelessdistributed computing,” in Proc. IEEE/ACM Symp. Edge Comput. (SEC),Oct. 2016, pp. 79–80.
[2] S. Li, Q. Yu, M. A. Maddah-Ali, and A. S. Avestimehr, “Edge-facilitatedwireless distributed computing,” in Proc. IEEE GLOBECOM, Dec. 2016,pp. 1–7.
[3] F. Bonomi, R. Milito, J. Zhu, and S. Addepalli, “Fog computing and itsrole in the Internet of Things,” in Proc. 1st Ed. MCC Workshop MobileCloud Comput., 2012, pp. 13–16.
[4] U. Drolia et al., “The case for mobile edge-clouds,” in Proc. IEEE 10thInt. Conf. Ubiquitous Intell. Comput. (UIC), Dec. 2013, pp. 209–215.
[5] D. Datla et al., “Wireless distributed computing: A survey of researchchallenges,” IEEE Commun. Mag., vol. 50, no. 1, pp. 144–152,Jan. 2012.
[6] G. Huerta-Canepa and D. Lee, “A virtual cloud computing provider formobile devices,” in Proc. 1st ACM Workshop Mobile Cloud Comput.Services Soc. Netw. Beyond, 2010, Art. no. 1.
[7] M. Chowdhury, M. Zaharia, J. Ma, M. I. Jordan, and I. Stoica, “Managingdata transfers in computer clusters with orchestra,” ACM SIGCOMMComput. Commun. Rev., vol. 41, no. 4, pp. 98–109, Aug. 2011.
[8] S. Li, M. A. Maddah-Ali, and A. S. Avestimehr, “Coded MapReduce,”in Proc. 53rd Allerton Conf., Sep. 2015, pp. 964–971.
[9] S. Li, M. A. Maddah-Ali, and A. S. Avestimehr, “Fundamental tradeoffbetween computation and communication in distributed computing,” inProc. IEEE ISIT, Jul. 2016, pp. 1814–1818.
[10] S. Li, M. A. Maddah-Ali, Q. Yu, and A. S. Avestimehr. (Apr. 2016).“A fundamental tradeoff between computation and communicationin distributed computing.” [Online]. Available: https://arxiv.org/abs/1604.07086
[11] S. Li, S. Supittayapornpong, M. A. Maddah-Ali, and A. S. Avestimehr,“Coded terasort,” in Proc. 6th Int. Workshop Parallel Distrib. Comput.Large Scale Mach. Learn. Big Data Anal., to be published.
[12] J. Dean and S. Ghemawat, “MapReduce: Simplified data processing onlarge clusters,” in Proc. 6th USENIX (OSDI), Dec. 2004, p. 10.
[13] M. Zaharia, M. Chowdhury, M. J. Franklin, S. Shenker, and I. Stoica,“Spark: Cluster computing with working sets,” in Proc. 2nd USENIXHotCloud, Jun. 2010, p. 10.