Mohamed Bourimi

Thomas Barth

Joerg M Haake

Bernd Ueberschär

Dogan Kesdogan

AFFINE for Enforcing Earlier Consideration of NFRs and Human Factors When Building Socio-Technical Systems Following Agile Methodologies

des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Nowadays, a shift is taking place from single-user-centered usage to support multiuser needs and hence covering many collaboration measures and social aspects. The needed technical support for these users' activities in many important areas of our professional and leisure life activities is provided through collaborative applications also known as groupware as well as social software. According to Shneiderman and Plaisant "an extrapolation of current trends leads to the suggestion that most computer-based tasks will become collaborative because just as most work environments have social aspects" [START_REF] Shneiderman | Designing the User Interface: Strategies for Effective Human-Computer Interaction[END_REF]. Thus, software systems and applications supporting collaboration are considered as socio-technical systems in the Computer-Supported Cooperative Work (CSCW) as well as Human-Computer Interaction (HCI) research fields [START_REF] Gross | Computer-Supported Cooperative Workspace[END_REF]. Because socio-technical systems are characterized by complex scenarios which are mostly reflected e.g. in the user interface, HCI and CSCW also focus nowadays on human aspects of the development of computer technology in collaborative settings. While the goals of interaction are mostly covered by functional requirements (FRs), users' preferences (e.g. usability) and concerns (such as privacy and security) are related to non-functional requirements (NFRs). According to [START_REF] Chung | Dealing with non-functional requirements: three experimental studies of a process-oriented approach[END_REF], FRs define what the system does and therefore its functionality whereas NFRs define how a system has to be. Many CSCW and HCI key literature studied NFRs such as usability in socio-technical and the trade-offs, which could arise between them, e.g. privacy and awareness trade-offs in those systems. However, various literature state that current approaches do not adequately consider generally NFRs from the beginning in the development processes such stated in [START_REF] Chung | Dealing with non-functional requirements: three experimental studies of a process-oriented approach[END_REF]. Thus, recently many development approaches especially in the area of socio-technical systems follow usercentered and participatory design in combination with agile methodologies in order to efficiently react on end-users' emerging needs and (change) requirements [START_REF] Jokela | Assessment of user-centred design processes -lessons learnt and conclusions[END_REF][START_REF] Schümmer | Empowering end-users: A pattern-centered groupware development process[END_REF][START_REF]End User Development[END_REF]. In our opinion, even when a given NFR is considered from the beginning (i.e. usability in user-centered or participatory design), it is mostly contemplated separately from other NFRs and factors. When considering that socio-technical systems mostly represent a special category of distributed systems that are known to be difficult to design and maintain, tensions could arise between project stakeholders (i.e. end-users and developers) especially in agile settings. Furthermore, current approaches often not explicitly address the gap of mapping NFRs into the underlying system architecture. In this paper, we present the AFFINE (Agile Framework For Integrating Nonfunctional requirements Engineering) simultaneously addressing these needs. We first present identified needs in Section 2. Next, we describe our approach consisting of the AFFINE framework in Section 3 and our conclusions in Section 4. In order to reduce the potential complexity of these processes and assure the delivery as well as the quality of the products, many models (e.g. the well-known waterfall, prototyping, and spiral model) tried to structure the software development processes and define their behavior e.g. by introducing roles and defining software development life cycles. Latter include common phases like the requirements analysis, design, development, testing, and support phases. In contrast to the classical defined process models, agile process models and methodologies intend a better reaction on unexpected problems often by consideration of human factors. They are empirical processes that cannot be consistently repeated and therefore require constant monitoring and adaptation [START_REF] Highsmith | Agile software development ecosystems[END_REF]. However, Balzert states in [START_REF] Balzert | Lehrbuch der Softwaretechnik[END_REF] that according to a coarse classification of the activities independently of a given development processes, one could generally differentiate between two main phases, namely, the solution specification phase and the solution construction phase. While most of the activities of the specification phase can be classified as requirements engineering activities, the activities of the construction phase target mapping a given solution specification to a concrete technical solution. Different software engineering practices recognized the critical importance of NFRs for the specification and construction of software systems in general. A classical work addressing NFRs is [START_REF] Chung | Dealing with non-functional requirements: three experimental studies of a process-oriented approach[END_REF] state that software engineering practices concentrate on FRs, rather than NFRs. Furthermore, the authors cite that NFRs are generally stated informally during the requirements analysis, are often contradictory, difficult to enforce, and to validate during software development process. Based on further literature, they state that not taking NFRs properly into account is acknowledged to be the most expensive and difficult to correct once the software has been implemented and thus, there is a need to deal comprehensively with such requirements during the system development process. The concrete needs we address in this paper were identified based on one of the longrunning project CURE (Collaborative Universal Remote Education) we were able to follow. This project has a very representative character since its needs correspond to identified needs in other literature. The CURE platform was developed at the FernUniversität in Hagen ( F u H ) t o s u p p o r t d i f f e r e n t c o l l a b o r a t i v e l e a r n i n g a n d collaborative work scenarios [START_REF] Haake | Supporting flexible collaborative distance learning in the cure platform[END_REF]. The development process followed in CURE is an agile process called the Oregon Software Development Process (OSDP) described in [START_REF] Schümmer | The oregon software development process[END_REF]. Applying OSDP considered end-users' feedback of the participating departments at the FuH. Representatives of students and instructors from various disciplines such as mathematics, electrical engineering, computer sciences and psychology were participating in the usage and evaluation of the prototypes resulting from each OSDP-iteration. Even though OSDP considers conceptually NFRs in form of a NFR backlog, their consideration was not earlier enough to overcome drawbacks in the construction phase. In the case of CURE, responding to end-users wishes related to NFRs (e.g. usability of the web interface, performance of the synchronous communication means and awareness provision in the shared workspaces) was interrupted in order to meet the delivery, integration deadlines and budget. CURE was extended in various sub-projects (e.g. [START_REF] Bourimi | Collaborative design and tailoring of Web based learning environments in CURE[END_REF][START_REF] Bourimi | Leveraging visual tailoring and synchronous awareness in Web-based collaborative systems[END_REF][START_REF] Bourimi | Tailoring collaboration according privacy needs in real-identity collaborative systems[END_REF]). Most of these works were primarily concerned with improving NFRs which were classified as insufficiently covered by the developed system or tried to address new needs emerged through the usage of the system. Ambler states in [START_REF] Ambler | Beyond functional requirements on agile projects[END_REF] that NFRs and constrains are difficult to consider in projects following agile methodologies. A conceptual consideration of NFRs in the followed methodology avoids delegating their fulfillment to the intuition of involved people that could result in intentional or accidental negligence. Thus, we identify the need

Problem and Requirements Analysis

of conceptually enforcing the consideration of all relevant NFRs and possible trade-offs early in the development process (N1).

