×

Stability, efficiency, and contentedness of social storage networks. (English) Zbl 1434.91055

Summary: Social storagesystems are a good alternative to existing data backup systems of local, centralized, and P2P backup. Till date, researchers have mostly focussed on either building such systems by using existing underlying social networks (exogenously built) or on studying quality of service related issues. In this paper, we look at two untouched aspects of social storage systems. One aspect involves modelling social storage as an endogenous social network, where agents themselves decide with whom they want to build data backup relation, which is more intuitive than exogenous social networks. The second aspect involves studying the stability of social storage systems, which would help reduce maintenance costs and further, help build efficient as well as contented networks. We have a four fold contribution that covers the above two aspects. We, first, model the social storage system as a strategic network formation game. We define the utility of each agent in the network under two different frameworks, one where the cost to add and maintain links is considered in the utility function and the other where budget constraints are considered. In the context of social storage and social cloud computing, these utility functions are the first of its kind, and we use them to define and analyse the social storage network game. Second, we propose the concept of bilateral stability which refines the pairwise stability concept defined by M. O. Jackson and A. Wolinsky [J. Econ. Theory 71, No. 1, 44–74 (1996; Zbl 0871.90144)], by requiring mutual consent for both addition and deletion of links, as compared to mutual consent just for link addition. Mutual consent for link deletion is especially important in the social storage setting. The notion of bilateral stability subsumes the bilateral equilibrium definition of S. Goyal and F. Vega-Redondo [J. Econ. Theory 137, No. 1, 460–492 (2007; Zbl 1132.91321)]. Third, we prove necessary and the sufficient conditions for bilateral stability of social storage networks. For symmetric social storage networks, we prove that there exists a unique neighborhood size, independent of the number of agents (for all non-trivial cases), where no pair of agents has any incentive to increase or decrease their neighborhood size. We call this neighborhood size as the stability point. Fourth, given the number of agents and other parameters, we discuss which bilaterally stable networks would evolve and also discuss which of these stable networks are efficient – that is, stable networks with maximum sum of utilities of all agents. We also discuss ways to build contented networks, where each agent achieves the maximum possible utility.

MSC:

91D30 Social networks; opinion dynamics
91A43 Games involving graphs
68P20 Information storage and retrieval of data
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Aumann, R. J., & Myerson, R. B. (1988). Endogenous formation of links between players and of coalitions: an application of the Shapley value. In A. E. Roth (Ed.), The Shapley value (pp. 175-192). Cambridge University Press.
[2] Bala, V.; Goyal, S., A noncooperative model of network formation, Econometrica, 68, 5, 1181-1229 (2000) · Zbl 1022.91047 · doi:10.1111/1468-0262.00155
[3] Bala, V.; Goyal, S., A strategic analysis of network reliability, Review of Economic Design, 5, 3, 205-228 (2000) · doi:10.1007/s100580000019
[4] Batten, C., Barr, K., Saraf, A., & Trepetin, S. (2002). pStore: A secure peer-to-peer backup system. Technical Memo MIT-LCS-TM-632, Massachusetts Institute of Technology Laboratory for Computer Science.
[5] Belleflamme, P.; Bloch, F., Market sharing agreements and collusive networks, International Economic Review, 45, 2, 387-411 (2004) · doi:10.1111/j.1468-2354.2004.00130.x
[6] Billand, P.; Bravard, C.; Sarangi, S., Strict Nash networks and partner heterogeneity, International Journal of Game Theory, 40, 3, 515-525 (2011) · Zbl 1231.91040 · doi:10.1007/s00182-010-0252-8
[7] Blackburn, X. Z. J., Kourtellis, N., Skvoretz, J., & Iamnitchi, A. (2014). The power of indirect ties in friend-to-friend storage systems. In 14th IEEE international conference on peer-to-peer computing (P2P’14) (pp. 1-5). London, UK: IEEE.
[8] Bloch, F.; Dutta, B., Communication networks with endogenous link strength, Games and Economic Behavior, 66, 1, 39-56 (2009) · Zbl 1161.91477 · doi:10.1016/j.geb.2008.03.007
[9] Bloch, F.; Jackson, MO, The formation of networks with transfers among players, Journal of Economic Theory, 133, 1, 83-110 (2007) · Zbl 1280.91034 · doi:10.1016/j.jet.2005.10.003
[10] Borkotokey, S.; Gogoi, L.; Sarangi, S., A survey of player-based and link-based allocation rules for network games, Studies in Microeconomics, 2, 1, 5-26 (2014) · doi:10.1177/2321022214522744
[11] Bramoullé, Y.; Djebbari, H.; Fortin, B., Identification of peer effects through social networks, Journal of Econometrics, 150, 1, 41-55 (2009) · Zbl 1429.91254 · doi:10.1016/j.jeconom.2008.12.021
[12] Bramoullé, Y.; Kranton, R.; D’Amours, M., Strategic interaction and networks, American Economic Review, 104, 3, 898-930 (2014) · doi:10.1257/aer.104.3.898
[13] Bramoullé, Y.; López-Pintado, D.; Goyal, S.; Vega-Redondo, F., Network formation and anti-coordination games, International Journal of Game Theory, 33, 1, 1-19 (2004) · Zbl 1080.91015 · doi:10.1007/s001820400178
[14] Buchegger, S., & Datta, A. (2009). A case for P2P infrastructure for social networks-opportunities & challenges. In Sixth international conference on wireless on-demand network systems and services (WONS’09) (pp. 161-168). Snowbird, UT, USA: IEEE.
[15] Buchegger, S., Schiöberg, D., Vu, L. H., & Datta, A. (2009). PeerSoN: P2P social networking: Early experiences and insights. In Proceedings of the second ACM Eurosys workshop on social network systems (SNS’09) (pp. 46-52). Nuremberg, Germany: ACM.
[16] Buechel, B.; Hellmann, T., Under-connected and over-connected networks: The role of externalities in strategic network formation, Review of Economic Design, 16, 1, 71-87 (2012) · Zbl 1241.91025 · doi:10.1007/s10058-012-0114-x
[17] Calvó-Armengol, A., Job contact networks, Journal of Economic Theory, 115, 1, 191-206 (2004) · Zbl 1063.91055 · doi:10.1016/S0022-0531(03)00250-3
[18] Cox, LP; Murray, CD; Noble, BD, Pastiche: Making backup cheap and easy, SIGOPS-Operating Systems Review, 36, SI, 285-298 (2002) · doi:10.1145/844128.844155
[19] Cox, LP; Noble, BD, Samsara: Honor among thieves in peer-to-peer storage, SIGOPS-Operating Systems Review, 37, 5, 120-132 (2003) · doi:10.1145/1165389.945458
[20] Dai, S., Networks of Institutions: Institutional Emergence, Social Structure and National Systems of Policies (2015), Routledge: Taylor & Francis, Routledge
[21] Demaine, ED; Hajiaghayi, M.; Mahini, H.; Zadimoghaddam, M., The price of anarchy in network creation games, ACM Transactions on Algorithms, 8, 2, 13:1-13:13 (2012) · Zbl 1295.68041 · doi:10.1145/2151171.2151176
[22] Dutta, B.; Ghosal, S.; Ray, D., Farsighted network formation, Journal of Economic Theory, 122, 2, 143-1 (2005) · Zbl 1112.91013 · doi:10.1016/j.jet.2004.05.001
[23] Dutta, B.; Jackson, MO; Dutta, B.; Jackson, MO, On the formation of networks and groups, Networks and groups: Models of strategic formation, 1-15 (2003), Berlin: Springer, Berlin
[24] Dutta, B.; Mutuswami, S., Stable networks, Journal of Economic Theory, 76, 2, 322-344 (1997) · Zbl 0893.90043 · doi:10.1006/jeth.1997.2306
[25] Fabrikant, A., Luthra, A., Maneva, E., Papadimitriou, C. H., & Shenker, S. (2003). On a network creation game. In Proceedings of the twenty-second annual symposium on principles of distributed computing (PODC’03) (pp. 347-351). Boston, Massachusetts: ACM. · Zbl 1322.91013
[26] Falk, A.; Kosfeld, M., It’s all about connections: Evidence on network formation, Review of Network Economics (2012) · doi:10.1515/1446-9022.1402
[27] Flåm, SD; Horvath, C., Network games; adaptations to Nash-Cournot equilibrium, Annals of Operations Research, 64, 1, 179-195 (1996) · Zbl 0854.90152 · doi:10.1007/BF02187645
[28] Furusawa, T.; Konishi, H., Free trade networks, Journal of International Economics, 72, 2, 310-335 (2007) · doi:10.1016/j.jinteco.2006.08.003
[29] Gilles, RP; Sarangi, S., Network formation under mutual consent and costly communication, Mathematical Social Sciences, 60, 3, 181-185 (2010) · Zbl 1200.91265 · doi:10.1016/j.mathsocsci.2010.08.001
[30] Goeree, JK; Riedl, A.; Ule, A., In search of stars: Network formation among heterogeneous agents, Games and Economic Behavior, 67, 2, 445-466 (2009) · Zbl 1188.91052 · doi:10.1016/j.geb.2008.12.005
[31] Goyal, S.; Peitz, M.; Waldfogel, J., Social networks on the web, The Oxford handbook of the digital economy, 434-459 (2012), Oxford: Oxford University Press, Oxford
[32] Goyal, S.; Joshi, S., Networks of collaboration in oligopoly, Games and Economic Behavior, 43, 1, 57-85 (2003) · Zbl 1040.91043 · doi:10.1016/S0899-8256(02)00562-6
[33] Goyal, S.; Joshi, S., Bilateralism and free trade, International Economic Review, 47, 3, 749-778 (2006) · doi:10.1111/j.1468-2354.2006.00395.x
[34] Goyal, S.; Joshi, S., Unequal connections, International Journal of Game Theory, 34, 3, 319-349 (2006) · Zbl 1109.91016 · doi:10.1007/s00182-006-0023-8
[35] Goyal, S.; Moraga-González, JL, R&D networks, The RAND Journal of Economics, 32, 4, 686-707 (2001) · doi:10.2307/2696388
[36] Goyal, S.; Vega-Redondo, F., Structural holes in social networks, Journal of Economic Theory, 137, 1, 460-492 (2007) · Zbl 1132.91321 · doi:10.1016/j.jet.2007.01.006
[37] Gracia-Tinedo, R., Artigas, M. S., & Garcia-López, P. (2012a). Analysis of data availability in F2F storage systems: When correlations matter. In 12th IEEE international conference on peer-to-peer computing (P2P’12) (pp. 225-236). Tarragona, Spain: IEEE.
[38] Gracia-Tinedo, R., Sánchez-Artigas, M., & Garcia-López, P. (2012b). F2box: Cloudifying F2F storage systems with high availability correlation. In 5th IEEE international conference on cloud computing (CLOUD’12) (pp. 123-130). Honolulu, HI, USA: IEEE.
[39] Gracia-Tinedo, R., Sánchez-Artigas, M., Moreno-Martínez, A., & Garcia-López, P. (2012c). Friendbox: A hybrid F2F personal storage application. In 5th IEEE international conference on cloud computing (CLOUD’12) (pp. 131-138). Honolulu, HI, USA: IEEE.
[40] Hall, P., On representatives of subsets, Journal of the London Mathematical Society, 10, 1, 26-30 (1935) · JFM 61.0067.01 · doi:10.1112/jlms/s1-10.37.26
[41] Hummon, NP, Utility and dynamic social networks, Social Networks, 22, 3, 221-249 (2000) · doi:10.1016/S0378-8733(00)00024-1
[42] Jackson, MO; Demange, G.; Wooders, M., A survey of network formation models: Stability and efficiency, Group formation in economics, 11-57 (2005), Cambridge: Cambridge University Press, Cambridge
[43] Jackson, MO, Social and economic networks (2008), Princeton: Princeton University Press, Princeton · Zbl 1149.91051
[44] Jackson, MO; van den Nouweland, A., Strongly stable networks, Games and Economic Behavior, 51, 2, 420-444 (2005) · Zbl 1099.91011 · doi:10.1016/j.geb.2004.08.004
[45] Jackson, MO; Wolinsky, A., A strategic model of social and economic networks, Journal of Economic Theory, 71, 1, 44-74 (1996) · Zbl 0871.90144 · doi:10.1006/jeth.1996.0108
[46] Jain, H., Teja, G., Mane, P., Ahuja, K., & Krishnamurthy, N. (2018). Data backup network formation with heterogeneous agents. In 10th international conference on communication systems & NETworkS (COMSNETS’18). Bengaluru, India: IEEE. arXiv preprint arXiv:1711.10283.
[47] Kuznetsov, P.; Schmid, S.; Patt-Shamir, B.; Ekim, T., Towards network games with social preferences, 17th International colloquium on structural information and communication complexity (SIROCCO’10), 14-28 (2010), Heidelberg: Springer, Heidelberg · Zbl 1284.91077
[48] Landers, M., Zhang, H., & Tan, K. L. (2004). PeerStore: Better performance by relaxing in peer-to-peer backup. In Fourth international conference on peer-to-peer computing (P2P’04) (pp. 72-79). Zurich, Switzerland: IEEE.
[49] Li, J., & Dabek, F. (2006). F2F: Reliable storage in open networks. In the 5th international workshop on peer-to-peer systems (IPTPS’06), Santa Barbara, CA, USA (pp. 1-6).
[50] Lillibridge, M., Elnikety, S., Birrell, A., Burrows, M., & Isard, M. (2003). A cooperative internet backup scheme. In Proceedings of the annual conference on USENIX annual technical conference (pp. 29-41). San Antonio, Texas, USA: USENIX Association.
[51] Meyer, J., Representing risk preferences in expected utility based decision models, Annals of Operations Research, 176, 1, 179-190 (2010) · Zbl 1233.91083 · doi:10.1007/s10479-008-0381-7
[52] Moreno-Martínez, A., Gracia-Tinedo, R., Sánchez-Artigas, M., & Garcia-Lopez, P. (2012). Friendbox: A cloudified F2F storage application. In 12th IEEE international conference on peer-to-peer computing (P2P’12) (pp. 75-76). Tarragona, Spain: IEEE.
[53] Moscibroda, T., Schmid, S., & Wattenhofer, R. (2006). On the topologies formed by selfish peers. In Proceedings of the twenty-fifth annual ACM symposium on principles of distributed computing (PODC’06) (pp. 133-142). Denver, Colorado, USA: ACM. · Zbl 1314.68162
[54] Moscibroda, T.; Schmid, S.; Wattenhofer, R., Topological implications of selfish neighbor selection in unstructured peer-to-peer networks, Algorithmica, 61, 2, 419-446 (2011) · Zbl 1221.68038 · doi:10.1007/s00453-010-9398-9
[55] Myerson, RB, Graphs and cooperation in games, Mathematics of Operations Research, 2, 3, 225-229 (1977) · Zbl 0402.90106 · doi:10.1287/moor.2.3.225
[56] Nguyen, T. D., & Li, J. (2007). Blockparty: Cooperative offsite backup among friends. In 4th USENIX symposium on networked systems design & implementation (poster paper). Cambridge, MA: USENIX Association.
[57] Oliveira, M. I. S., Cirne, W., Brasileiro, F., & Guerrero, D. (2008). On the impact of the data redundancy strategy on the recoverability of friend-to-friend backup systems. In 26th Brazilian symposium on computer networks and distributed systems (SBRC’08), Rio de Janeiro, Brazil (pp. 1-14).
[58] Papadimitriou, C. (2001). Algorithms, games, and the internet. In Proceedings of the thirty-third annual ACM symposium on theory of computing (STOC’01) (pp. 749-753). Hersonissos, Greece: ACM. · Zbl 1323.68022
[59] Pratt, JW, Risk aversion in the small and in the large, Econometrica, 32, 1-2, 22-136 (1964) · Zbl 0132.13906
[60] Rzadca, K., Datta, A., & Buchegger, S. (2010). Replica placement in P2P storage: Complexity and game theoretic analyses. In 30th IEEE International Conference on Distributed Computing Systems (pp. 599-609). Genova, Italy: IEEE.
[61] Rzadca, K.; Datta, A.; Kreitz, G.; Buchegger, S., Game-theoretic mechanisms to increase data availability in decentralized storage systems, ACM Transactions on Autonomous and Adaptive Systems, 10, 3, 14:1-14:32 (2015) · doi:10.1145/2723771
[62] Sharma, R., Datta, A., DeH’Amico, M., & Michiardi, P. (2011). An empirical study of availability in friend-to-friend storage systems. In IEEE international conference on peer-to-peer computing (P2P’11) (pp. 348-351). Kyoto, Japan: IEEE.
[63] Skorin-Kapov, D., Social enterprise tree network games, Annals of Operations Research (2017) · Zbl 1417.91140 · doi:10.1007/s10479-017-2460-0
[64] Steinmetz, R.; Wehrle, K.; Steinmetz, R.; Wehrle, K., What is this “peer-to-peer” about?, Peer-to-peer systems and applications, 9-16 (2005), Berlin: Springer, Berlin
[65] Suijs, J.; Borm, P.; Hamers, H.; Quant, M.; Koster, M., Communication and cooperation in public network situations, Annals of Operations Research, 137, 1, 117-140 (2005) · Zbl 1138.91358 · doi:10.1007/s10479-005-2249-4
[66] Tennekes, M. (2010). Network formation games. PhD thesis, Maastricht University.
[67] Toka, L.; Michiardi, P., Analysis of user-driven peer selection in peer-to-peer backup and storage systems, Telecommunication Systems, 47, 1, 49-63 (2011) · doi:10.1007/s11235-010-9301-7
[68] Tran, D. N., Chiang, F., & Li, J. (2008). Friendstore: cooperative online backup using trusted nodes. In Proceedings of the 1st workshop on social network systems (SocialNets’08) (pp. 37-42). Glasgow, Scotland: ACM.
[69] Tran, N.; Chiang, F.; Li, J., Efficient cooperative backup with decentralized trust management, ACM Transactions on Storage, 8, 3, 8:1-8:25 (2012) · doi:10.1145/2339118.2339119
[70] Weatherspoon, H.; Kubiatowicz, JD; Druschel, P.; Kaashoek, F.; Rowstron, A., Erasure coding vs. replication: A quantitative comparison, Peer-to-peer systems, 328-337 (2002), Berlin: Springer, Berlin · Zbl 1014.68665
[71] Zirulia, L., Industry profit maximizing R and D networks, Economics Bulletin, 12, 1, 1-6 (2006)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.