Involving end-users in an agile process could be very expensive. Especially when an agile methodology is followed in the end-users as well as developers are often experiencing continuous c o mmu n i c a t i o n t e n s i o n s. Developers are often asked to change, e.g., user interfaces or functionality, which seemed to be agreed upon earlier. Furthermore, on the one hand end-users and developers have different terminology for the same things or the same terminology for different things. On the other hand, members of the same development team might have different backgrounds and terminologies. This is also crucial in the case that different partners and/or distributed teams are cooperating in the same project. Communication problems are well known in the software engineering field and do not concern only agile methods. The same methodology may not be imposed to different stakeholder in the project, since involved parties may already have elaborated methodologies and processes as well as have different interests and goals (i.e. using their own software pieces or products etc.). Indeed, recent studies show that the most frequent failure source are communication problems with more than 70% [START_REF] Huth | Marktstudie probleme und fehler im requirements-engineering[END_REF] and that 33% of the projects are negatively affected or cancelled because of changing the requirements [START_REF] Emam | A replicated survey of it software project failures[END_REF]. Based on our experiences we argue that this is especially expensive when following an agile development process. Even though agility assure the close involvement of end-users, latter are mostly not experienced in communicating requirements to the developers [START_REF] Balzert | Lehrbuch der Softwaretechnik[END_REF]. Thus we identify the second need of explicitly balancing end-users' with developers' needs when following agile development method(ologie)s (N2). The design and evaluation of socio-technical systems is still a challenge because of the exploratory nature of these applications [START_REF] Shneiderman | Designing the User Interface: Strategies for Effective Human-Computer Interaction[END_REF]. Indeed, people involvement varies and the usage can range from occasional to frequent according to a given setting and circumstances. The same socio-technical system can lead to different evaluation results in different social environments [START_REF] Gross | Computer-Supported Cooperative Workspace[END_REF]. The evaluation of socio-technical systems needs methodologies and approaches t h a t a l l o w s f o r r a p i d a n d c o s t -effective development and usage of prototypes. Shneiderman and Plaisant mention that "while software engineering methodologies are effective in facilitating the software development process, they have not always provided processes for studying the users, understanding their needs, and creating a usable interface" [START_REF] Shneiderman | Designing the User Interface: Strategies for Effective Human-Computer Interaction[END_REF]. Depending on the project specific situation, development costs need often to be reduced. Software should not be built from scratch each time in the development process. In [START_REF] Grudin | Groupware and social dynamics: eight challenges for developers[END_REF], Grudin addresses challenges for groupware developers and suggests that adding new functionality to an accepted application is more adequate than developing a new application. This is a typical case when building many socio-technical systems or while their evolution. At a first glance, adding new functionality and enhanced interaction possibilities to existing systems seems attractive. However, adding new functionality often requires adding and modifying a lot of source code. This often complicates the API and requires a redesign of the domain model. Furthermore, Paech et al. argues in their position paper [START_REF] Paech | Functional requirements, nonfunctional requirements, and architecture should not be separated[END_REF] that FRs and NFRs as well as architecture should not be separated. The emerging changes are especially crucial when considering costs in terms of (re-)design, implementation and retrofitting costs. Thus, added functionality to socio-technical systems is reflected in growing complexity of their classes and/or components. Thus, the extension or retrofitting and the integration of new components in these systems represent realistic scenarios, which have to be considered in terms of development costs. However, it is important that by freezing changes, the design of the system stays extendable for future extensions and retrofitting. Thus, we formulate the third need as follows: The development method must be supported at the architectural and construction level to assure meeting N1 and N2 at minimal cost. A Kind of reference architecture providing support for NFRs is needed (N3). While N1 is more concerned with the specification phase of a given socio-technical system and N3 with its construction phase, N2 still overlapping both phases when following an agile methodology. Simultaneous consideration of N1-N3 is therefore required.

Our Approach: AFFINE

Introducing an agile method at the level of the development process is the key to satisfy N1 and N2 at the organizational level in our opinion. In order to reduce the complexity of the involvement of our method in various phases of the followed development process in a given project, we propose as an integral component Scrum [28]. Scrum can be seen as a process for empirical control of software development, which helps in handling changing requirements more efficiently by considering human factors in the development process of both; customers (in our case end-users) and project stakeholders in general. Based on our experiences in various projects, the main strengthens of Scrum consists of (1) the simplicity in terms of roles defined (Scrum master, product owner, and development team), development steps to be followed (e.g. development periods called sprints), documentation to be produced (e.g. sprint backlog), and meetings to be held (e.g. daily Scrum), ( 2) balancing the needs of the customers and developers through consensus enforcement for a given deliverable and continuous communication (e.g. in the daily Scrum meetings), ( 3) creating awareness on ongoing project tasks (also in daily Scrum e.g.), and ( 4) allowing for better as well as faster handling of detected, non-expected problems during the development process, which generally results (by right application) in better acceptance of the delivered product with low costs. Since the facilitator moderates the interaction, we represent such loop as an arrow starting and ending in the facilitator role. In Scrum, a sprint backlog document might be updated in such loop. Numerating this loop in our representation does not imply that the interaction is carried out in a giving sequence inside it. The left side of the same Figure shows our extension of a typical Scrum process to enforce the earlier consideration of NFRs. There, we introduce the role of a NFR stakeholder (mostly experts), who is concerned with the fulfillment and consideration of a respective NFR. The same facilitator has to moderate the circulation of the common document to the first stakeholder (according to prior prioritization), who has to update the document (e.g. adding warnings, requirements or changing them etc.). The structure of the common document and its content have to be defined from the project involved parties. However, circulating only one document, which contains all needed information for the development of given product, should avoid potential inconsistencies and information lost. After updating the document (at least by annotating that it was reviewed and maybe admitted without changes from the respective stakeholder), the document returns to the facilitator(s) and loops again over the left side. By admission without changes, the facilitator might shorten this iteration and directly forward the document to the next stakeholder. If any change happens in late circulations at the level of a stakeholder, the document returns to the facilitator, has to be circulated in the right side, and finally has to begin the circulation at the first stakeholder at the left side. We suggest the following informal steps for N1 and N2: 1. Involvement of all stakeholders of the project and introducing the role of the facilitator (one or more according to the project setting). 2. Goals or use cases (UC) identification of the intended processes (by defining the set of FRs). The facilitator has e.g. to guarantee the same terminology is used and has to detect miss-satisfaction signs in the different phases. 3. Alignment of all NFRs that have to be considered prioritizing them according to the project goals or UCs. 4. Responsible and experts for each goal or UC as well as NFR have to be chosen. 5. Circulating a single document (to avoid syncing various documents) containing the set of goals or UCs and their specification and modeling (by considering aligned FRs and NFRs at the same time). For this, UML or similar notations could be helpful in order to estimate efforts. The circulation has to be performed by the facilitator according to the priority of the NFRs. If a breakdown is identified in the circulation loop, the document has to be send back to the responsible of the first affected NFR (ordinarily with higher priority). If many NFRs are simultaneously affected, a meeting of the responsible and experts has to be organized. When conflicts arise, the facilitator intervenes in order to reach consensus. Since the facilitator is normally only a supporting role, his main goal consists in delivering the result while preserving satisfaction of end-users and project stakeholders. However, the final decision has to be made by the responsible(s) or at least by the coordination entity of the project. 6. The circulation ends when reaching the goals i.e. by implementing the UCs and testing them (also through the end-users). Those steps have to be executed for each project iteration. If the project is organized according big work packages, following a divide and conquer methodology could be helpful. In order to optimize the requirements gathering, user-centered design and modeling steps (for instance by using established methods like prototyping) and UML or ER diagrams (as mentioned before) could be useful. Finally, we want to mention, that the facilitator does not represents a critical point in this procedure. Any person familiarized with development activities should be able to act within this process as a facilitator. Further, if Scrum is integrated as an agile method, the Scrum certification exam ensures needed qualification of a facilitator. Related to N3, SOA is currently assessed as the next step forward in the design, development, operation, and organization of large-scale distributed systems (see e.g. [22]). Characteristics like loose coupling, discovery of artifacts during design/run time, and the ability to reuse services to enable efficient adaptation of a system to changing requirements (e.g. changes in users behavior, processes) are not supposed to be provided by an architectural approach for the first time. Learning from preceding approaches, characteristics like the commitment to open standards and the separation of architectural concepts from their technical implementation led to a widespread acceptance of service-oriented principles in commercial as w e l l a s s c i e n t i f i c communities. Since in our context NFRs are in the focus of attention, the inherent possibility of tailoring an SOA at design time according to the actual needs by carefully selecting the specifications to implement is an adequate means to realize these requirements [22]. Beyond this, NFRs like usability and performance in sociotechnical systems can only be assessed during runtime and in close cooperation with the end-user. As already discussed in this paper, an early consideration of NFRs during the lifecycle of an SOA leads to reduced development cost. Integrating different stakeholders into the development of an SOA is one approach to handle this; a Service Life Cycle Model focusing on SOAs stakeholders as a prerequisite for governing an SOA throughout its lifecycle is presented in [23]. Since NFRs are crosscutting concerns, the positive synergy between aspect-oriented programming (AOP) techniques and SOA for satisfying NFRs implementation was beneficial in our case. The architecture of the CURE-based sub-projects described in the related publications supports different kind of clients (i.e. Eclipse RPC thick client for the collaborative design editor [START_REF] Bourimi | Collaborative design and tailoring of Web based learning environments in CURE[END_REF], normal and AJAX browser clients for the retrofitted CURE [START_REF] Bourimi | Leveraging visual tailoring and synchronous awareness in Web-based collaborative systems[END_REF], and mobile as well as ubiquitous clients for the ubiquitous CURE [START_REF] Bourimi | Tailoring collaboration according privacy needs in real-identity collaborative systems[END_REF]) with the same SOA/AOP layer. Thereby, different kinds of architecture families also are supported (based the on client-server model, replicating or P2P). Surely, this is due because the context of these sub-projects could be satisfied with such single layer. Nevertheless, if different contexts have to be supported, various instances of the SOA/AOP layer could be deployed. So we mean that our AOP/SOA-based generic architecture meets N3 with a high genericity.

Conclusion

In this paper, we proposed the AFFINE framework that aims at simultaneously addressing three needs when developing socio-technical systems by following agile methodologies. The three needs were identified from the long-running project CURE as well as based on relevant HCI and CSCW literature gathered experiences. The main idea of AFFINE is to use an agile method including Scrum as an integral part. The agile method is user-centered and considers human factors, which could affect the success and acceptance of the developed socio-technical systems. The method enforces conceptually the earlier consideration of NFRs while the suggested supporting architecture provides a generic reference architecture for developing sociotechnical systems in agile development settings. Furthermore, AFFINE is independent from a specific software development process and applicable for different phases of the followed process in a given project. The concrete suggestion to use SOA and AOP at the technological level showed their advantages in first evaluations. The proposed framework is now successfully being applied in the ongoing work of many projects led by us as first empirical evaluations show. Future work aims at collecting more experiences and refining AFFINE.

  Software d e v e l o p m e n t p r o c e s s e s c a n b e s e e n a s c o m p l e x c o l l a b o r a t i v e s o c i a l processes.

Figure 3 . 1 :

 31 Figure 3.1: The Scrum based AFFINE method. The right side of Figure 3.1 r e p r e s e n t s b r o a d l y a t y p i c a l S c r u m d e v e l o p m e n t procedure. A facilitator (in our case the Scrum master) as well as the product owner and development team interact with each other in order to drive the product development. This interaction is represented as loop involving them all together.Since the facilitator moderates the interaction, we represent such loop as an arrow starting and ending in the facilitator role. In Scrum, a sprint backlog document might be updated in such loop. Numerating this loop in our representation does not imply that the interaction is carried out in a giving sequence inside it. The left side of the same Figure shows our extension of a typical Scrum process to enforce the earlier consideration of NFRs. There, we introduce the role of a NFR stakeholder (mostly experts), who is concerned with the fulfillment and consideration of a respective


Nicolas Kourtellis

Joshua Finnis
email: jfinnis@cse.usf.edu

Paul Anderson
email: paanders@cse.usf.edu

Jeremy Blackburn

Cristian Borcea
email: borcea@cs.njit.edu

Adriana Iamnitchi

Prometheus: User-Controlled P2P Social Data Management for Socially-Aware Applications

Keywords: social data management, P2P networks, socially-aware applications

Recent Internet applications, such as online social networks and user-generated content sharing, produce an unprecedented amount of social information, which is further augmented by location or collocation data collected from mobile phones. Unfortunately, this wealth of social information is fragmented across many different proprietary applications. Combined, it could provide a more accurate representation of the social world, and it could enable a whole new set of socially-aware applications. We introduce Prometheus, a peer-to-peer service that collects and manages social information from multiple sources and implements a set of social inference functions while enforcing user-defined access control policies. Prometheus is socially-aware: it allows users to select peers that manage their social information based on social trust and exploits naturallyformed social groups for improved performance. We tested our Prometheus prototype on PlanetLab and built a mobile social application to test the performance of its social inference functions under real-time constraints. We showed that the social-based mapping of users onto peers improves the service response time and high service availability is achieved with low overhead.

Introduction

Recently, we have witnessed the emergence of a wealth of socially-aware applications, which utilize users' social information to provide features such as filtering restaurant recommendations based on reviews by friends (e.g., Yelp), recommending email recipients or filtering spam based on previous email activity [START_REF] Kong | Collaborative spam filtering using e-mail networks[END_REF], and exploiting social incentives for computer resource sharing [START_REF] Tran | Friendstore: cooperative online backup using trusted nodes[END_REF]. Social information is also leveraged in conjunction with location/collocation data to provide novel mobile applications such as Loopt, Brightkite, Foursquare and Google's Latitude.

These applications need to collect, store, and use sensitive social information (including location and collocation). The state of the art is to collect and manage such information within the context of an application (as in the examples above) or to expose this information from platforms that specifically collect it, such as online social networks (OSN). For example, Facebook allows third-party application developers and websites to access the social information of its roughly 500 million users. Similarly, OpenSocial provides a common API for third-party applications to access social information stored on any of the supported social networks.

However, relying on social information exposed by OSNs has two major problems. First, the hidden incentives for users to have as many "friends" as possible lead to declarations of contacts with little connection in terms of trust, common interests, shared objectives, or other such manifestations of (real) social relationships [START_REF] Golder | Rhythms of social interaction: Messaging within a massive online network[END_REF]. Thus, an application that tries to provide targeted functionalities must wade through a lot of noise. Second, the business plans of the companies behind the social networks often conflict with the need to respect user privacy. Additionally, some social networks institute particularly draconian policies concerning the ownership of user-contributed information and content. For example, users cannot easily delete their OSN profiles, as in the case of Facebook which owns their data; they cannot export their social data to a service of their choice; and their social information has restricted use. This paper presents Prometheus, a peer-to-peer service for user-controlled social data management that enables innovative socially-aware applications. Prometheus collects social information from multiple sources (e.g., OSNs, email, mobile phones) by quantifying the actual social interactions between users. Thus, it maintains richer and more nuanced social information, which can lead to more accurate inferences of trust, interests, and context. Prometheus implements and exposes to applications several social inference functions.

The choice of a peer-to-peer (P2P) architecture was motivated by two factors: user privacy and service availability. We considered two alternative architectures. In a centralized architecture (as in current OSNs) there are no incentives or appropriate business models to store social data for free and allow users to control the privacy of their data. Prometheus leverages the P2P infrastructure of Mobius [START_REF] Borcea | P2P systems meet mobile computing: A communityoriented software infrastructure for mobile social applications[END_REF] to provide user-controlled social data management and social inferences for services and applications. An alternative architecture stores social information on users' mobile devices, as proposed in [START_REF] Mokhtar | A middleware service for pervasive social networking[END_REF][START_REF] Pietiläinen | MobiClique: Middleware for mobile social networking[END_REF][START_REF] Sarigol | A tuple space for social networking on mobile phones[END_REF][START_REF] Toninelli | Middleware support for mobile social ecosystems[END_REF]. Even though much of the social information is nowadays generated by mobile devices, they are inherently unsuitable for running a complex social service such as Prometheus due to resource constraints: the mobile devices may not be always online or synchronized to provide fast and efficient inference support, and energy and computation power may be scarce.

Prometheus gives users the ultimate control over where their private information is stored in the system, and which applications and users are allowed to access it. We ensure data security and access control on the peers using built-in public-key cryptography primitives and user-defined access control policies.

We prototyped and evaluated Prometheus on a large-scale deployment on PlanetLab and tested its performance with realistic workloads. The results show that the response time for social inferences decreases when user information is mapped onto peers using a social-aware approach. Furthermore, high service availability is achieved with low overhead. To test the Prometheus service under real-time deadlines, we implemented CallCensor, a mobile social application that uses Prometheus to decide whether to filter out incoming calls based on the current social context. The response time for this application running on a Google Android phone meets the real-time deadlines, proving that the Prometheus service overhead is reasonable.

An overview of the Prometheus service is presented in Section 2, and related work is covered in Section 3. Section 4 presents a detailed design of Prometheus, and Section 5 describes the experimental evaluation. We conclude in Section 6.

Prometheus Overview

Prometheus is a peer-to-peer service that enables socially-aware applications by collecting information from multiple sources and exposing it through an interface that implements non-trivial social inferences. This is accomplished via decentralized storage and management of a weighted, labeled, directed multi-edge social graph on user-contributed nodes. The access to social data is controlled by user defined policies.

Specifically, users register with Prometheus and allow it to collect social information about them from multiple sources that we refer to as social sensors. Social sensors are applications running on behalf of a user which report to Prometheus information such as interactions with other users via email, phone, instant messaging, comments on blogs, ratings on user-generated content, or even face-to-face interactions determined from collocation data. Social sensors can therefore be deployed on the user's devices (e.g., mobile phone) or on the Web (e.g., as a Facebook application reporting wall writing interactions).

The information collected by social sensors is processed by Prometheus to create a decentralized, weighted, directed, and labeled multi-edged graph, where vertices correspond to users and edges correspond to interactions between users as reported by social sensors. The interactions are described with a label (e.g., "work", "hiking") and a weight that specifies the intensity of the interaction. Prometheus uses this decentralized graph to answer various social queries from applications. Both the social information from sensors and the social subgraphs are stored and maintained in a P2P network formed by user PCs. The information from sensors is stored in an encrypted form and can be decrypted only by "trusted" peers, which are selected by users. The subgraph of each user is stored on her trusted peers. The trusted peers also enforce user-defined access control policies for each social query.

Figure 1 presents the Prometheus architecture. Prometheus runs on top of Pastry [START_REF] Rowstron | Pastry: Scalable, decentralized object location, and routing for large-scale peer-to-peer systems[END_REF], a distributed hash table (DHT)-based overlay, and uses Past [START_REF] Rowstron | Storage management and caching in PAST, a largescale, persistent peer-to-peer storage utility[END_REF] for replicated storage of sensor data. Each user has a group of trusted peers responsible for maintaining replicas of her social subgraph for high service availability. Only trusted peers can decrypt the user's social data. The maintenance of the trusted peer group is done by leveraging Scribe [START_REF] Castro | Scribe: A large-scale and decentralized application-level multicast infrastructure[END_REF], an application-level DHT multicast infrastructure.

Prometheus exposes an interface that enables applications to have access to a rich set of social inference requests computed over the distributed social graph. For example, an application can request on its user's behalf to receive the top relations (a function of a specified label and weight) of its user. Similarly, it can request the social strength between its user and another user not directly connected in the social graph. Prometheus provides the mechanism by which inference requests can access not only a single user's social graph (i.e., directly connected users), but also the social information of users located several hops away in the global social graph.

All inferences are subject to users' access control policies. These policies allow users to have fine-grained control over the access of all or parts of their graph by other users. For example, these policies can specify access control as a function of social labels. Prometheus uses a public-key infrastructure (PKI) to ensure both message confidentiality and user authentication. Each user and group has its own pair of public/private keys. For access control purposes, users are identified by their public keys. Social sensors use the appropriate keys to encrypt the data submitted to Prometheus.

Prometheus not only enables novel socially-aware applications but also specifically takes advantage of social-based incentives. Social awareness is embedded in the design of Prometheus in two ways. First, Prometheus allows users to select trusted peers to maintain their social subgraph based on out-of-band relationships. Socially-incentivized users keep their computers online, thus reducing churn [START_REF] Li | F2F: reliable storage in open networks[END_REF] and consequently increasing service availability for their friends' social inference requests. Second, given the characteristics of social graphs, sociallyrelated users will likely select the same trusted peers to store their social sub-graphs (i.e., friends have common friends who contribute peers in the system and thus select the same trusted peers). This allows complex social inferences over several social graph hops to be fulfilled locally, without traversing multiple network hops to access all the needed social information.

Related Work

Socially-aware applications and services have so far addressed ways to leverage out-of-band social relationships for diverse objectives such as improving security [START_REF] Yu | Sybilguard: defending against sybil attacks via social networks[END_REF], inferring trust [START_REF] Maniatis | The LOCKSS peer-to-peer digital preservation system[END_REF], providing incentives for resource sharing [START_REF] Tran | Friendstore: cooperative online backup using trusted nodes[END_REF], or building overlays [START_REF] Popescu | Safe and private data sharing with Turtle: Friends team-up and beat the system[END_REF] for private communication. Leveraging online social information has been used to rank Internet search results relative to the interests of a user's neighborhood in the social network [START_REF] Gummadi | Exploiting social networks for internet search[END_REF], to favor socially-connected users in a BitTorrent swarm [START_REF] Pouwelse | Tribler: A social-based peer-topeer system[END_REF], and to reduce unwanted communication [START_REF] Mislove | Ostra: leveraging trust to thwart unwanted communication[END_REF].

In all of these cases, social knowledge has been mined in the context of a single application and from a single source of information. Our work differs from these systems in four important ways. First, we collect information from multiple sources. The only system we are aware of that considers social information aggregation for enriching information value is Sonar [START_REF] Guy | Harvesting with SONAR: the value of aggregating social network information[END_REF]. Unlike our approach, Sonar is limited to improving information flow in an organization by aggregating social network information within the enterprise context, from sources such as email, instant messaging, etc. Second, we extract social knowledge from the social graph by accessing larger portions of the network, not only a user's direct neighborhood. Somewhat similarly, RE [START_REF] Garriss | Re: reliable email[END_REF] uses two hop relationships to automatically populate email whitelists. Third, in Prometheus, social information can cross application boundary contexts, similar to Ramachandran and Feamster's proposal to "export" the social ties formed in social networks for authentication in off-social applications [START_REF] Ramachandran | Authenticated out-of-band communication over social links[END_REF]. And finally, our social graph representation offers richer information for fine-grained evaluation of social ties. Kahanda and Neville also represent interactions with a weighted, directed multiedged graph [START_REF] Kahanda | Using transactional information to predict link strength in online social networks[END_REF]. Prometheus differs in its generality of the graph-its edges can represent interactions collected from different sources.

APIs for accessing social information has been offered by Facebook through its Open Graph API [START_REF]Graph api -facebook developers[END_REF] for access to simple, unprocessed social data. This API does not provide direct "friends of friends" inferences as Prometheus does, but instead an application must explicitly crawl the graph.

Privacy in Online Social Networks (OSNs) through decentralization has been addressed in [START_REF] Cutillo | Privacy preserving social networking through decentralization[END_REF]. Prometheus similarly forwards messages based on social relations while restricting a large scale view of the graph through a P2P mechanism. Prometheus differs dramatically, however, in the exposure of the graph as a first class data object through inference functionality. Persona [START_REF] Baden | Persona: An online social network with user-defined privacy[END_REF] uses an attributebased encryption (ABE) to provide privacy in OSNs. Prometheus can leverage this system to provide more flexible access control policies.

Peer-to-peer management of social data is also proposed in PeerSoN [START_REF] Buchegger | PeerSoN: P2P social networking: early experiences and insights[END_REF] and Vis-à-Vis [START_REF] Shakimov | Privacy, cost, and availability tradeoffs in decentralized OSNs[END_REF]. PeerSoN uses direct data exchange between users' devices.

Prometheus differs from this approach by using trusted peers, which are independent from the users' devices, to store and exchange social data. Vis-à-Vis introduces the concept of a Virtual Individual Server (VIS) where each user's data are stored on a personal virtual machine. While similar to the trusted peer concept in Prometheus, VISs are hosted by a cloud computing provider to counter peer churn, while Prometheus uses social incentives to reduce churn on user-supplied peers.

Our work significantly differs from the previously noted approaches in that it not only collects and stores user social information from multiple sources in a P2P network but also exposes social inference functions useful for novel sociallyaware applications. This approach shares ideas with the MobiSoc middleware [START_REF] Gupta | MobiSoC: a middleware for mobile social computing applications[END_REF]; however, the MobiSoc middleware is logically centralized leading to "big brother" concerns similar to existing OSNs.

Prometheus Design

User Registration

Users register with Prometheus from a trusted device by contacting any peer in the network and are assigned a unique user id (U ID). At registration time, they specify the peer(s) they will contribute to the network (if any). The peer handling the registration creates a mapping between U ID and the list of these peers' IP addresses. This mapping is stored in the network as the key-value pair U ID={IP 1, ..., IP n}. When a peer returns from an offline state, it updates the mapping with its current IP address. Users have a pair of public/private keys, and the mappings are signed with their private key.

Users select, deploy, and configure the social sensors they want to use. They may wish to declare particular social relationships, such as family relations, that may prove difficult or impossible to infer by social sensors. Finally, they select an initial set of trusted peers based on out-of-bound trust relations with other Prometheus users. The larger the size of this set, the higher the service availability; but at the same time, the consistency and the overall performance may decrease. Users have also a pair of public/private keys for their trusted peer group. The group keys are transferred to each group peer by encrypting them with the peer's owner public keys. As social information about a new user will be incorporated in the social graph, users may be prompted with different choices for trusted peers (e.g., peers belonging to users with stronger ties).

Trusted Peer Group Management

We address three issues concerning the trusted peer group management of a user: (a) group membership, (b) search for trusted peers, and (c) group churn.

A user can add peers in the trusted peer group by executing a secure threeway handshake procedure which establishes a two-way trust relationship between her and the peer owner. All the messages in this exchange are signed and verified.

If the owner of a candidate peer accepts a peer addition request, the initiator will send the group keys to the new peer as described above. Then, the new peer subscribes to the Scribe Trusted Peer Group UID of the user.

If a user decides to remove a peer from the trusted group (e.g., she no longer trusts the peer's owner), the user submits an unsubscribe request to one of the other trusted peers. This request is multicast to all group peers. Then, the peer generates a new pair of public/private keys for the group; this pair is distributed to all other trusted peers except the newly removed one. Additionally, the social sensors must be informed that the public key of the group has been changed. A peer owner may also decide to remove her peer from a trusted group of another user. This request is multicast to all the other group members.

Service requests can be sent to any peer, but only the trusted peers of a user can provide data about that user. Therefore, a random peer can find trusted peers for a user by submitting a multicast request to the user's trusted peer group. The group peers respond with their signed membership which is verified for authenticity with the user's group public key. The random peer is subsequently able to directly communicate with the individual trusted peers.

Past replicates the sensor data, thus maintaining data availability. However, the social graph for a user is unavailable if all her trusted peers leave the network; no service requests involving this user can be answered until a trusted peer rejoins the network. We ensure that generated data (e.g., input from social sensors) are not lost while a user's group is down via replication in the DHT by PAST. If a peer becomes untrusted while offline, a trusted peer from the particular group instructs the returning peer to unsubscribe.

Geo-Social Graph Representation

Prometheus represents the social graph as introduced in [2]: a directed, labeled, and weighted multi-edged graph, maintained and used in a decentralized fashion, as presented in Figure 2.

Multiple edges can connect two users, and each edge is labeled with a type of social interaction and assigned a weight that represents the intensity of that interaction. The labels for interactions and their associated weights are assigned by sensors. From an application point of view, distinguishing between different types of interactions allows for better functionality. Weights are assigned as a function of the number and frequency of interactions. This allows for a more accurate estimation of relationship strengths [START_REF] Xiang | Modeling relationship strength in online social networks[END_REF]. The latest known location of a user is also maintained as an attribute of the vertex representing the user in the graph.

We chose to represent the graph as directed because of the well-accepted result in sociology that "ties are usually asymmetrically reciprocal" [START_REF] Wellman | Structural analysis: From method and metaphor to theory and substance[END_REF]. Representing edges as directed enhances security by limiting the potential effects of illegitimate graph manipulation. For example, if Alice repeatedly performs interactions with Bob that are not reciprocated, only the edge connecting Alice to Bob will have its weight increased, not the edge from Bob to Alice.

Social Sensors

Two types of social ties can typically be inferred from user interactions. The first type, object-centric ties, is identified through the use of similar resources or participation in common activities. Examples include tagging the same items in collaborative tagging communities such as Delicious or CiteULike and repeatedly being part of the same BitTorrent swarms. The second type, people-centric ties, is determined from declared social relationships (e.g., in online social networks), declared membership to groups (e.g., networks in Facebook or company name in LinkedIn), or collocation information.

Social sensors are applications that are installed on the user's mobile device or PC that aggregate and analyze the history of user's interactions with other users and report to Prometheus labels and weights corresponding to directed edges. These social data are encrypted with the public key of the user's trusted group, signed with the user's private key, and stored in the DHT by Past. Note that if web sensors (such as Facebook applications) are used, the data have to be first sent to one of the user's devices to be signed and encrypted. The data for each user are stored as records in an append-only file, named Social Data U ID. Only the trusted peers can decrypt these records.

We designed Prometheus to be oblivious to the types of social activity reported by social sensors, thus allowing extensibility. For example, many such sensors already exist, although they have been implemented in different contexts; these sensors record and quantify OSNs' user activity [START_REF] Lewis | Tastes, ties, and time: A new social network dataset using Facebook.com[END_REF], co-appearance on web pages [START_REF] Matsuo | Polyphonet: an advanced social network extraction system from the web[END_REF], or co-presence recorded as collocation via Bluetooth [START_REF] Eagle | Reality mining: sensing complex social systems[END_REF]. Sensors can perform relatively sophisticated analysis before sending the data to Prometheus. For instance, collocation social sensors can differentiate between routine encounters with familiar strangers and interactions between friends [START_REF] Eagle | Reality mining: sensing complex social systems[END_REF].

Social State Maintenance

The social data for each user are stored in the file Social Data U ID as encrypted records. To ensure atomic appends, a lock file associated with the data file is created by the sensor trying to append a record. Other sensors trying to append concurrently will receive an error when trying to create this file. Once the append is done, the lock file is deleted. Since the file is append-only, readers can access it at any time: in the worst case, they will miss the latest update.

Social sensors can send updates to create new edges, remove old edges, or modify an edge weight. Each record contains a sequence number and encrypted data with the label and its associated weight. Trusted peers periodically check the file for new records and retrieve all such records: this is easily done based on sequence number comparison starting from the end of the file. The peer decrypts the new records and verifies the digital signature to make sure the updates are authentic. Then, it updates the subgraph of the user with the newly retrieved records. For short periods of time, the trusted peers may have inconsistent data, but this is not a major problem as social graphs do not change often.

Social sensors may specify that certain edges must be "aged" over time if no new updates for those edges are received (i.e., lack of social interactions associated with those labels). The social sensors may also specify the decrement value and the time period for aging (these values are also stored in the Social Data U ID file for each user).

Service Interface

Prometheus implements in a distributed fashion a set of basic social inference functions, which are exposed to applications through a service interface. We assume that every device running an application that interacts with Prometheus caches a number of peer IP addresses to bootstrap the interaction.

Social Inference Functions: We implemented the following social inference functions; more complex inferences can be built on top of this set.

relation test(ego, alter, α, x) is a boolean function that checks whether ego is directly connected to alter in the social subgraph of ego by an edge with label α and with a minimum weight of x. A mobile phone application can use this function, for example, to determine whether an incoming call is from a coworker with a strong social tie, and therefore, should be let through even on weekends.

top relations(ego, α, n) returns the top n users in the social subgraph of ego (ordered by decreasing weights) who are directly connected to ego by an edge with label α. An application can use this function, for example, to invite users highly connected with ego to share content related to activity α.

neighborhood(ego, α, x, radius) returns the set of users in ego's social neighborhood of size radius who are connected through social ties of a label α and minimum weight of x. The radius parameter allows for a multiple hop search in the social graph (e.g., setting radius to 2 will find friends of friends). Our Call-Censor mobile phone application which silences ego's cell phone during meetings at work (Section 5.3) uses this function to determine if a caller is in ego's work neighborhood in the social graph even if not directly connected.

proximity(ego, α, x, radius, min distance, timestamp) is an extension of the neighborhood function which filters the results of the social neighborhood inference based on physical distance to ego. After the location information is collected for ego and the set of users is returned by neighborhood, proximity returns the set of users who are within min distance from ego. A mobile phone application might use this function to infer the list of collocated coworkers within a certain distance of ego. Users who do not share the location or have location information older than the timestamp will not be returned.

social strength(ego, alter) returns a real number in the range of [0, 1] that quantifies the social strength between ego and alter from ego's perspective. The two users can be multiple hops apart in the social graph. The return value is normalized, as shown below, to ego's social ties to ensure that the social strength is less sensitive to the social activity of the users. N W is the normalized weight between two directly connected users, K is the path length joining two indirect users, N i is a user in this path, w is the weight of an edge, and strength is the return value for a multi-hop path: N W (ego, neighbor i ) = all-labels w(ego, neighbor i ) max all-neighbors all-labels w(ego, neighbor)

.

(1)

strength path(N 1 , N 2 , . . . , N K ) = max all-paths min i=1,...,K-1 N W (N i , N i+1 ) K . (2)
Such a function could be used, for example, to estimate social incentives for resource sharing. We limit the length of the indirect path that connects two users to two, using a well-accepted result in sociology known as the "horizon of observability" [START_REF] Friedkin | Horizons of observability and limits of informal control in organizations[END_REF].

Inference Function Execution: Social inference requests are signed with the private key of the user who submitted them and sent to any Prometheus peer. The request will then be forwarded to one of the trusted peers of the user, which enforces the access control policies and verifies the submitter's identity through her public key. The peer fulfills the request by traversing the local social subgraph for the information requested by the application, encrypting and signing the result using the requesting user's public key and the trusted group's private key, respectively, and returning the result to the application.

For functions that need to traverse the graph for more than one hop (e.g., social strength), the peer will forward requests for information about other users to their trusted peers. The requests include the U ID of the original submitter (in order to verify her access rights). The peer signs these requests with the group private key and optionally encrypts them with the destination group public key. Each receiving peer authenticates the request and checks the access control policies for the requesting user. If the request is granted, the result is returned to the requesting peer. If the request still needs more information, the peer repeats the same process. Finally, the original requesting peer collects recursively all the replies and submits the final result to the application.

Access Control Policies

Users can specify access control policies (ACP) upon registration and can update them any time thereafter. These policies are stored on each trusted peer of the user and are applied each time an inference request is handled by these peers. For availability, the policies are also stored encrypted with the group public key in the DHT, thus allowing rejoining trusted peers to recover policies updated while the peer was offline. The same mechanism used for updating the social graph is used to update policies. As future work, we plan to investigate providing strong consistency for policies.

Currently, we consider four different categories of social information for which users can set access control policies: relations, labels, weights, and location. By design, ACPs are whitelists. To specify who is allowed to access these categories of social information, ACPs allow the following elements to appear: individual users, groups of users identified by labels, application name to allow access to certain applications no matter which user runs them, and number of social hops the requesting users must be within. To verify the access rights, Prometheus may call its inference functions. For example, to detect whether the originator of the request is within a certain number of hops, the originator is checked against the result of a two-hop neighborhood function. ACPs also allow for blacklisted users to provide convenience in the case that a user wants to provide access to a large set of users and exclude a small number of members of that set.

Relations, labels, and weights allow fine-grained control over access to users' social graphs. Setting the relations field would prevent any user not allowed access from completing an inference that asks whether the user is connected with some other user, which accounts for most social inferences. Social inference functions which make use of labels as a filter provide an increased amount of data about a user; hence, it is likely that users will set this field more restrictively than the relations field. Prometheus allows users to set restrictions for any label relations: hops-2 hiking-label: lbl-hiking work-label: lbl-work general-label: weights: location: hops-1 - -----------------blacklist: user-Eve Fig. 3. Example of an access control policy in Prometheus in their social graph in their ACP. Upon an inference request, Prometheus will first check to see if the specific label has any restrictions, and if not, check the "general-label" category for restrictions on all labels. Weights provide even more detail about user social graphs. Users can set additional restrictions upon social inferences that request weighted data. Finally, location governs access to any inference function which asks for a user's location. Figure 3 shows an example ACP for Alice that disallows any social inference that makes use of the social graph (through the relations field) originating from a user outside of two hops, with an additional restriction that only those connected to her with a "hiking" label can request social inferences for her "hiking" information, excluding the user Eve. Social inferences which use location are restricted to those she is directly connected with. If a "hiking" neighborhood inference is submitted to Alice, Prometheus checks her ACP in the order relations→hiking-label→weights.

Experimental Evaluation

We implemented Prometheus on top of the FreePastry Java implementation of Pastry DHT which also provides API support for Scribe and Past. The social graph management is implemented in Python. The Prometheus prototype was deployed and evaluated on PlanetLab.

Our evaluation had three goals: (1) measure Prometheus performance over a large scale worldwide distributed network using realistic workloads with a large number of users, created based on previous studies of social media user behavior;

(2) assess the effect of socially-aware trusted peer selection on the system's overall performance; and (3) validate Prometheus with a social application developed on mobile phones and measure the performance of this application. An implicit goal was to identify potential performance optimizations, as we focused so far on building a robust end-to-end system. The two metrics used in this evaluation were end-to-end response time to quantify the user-perceived performance and number of network messages to quantify the service overhead.

In the first set of experiments, we used 100 peers deployed on PlanetLab, and each peer submitted workload on behalf of 1000 users. The number of users trusting each peer was varied from 10 to 30, i.e., each user trusted 1 and 3 peers respectively. The user distribution across peers was varied using two methods: i) random -users randomly trust peers, and ii) social -socially connected users trust the same peer. We limit the number of users assigned on a peer to 30, based on sociological studies [START_REF] Friedkin | The development of structure in random networks: an analysis of the effects of increasing network density on five measures of structure[END_REF] that claim that, on average, an urban person has meaningful social relationships with about 30 other individuals.

The second set of experiments was designed to assess Prometheus performance when used with a real application and on a real social graph. We implemented a mobile application, CallCensor, that silences the phone ring based on the social context of the callee and the relationship with the caller.

In the experiments, we used a timeout of 15 seconds for every social hop in the graph traversed by Prometheus to fulfill a request. After this timeout, a Prometheus peer handling either the initial request or subsequent secondary requests responded with the results it had at that point. Applications could modify the timeout parameter to trade waiting time for more information returned by social inferences.

Synthetic Workloads and Social Graph

We evaluated the operation of Prometheus with a large user base. We emulated the workload of two socially-aware applications and one social sensor based on previous system characterizations [START_REF] Wilson | User interactions in social networks and their implications[END_REF][START_REF] Krishnamurthy | A few chirps about twitter[END_REF][START_REF] Guo | Measurements, analysis, and modeling of bittorrent-like systems[END_REF].

Workload for Social Sensor: We emulated a Facebook social sensor based on a Facebook trace analysis [START_REF] Wilson | User interactions in social networks and their implications[END_REF]. The workload was characterized by the probability distribution function for users to post comments on walls and photos. Users were ranked into groups based on their social degree and each group was mapped onto a probability class using the cumulative distribution function from Figure 8 in [START_REF] Wilson | User interactions in social networks and their implications[END_REF]. To emulate a social interaction from ego to alter, a group was selected based on its associated probability, and a user ego from the group (who was not selected yet) was picked as the source of input. Alter was randomly selected from the ego's direct social connections. The weight of each input was kept constant to a small value for all users. Since users were picked based on their social degree, the users with higher social degree probabilistically produced more input, leading to higher weights on their corresponding edges in the social graph.

Workload for Neighborhood Inference: We used an analysis of Twitter traces [START_REF] Krishnamurthy | A few chirps about twitter[END_REF] to associate a tweet with a neighborhood request (centered at the leader of the tweet) in Prometheus. Thus, we extracted the probability distribution function of submitted requests. Users were ranked into groups based on their social degree ratio (the number of incoming edges divided by the number of outgoing edges). Based on Figure 4 in [START_REF] Krishnamurthy | A few chirps about twitter[END_REF], each group was mapped onto a particular probability to be selected for a neighborhood request. Once the group was selected, a user from the group (who was not selected yet) was picked to be the source of the request. The number of hops for the request was randomly picked from 1, 2 or 3 hops.

Workload for Social Strength Inference: We used an analysis of Bit-Torrent traces to emulate the workload of a battery-aware BitTorrent applica- tion [START_REF] King | BatTorrent: A battery-aware bittorrent for mobile devices[END_REF] on mobile devices: a user may rely on social incentives to be allowed to temporarily "free ride" the system when low on battery. Members of the same swarm check their social strength with the needy leecher to see if they want to contribute by uploading on her behalf. We assumed that users participated at random in swarms. Two users were randomly selected as the source and destination of the social strength inference request. The user selected as the source was associated with a total number of requests she would submit throughout the experiment. This number was extracted from an analysis of BitTorrent traces (Figure 9b in [START_REF] Guo | Measurements, analysis, and modeling of bittorrent-like systems[END_REF]).

Social Graph: We used a graph of 1000 users created with a synthetic social graph generator described in [START_REF] Sala | Measurementcalibrated graph models for social network experiments[END_REF]. The generator consistently produces graphs with properties such as degree distribution and clustering coefficient similar to real social graphs. We used this graph as a bidirectional graph and applied a low weight threshold on the inference requests to produce a high-stress load.

Results from Synthetic Workload Experiments

For every run of the experiments, more than 200,000 social strength and neighborhood requests and more than 32,000 social inputs were submitted from the emulated applications and social sensors. Figure 4 shows the end-to-end average response time for the neighborhood inference. We learn four lessons from these experiments.

First, the social-based mapping of users onto peers leads to significant improvements, especially for the 30 users/peer case. For this case, we have as much as 15% of the invocations finishing faster when compared to the random case (some invocations can finish in half the time). Additionally, the benefits compound as the number of hops increases. Of course, the difference is visible only for 2 and 3 hops, as the 1 hop function is computed locally. While we do not plot the number of messages in the system for the sake of brevity, we notice that the social-based mapping reduces the communication overhead by more than an order of magnitude. Second, the results show that a three-fold improvement in service availability can be achieved with minimum performance degradation. This is because the graph on the right side has three times more trusted peers per user and its overall response time is only marginally inferior compared with the graph on the left. Therefore, Prometheus design for availability (i.e., replicating the social graph on all trusted peers) is proven to work well in a realistic scenario.

Third, the absolute values of the response time are relatively high, especially for 2 and 3 hops. This is mostly due to the communication delay introduced by the P2P network. In our testbed, the average RTT is 200-300 msec. This value is multiplied by the number of hops traveled by a request/response. For example, for 10 users/peer, an average of 67 peers have to be contacted to collect neighborhood data from users located 3 social hops away (the number of users is 350). To improve these results, we plan to implement caching of recently computed results as well as pre-computing results in the background. These methods are expected to work well because the social graph changes rarely. Therefore, the cost associated with maintaining consistency should be low.

Fourth, creating the trusted peer list can be an expensive operation. Let us recall that a request can arrive at a random node, which has to first acquire the list of trusted peers for the user, and then forward the request to one of these trusted peers. This operation involves several lookups in the DHT, which result in multiple peer traversals. To solve this problem, Prometheus caches the list of trusted peers after the first access. The two graphs show the performance using this caching mechanism. The overhead associated with the cold start of creating the trusted peer list is as much as 10 sec for 3 hops.

Figure 5 shows the end-to-end average response time for the social strength inference. The performance is almost identical to the one for neighborhood for 2 hops because this function has to verify all possible paths between two users, but is limited to users located 2 social hops away.

CallCensor: A Real-Time Mobile Socially-aware Application

The CallCensor application leverages social information received from Prometheus to decide whether to allow incoming calls to go through. In addition to the social information from Prometheus, this application uses the phone location to infer whether the user is in a meeting (e.g., in the office). For each incoming call, the application queries Prometheus with a social strength or neighborhood inference request to assess the type of social connection between the caller and the phone owner. Based on the owner settings (e.g., allow calls from the spouse anytime), the application decides if the phone should ring, vibrate or silence upon receiving the call. The application was written in Java for mobile devices running the Google Android OS and was tested on a Nexus One mobile phone from HTC (1GHz processor, 512MB RAM).

We tested three scenarios in which a caller can be connected to the callee: directly connected within 1 social hop, indirectly connect by 2 social hops, and connected with a high social strength (independent of the number of hops). We tested each of these scenarios 50 times on 3 PlanetLab peers. We measured the end-to-end response time of an inference request submitted to Prometheus. This experiment introduced additional overhead due to the communication between the mobile application and Prometheus.

The social graph used in these experiments was based on data collected at NJIT. The graph has two types of edges, representing Facebook friends and Bluetooth collocation. Mobile phones were distributed to students and collocation data (determined via Bluetooth addresses discovered periodically by each mobile device) were sent to a server. The same set of subjects installed a Facebook application to participate in a survey, and they gave us permission to collect their friend lists. The user set was small (100 users) compared to the size of the student body (9000), therefore resulting in a somewhat sparse graph. About half of the subjects reported less than 24 hours of data over the span of a month. The collocation data have two thresholds of 45 and 90 minutes for users to have spent together; thus, the 90 minute collocations comprise of a subgraph of the 45 minute collocations.

While the edges on the graph were not initially weighted, we applied synthetic weights of 0.1 for "facebook" edges, 0.1 for "collocation" of 45 minutes and 0.2 for "collocation" of 90 minutes. For the experiments, we consider the "collocation" edges to represent a work relationship, while the "facebook" edges represent a personal relationship. The user (ego) was assumed to be in a work environment when another user (alter ) called. Figure 6(a) illustrates this graph and demonstrates one of the features of Prometheus: using multi-edge graphs provides for better social inferences. Neither the "facebook" nor the "collocation" graph is connected, but the graph containing both types of edges is.

The users were assigned to trust 3 PlanetLab peers using a social-based distribution. For each of the scenarios tested, the ego and alter were randomly chosen, and the inference request was sent to a random peer.

Figure 6(b) presents the end-to-end average response time for the requests sent by CallCensor for the three cases mentioned above. The results also show the time spent by the requests only in Prometheus. We first observe that the results are acceptable for the real-time constraint of the application: the response must arrive before the call is forwarded to the voice-mail of the callee. Second, we notice that the application itself introduced a significant overhead: for example, 50% in the 2-hop neighborhood and social strength cases due to both communication overhead and relatively slow execution on the mobile phone. Third, we observe the similarity of the social strength results with the neighborhood for 2 social hops, as found in the previous experiments.

Conclusions and Future Work

This paper presented Prometheus, a P2P service that enables socially-aware applications by providing decentralized, user-controlled social data management. Its decentralized, multi-edged, directed and weighted graph offers a fine-grained representation of the users' social state. Since Prometheus provides good privacy and availability, we expect users to provide a significant amount of social information, well beyond what is available today. We built and evaluated Prometheus using a large scale distributed testbed and a realistic workload. Additionally, we implemented a proof-of-concept mobile social application that utilizes Prometheus functionalities. The performance results can certainly be optimized as we focused only on functionality so far. As mentioned in the previous section, we plan to cache and pre-compute results benefiting from the slow changes that occur in social graphs. A possible solution for ensuring consistency in such a case is to use the DHT storage to store "dirty bits" for each user. These bits would show if users' information has been updated by social sensors, thereby informing peers that their cached results are stale and that they should rerun the inferences.

We plan to expand the set of social inferences as well as to allow different sensors to provide input for the same label. Additionally, we will explore activity ontologies, provided to social sensors by Prometheus, to support label consistency across multiple sensors.

Prometheus peers have been assumed trusted and cooperative. Due to its distributed nature, Prometheus is harder to be completely compromised than centralized solutions. Similarly, it is more resilient to DoS attacks. Nevertheless, we plan to examine the implications of malicious users and peers in the near future. Of special concern is the case where a (previously) trusted peer becomes malicious. While this newly malicious peer can certainly be removed from a user's trusted peer group, it still retains previously acquired social knowledge, and thus, the ability to subvert the service experienced by the user-owner of the social data. Also, a trusted peer can become faulty and provide inaccurate results. We plan to investigate Byzantine fault-tolerance protocols to guarantee the validity of the results. Finally, while our default access control policies prevent any single user from gaining knowledge of the entire graph, we have yet to ascertain what level of collusion between users would expose the entire graph.

Fig. 1 .

 1 Fig. 1. Prometheus architecture: The service runs on top of Pastry, a DHT-based overlay, Scribe, a DHT multicast infrastructure, and Past, a DHT storage system. The social data from sensors are encrypted and can be stored at any peer. The social subgraphs are stored on groups of trusted peers. Each peer runs three Prometheus components for social graph management, privacy management, and trusted group management. Same color nodes are members of a user's trusted peer group. Continuous (red ) arrows show group communication for social graph maintenance, while dashed (blue and green) arrows show social inference queries submitted to other peers.

Fig. 2 .

 2 Fig. 2. An example of a social graph for eight users (A-H ) who own seven peers. The mapping between users, peer owners, and trusted peers is shown in the upper left corner. Each edge is marked with its label and weight. The bottom figures illustrate the subgraphs maintained by peers 1 and 5. Users shown in dark color (e.g., users A, B and C on peer 1 ) trust the peer to manage their social data. Users shown in light shaded color (e.g., users E and D on peer 1 ) do not trust the peer but are socially connected with users who do.

Fig. 4 .

 4 Fig.[START_REF] Borcea | P2P systems meet mobile computing: A communityoriented software infrastructure for mobile social applications[END_REF]. CDF for the average end-to-end response time of neighborhood inference for two types of user-to-peer mapping (Random and Social ) and two numbers of users per peer (10 or 30 ).

Fig. 5 .

 5 Fig.5. CDF for the average end-to-end response time of social inference function social strength (Socs) for two types of user-to-peer mapping (Random and Social ) and two levels for number of users per peer (10 and 30 users per peer).

Fig. 6 .

 6 Fig. 6. The input social graph (a) has two types of edges: black dashed lines are Facebook edges, and red continuous lines are collocation edges. Line thickness demonstrates the weight of the edge. The results (b) show the CDF for the average end-to-end response time of CallCensor on 3 PlanetLab nodes for neighborhood for 1 and 2 hops and social strength (SocS). We show the time needed by Prometheus to produce a response and also the overall time needed by CallCensor to request and handle this response.

Acknowledgments. This research was supported by the NSF under Grants No. CNS 0952420, CNS 0831785 and CNS 0831753. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the sponsors. We thank Daniel Boston, Juan Pan, and Steve Mardenfeld from NJIT for collecting the Bluetooth collocation traces.