Adolescent girls and young women (AGYW) in sub-Saharan Africa face unique barriers to contraceptive access and lack AGYW-centered contraceptive decision-support resources. To empower AGYW to make informed choices and improve reproductive health outcomes, we developed a tablet-based application to provide contraceptive education and decision-making support in the pharmacy setting - a key source of contraceptive services for AGYW - in Kenya. We conducted workshops with AGYW and pharmacy providers in Kenya to gather app feedback and understand how to integrate the intervention into the pharmacy setting. Our analysis highlights how intermediated interactions - a multiuser, cooperative effort to enable technology use and information access - could inform a successful contraceptive intervention in Kenya. The potential strengths of intermediation in our setting inform implications for technological health interventions in intermediated scenarios in \lrem{LMICs}\ladd{low- and middle-income countries}, including challenges and opportunities for extending impact to different populations and integrating technology into resource-constrained healthcare settings.

As noncommunicable diseases (NCDs) become more prevalent, countries around the world are investing resources into the development of artificial intelligence (AI) enabled tools to support the last mile delivery of NCD care. Through 14 interviews with government officials, community health workers, and senior health practitioners in Nepal, we outline eight facets of the imagined future of AI-enabled NCD care. We create a blueprint of the technology systems needed to support a simple AI-enabled NCD diagnostic in Nepal, and connect the components in this blueprint to interviewee-described realities of working at the margins of the Nepali health system. By ensconcing the technology systems needed to support AI-enabled NCD care into current lived experiences of caregiving, we unearth frictions that may prevent the realization of the imagined futures of AI-enabled health. Through our method and analysis, we aim to empower researchers and leaders to create sociotechnical systems that can deliver on their potential and promise.

eHealth has strong potential to advance HIV care in low- and middle-income countries. Given the sensitivity of HIV-related information and the risks associated with unintended HIV status disclosure, clients’ privacy perceptions towards eHealth applications should be examined to develop client-centered technologies. Through focus group discussions with antiretroviral therapy (ART) clients from Lighthouse Trust, Malawi’s public HIV care program, we explored perceptions of data security and privacy, including their understanding of data flow and their concerns about data confidentiality across several layers of data use. Our findings highlight the broad privacy concerns that affect ART clients’ day-to-day choices, clients’ trust in Malawi’s health system, and their acceptance of, and familiarity with, point-of-care technologies used in HIV care. Based on our findings, we provide recommendations for building robust digital health systems in low- and middle-income countries with limited resources, nascent privacy regulations, and political will to take action to protect client data.

Although farmers in Sub-Saharan Africa are accessing feature phones and smartphones at historically high rates, they face challenges finding a robust network of agricultural contacts. With collaborators, we conduct a quantitative survey of 1014 agricultural households in Kagera, Tanzania to characterize technology access, use, and comfort levels in the region. Recognizing the paucity of research on dual-platform technologies that cater to both feature phone and smartphone users, we develop and deploy eKichabi v2, a searchable directory of 9833 agriculture-related enterprises accessible via a USSD application and an Android application. To bridge the gap in affordances between the two applications, we conduct a mixed methods pilot leveraging mobile money agents as intermediators for our USSD application’s users. Through our investigations, we identify the advantages, obstacles, and critical considerations in the design, implementation, and scalability of agricultural information systems tailored to both feature phone and smartphone users in Sub-Saharan Africa.

The development and adoption of eHealth in low- and middle-income countries has potential to advance the quality of care in healthcare settings that are challenged by weak infrastructure. Especially in the countries where HIV rates are high, there is need to implement electronic medical record systems to enhance care and improve treatment outcomes. Due to the sensitivity of HIV-related information, eHealth applications in HIV care necessitate the attention and prioritization of data security and privacy. We explored diverse stakeholders' views on data security and privacy in Malawi's public HIV care program to expand the understanding of gaps and opportunities in improving data protections. This work connects data security and privacy goals and practices with previous work on mobile device usage as well as global best practices for security and privacy in healthcare settings. A key finding articulated by stakeholders is the importance of establishing strong data security governance.

Information services for maternal and child health are increasingly being implemented at scale and integrated into public health infrastructures in Global South countries. These services often disseminate tailored health information and provide channels for families to ask questions to health workers. With increasing uptake, these services are intervening into a highly gendered space and shaping care work and information-seeking in new ways. We present a study of a patient education program and associated WhatsApp-based information service deployed across multiple states in India, drawing on observations, interviews, and analysis of chat records. Building on notions of “unsettling care” [63], we examine what it means to deploy such an intervention in inequitable, fragmented health systems. We find that even as the intervention focuses on individual behavior change, it also runs up against structural issues, such as the overburden of health workers, an illegible health system, and gendered power dynamics that extend beyond the realm of the home. We use our findings to unsettle notions of how the intervention provides care, and to reframe how we might think about the design and implementation of health information services to also engage with structural issues.

The evolving socio-technical landscape in peri-urban Tanzania has paved the way for a dramatic increase in smartphone-supported micro and small enterprises. We conduct surveys and focus groups with 46 such entrepreneurs, shedding light on the internal mechanisms and external networks of their businesses. We uncover the new trust dynamics encountered in online interactions, the gendered aspects of this emerging business model, and the means through which people with low capital are reclaiming economic empowerment through entrepreneurship.

Seeking to address barriers to in-person care, governments and non-governmental organizations (NGOs) globally have been pushing for scaling chat- or phone-based information services that rely on care workers to engage with users. Despite theoretical tensions between care and scale and the essential role of care workers, workers' perspective on scale and its impact on care provision is rarely centered early on in decisions to scale. In this paper, we examine care and scale from the perspective of medical support executives (MSEs) who support a chat-based health information service for maternal and child health deployed across multiple states in India. We draw on observations of MSEs' work, interviews with MSEs, NGO staff who implement the service, and families who use the service, and speculative design sessions conducted with MSEs. We find that by centering MSEs' perspectives, we can differentiate between growth of the relationships and heterogeneity that enable social impact, versus scale-thinking that promotes the decontextualization of care. We leverage our findings to discuss implications for scale and automation in chat-based health information services, including the importance of human connection, place, and support for care workers.

HCI is increasingly concerned with health information quality and spread of misinformation on social media. Despite many major platforms having been adopted across the world, the situated evaluation and sharing of health information is underexplored across diverse health systems and cultural and political contexts. Drawing on semi-structured interviews, we study the navigation of health information on social media in urban and rural South India, backdropped by plural knowledges around health and the specific politics and sociality of health and social media in this setting. We use Ivan Illich’s concept of tools for conviviality [49] to distinguish between how people creatively use tools versus how tools manage and impose values on people—participants aimed to use health information towards care beyond institutionalized healthcare, but insidious misinformation and information-sharing practices served to commodify, spark uncertainty in, and discipline caring behavior. We use our findings to expand understandings of the use of health information on social media and how positionality shapes how people are affected by and respond to misinformation. We also draw attention to the structural aspects of health misinformation in the Indian context and how the design of social media platforms might play a role in addressing it.

The use of blockchain in regulatory ecosystems is a promising approach to address challenges of compliance among mutually untrusted entities. In this work, we consider applications of blockchain technologies in telecom regulations. In particular, we address growing concerns around Unsolicited Commercial Communication (UCC aka. spam) sent through text messages (SMS) and phone calls in India. Despite several regulatory measures taken to curb the menace of spam it continues to be a nuisance to subscribers while posing challenges to telecom operators and regulators alike.

We present a qualitative study of a six-month pilot of WhatsApp-based facilitated peer support groups, serving youth living with human immunodeficiency virus (HIV) in an informal settlement in Nairobi, Kenya. Popular chat apps are increasingly being leveraged to make a combination of patient-provider communication and peer support more accessible beyond formal healthcare settings. However, how these interventions are experienced in Global South contexts with phone sharing and intermittent data access is understudied. The context of stigmatized illnesses like HIV further complicates privacy concerns. We draw on chat records and interviews with youth and the facilitator to describe their experience of the intervention. We find that despite tensions in group dynamics, intermittent participation, and contingencies around privacy, youth were motivated by newfound aspirations and community to manage their health. We use our findings to discuss implications for the design of chat-based peer interventions, negotiation of privacy in mobile health applications, and the role of aspirations in health interventions.

Interactive wildlife-tracking maps on public-facing websites and apps have become a popular way to share scientific data with the public as more conservationists and wildlife researchers deploy tracking devices on animals. Environmental organizations engage with the public for a variety of reasons: to raise awareness of environmental causes, build relationships with potential partners, and encourage people to take political and personal actions. However while there is a large body of work comparing different media strategies for environmental communication goals, the effectiveness of interactive data visualizations for these purposes remains unclear. This work examines the strengths and weaknesses of interactive wildlife-tracking maps for environmental communication. We interview conservationists about their aspirations for using these maps with their own data, and conduct a study gauging lay users’ reactions to different designs. Many conservationists aspire to create deep, immersive user engagements with these maps—letting users relate to data-driven stories about individual animals and freely explore the nuances of the tracking data. Our findings show potential for the most highly-motivated users to deeply engage with these data and stories, but more casually-interested audiences struggle with the maps’ complexities. However for casual audiences, wildlife tracking maps can still superficially but effectively showcase the organizations’ work to protect the species; perhaps inspiring hope for their future, attracting audiences to other communication channels to learn more, and adding to the organizations’ credibility. Following these insights, we present a set of design considerations for further development of similar wildlife-tracking map applications; emphasizing their needs for user onboarding, context for data interpretation, and integration with relatable media.

This paper explores the challenge of taking Global Goods software to international scale. Global Goods software is non-commercial software designed to support global development goals. We argue that a fundamental challenge behind this type of software is the different roles of the global organizations that fund projects, the country leadership that controls implementation, and the actual users of the software. To address this, it necessary to have a design process that balances interests of stakeholders and a technical design that allows for modularity and extensibility. We present a case study of an application for country level management of the immunization cold chain that we have developed and contrast it with major Global Goods software systems such as DHIS2 and OpenMRS. The contributions of the work include the design of a pipeline for building a Global Goods application that is deployed across multiple countries, a collection of lessons learned during system design and implementation, and a comparison of extensibility strategies of different global goods applications.

Across the world, government websites are expected to be reliable sources of information, regardless of their view count. Interactions with these websites often contain sensitive information, such as identity, medical, or legal data, whose integrity must be protected for citizens to remain safe. To better understand the government website ecosystem, we measure the adoption of https including the "long tail" of government websites around the world, which are typically not captured in the top-million datasets used for such studies. We identify and measure major categories and frequencies of https adoption errors, including misconfiguration of certificates via expiration, reuse of keys and serial numbers between unrelated government departments, use of insecure cryptographic protocols and keys, and untrustworthy root Certificate Authorities (CAs). Finally, we observe an overall lower https rate and a steeper dropoff with descending popularity among government sites compared to the commercial websites & provide recommendations to improve the usage of https in governments worldwide.

This paper studies the use of Digital Financial Services (DFS) as a solution to women's financial inclusion in deeply patriarchal, resource constrained communities. Through a qualitative, empirical study we map the financial life cycles of 20 women micro-entrepreneurs in different cities in Pakistan and the challenges they face. We explore how technology is currently influencing these women's businesses and personal lives and reveal how mobile money is not tuned to the problems they face and their financial needs. We present alternate design directions for meeting the technological and financial needs of these women, circumnavigating the patriarchal structures that constrain them.

Although voice forums are widely used to enable marginalized communities to produce, consume, and share information, their financial sustainability is a key concern among HCI4D researchers and practitioners. We present ReCall, a crowdsourcing marketplace accessible via phone calls where low-income rural residents vocally transcribe audio files to gain free airtime to participate in voice forums as well as to earn money. We conducted a series of experimental and usability evaluations with 28 low-income people in rural India to examine the effect of phone types, channel types, and review modes on speech transcription performance. We then deployed ReCall for two weeks to 24 low-income rural residents who placed 5,879 phone calls, completed 29,000 micro tasks to yield transcriptions with 85% accuracy, and earned INR 20,500. Our mixed-methods analysis indicates that each minute of crowd work on ReCall gives users eight minutes of free airtime on another voice forum, and thus illustrates a way to address the financial sustainability of voice forums.

HCI4D researchers and practitioners have leveraged voice forums to enable people with literacy, socioeconomic, and connectivity barriers to access, report, and share information. Although voice forums have received impassioned usage from low-income, low-literate, rural, tribal, and disabled communities in diverse HCI4D contexts, the participation of women in these services is almost non-existent. In this paper, we investigate the reasons for the low participation of women in social media voice forums by examining the use of Sangeet Swara in India and Baang in Pakistan by marginalized women and men. Our mixed-methods approach spanning content analysis of audio posts, quantitative analysis of interactions between users, and qualitative interviews with users indicate gender inequity due to deep-rooted patriarchal values. We found that women on these forums faced systemic discrimination and encountered abusive content, flirts, threats, and harassment. We discuss design recommendations to create social media voice forums that foster gender equity in use of these services.

SMS fraud has become a growing concern for those working toward financial inclusion, however, it is often unclear how widespread such threats are in practice. This multi-method study investigates SMS fraud in Pakistan through identification and categorization of fraudulent messages as well as the impact on those who receive such messages. We collect fraudulent SMS messages by various means, including byway of a custom-built Android smartphone application. To complement this, we interview people exposed to SMS fraud and representatives of mobile network operators. Based on our analysis, lottery type fraud schemes dominate SMS fraud in Pakistan, and these schemes have the greatest impact on vulnerable low-income, rural populations. We offer a simple heuristic for fraud detection that has a high accuracy rate and is adaptable to evolving fraud schemes, and conclude with a recommendation for a fraud mitigation strategy to target fraudster call back numbers.

The developing world has increasingly relied on data driven policies. Numerous development agencies have pushed for on-ground data collection to support the development work they pursue. Many governments have launched their own efforts for frequent information gathering. Overall, the amount of data collected is tremendous, yet there are significant issues in doing useful analysis. Most of these barriers manifest in data cleaning and merging, and require a data engineer to support some parts of the analysis. In this paper, we investigate the challenges of cleaning development data through an interview based study. We conducted face to face interviews of 13 stakeholders, eight from international development organizations and five government workers from Pakistan, including both managers and data analysts. From analysis of the interviews we identified common challenges faced in processing development data including correcting open text fields, merging hierarchical data, and extracting data from textual formats such as PDF. We construct a basic taxonomy of data cleaning challenges, and identify areas where support tools can improve the process. Ultimately, the objective is to empower regular data users to easily do the necessary data cleaning and scrubbing for analysis.

Many countries across the globe are engaged in efforts to promote a cashless society. In India, there is a strong top-down push by the government and the private sector for mobile payments. In this work, we examine the benefits and pitfalls people perceive in using mobile payments for customer-merchant transactions. Through interviews with 19 customers and 15 merchants across rural, periurban, and urban India, we explore people's awareness about mobile payment systems, perceived trade-offs among different payment methods, and the security, privacy, and utility barriers in its adoption and use. Overall, we found that customers were interested in adopting mobile payments for referral rewards and sign-up incentives, but were hesitant to regularly use them, whereas merchants saw mobile payments as an unnecessary burden for their business. We discuss the nuanced views of customers and merchants, and offer recommendations to address the barriers in the use of mobile payments for customer-to-merchant transactions.

Access to financial services through a mobile phone, known as Mobile Financial Services (MFS), creates an opportunity to expand the reach of financial services to the 1.7 billion unbanked adults worldwide. Nevertheless, MFS adoption has been inconsistent, which motivates a need to identify the challenges that MFS users confront in different countries. In this work, we explore the Twitter as a potential data source to understand such challenges. More broadly, we assess whether (and how) publicly available Twitter data can augment the findings of expensive, large-scale research studies on MFS barriers. Our Qualitative Content Analysis of 9,000 mobile money grievance tweets that were extracted from 54 MFS customer care twitter feeds across six countries reveals service and access issues, incorrect transactions, and fraud as three main challenges MFS users report on Twitter. We discuss the nuances around these challenges and the substantial differences between the common issues reported in different countries. Ultimately, we conclude that Twitter data can elucidate the challenges of MFS adoption and also that it can augment the results of other types of MFS studies.

The intersection of Islam and gender affect technological and social interactions for Muslim women in significant ways and remains an understudied domain for CSCW and related fields. Building on 73 qualitative interviews with low-income women in Punjab, Pakistan, we analyze the complexity of family relationships and the subsequent dynamics of authority around technology uptake and usage by women within non-Western contexts, and, specifically, within the Islamic world. We argue that a Pakistani woman's experience with technology depends on many factors, including gendered roles, generational differences in a family, and wider socio-cultural and religious influences against the backdrop of a culturally conservative and patriarchal society. Our paper highlights the rich family dynamics, including key life events, that transform the roles of both Muslim women and their relatives. Our work is intended to inform scholars, practitioners within development agencies and industry, and other individuals studying technology and development about household dynamics that influence Muslim women's use of technology to encourage them to consider these dynamics during design and implementation processes for technological inclusion.

We contribute to the growing conversation on assets-based approaches to design in Computer-Supported Cooperative Work (CSCW) and Human-Computer Interaction (HCI) with a qualitative study of resilience. Our study is situated within a community health infrastructure in a rural county in southwest Kenya, where health organizations pay community health workers' salaries via digital payments, backdropped by ongoing issues with missing and delayed payments. Through the lens of intersectionality, we examine how community health workers of diverse backgrounds and contracted status respond to the mandated use of digital payment methods and long payment delays. We highlight how resilience in this context is situated in workers' intersecting socioeconomic and professional identities, which shape the assets and constraints that workers engage with in efforts to be resilient. We leverage our findings to discuss how assets-based approaches to design can be further operationalized and used to sustainably support resilience.

Rotating Savings and Credit Association (ROSCA) is a mechanism of informal collaborative savings that is widely used across the globe. Despite its popularity and prevalence, it is not well-studied from HCI and CSCW perspectives. The global increase in mobile penetration has created opportunities to serve the unbanked using mobile-based Digital Financial Services (DFS) for greater financial inclusion but there have not been any DFS-based interventions around ROSCAs. In this paper, we report a qualitative study involving 80 individuals to understand the dynamics of ROSCAs and opportunities for their digitization in the Pakistani context. We also present a smartphone-based Digital ROSCA platform designed on top of a simulated mobile money system. The platform was designed to be inclusive towards low-literate users. We present qualitative findings of its evaluation with 15 users (3 individual ROSCA groups). We find that digitization has the potential to support and strengthen traditional ROSCAs by mitigating issues like record-keeping, delayed payments, collection, distribution, and safety of money. It also allows the creation of payment history for individuals that can be used to score their financial credibility.

Evaluations of technological artifacts in HCI4D contexts are known to suffer from high levels of participant response bias---where participants only provide positive feedback that they think will please the researcher. This paper describes a practical, low-cost intervention that uses the concept of social proof to influence participant response bias and successfully elicit critical feedback from study participants. We subtly exposed participants to feedback that they perceived to be provided by people 'like them', and experimentally controlled the tone and content of the feedback to provide either positive, negative, or no social proof. We then measured how participants' quantitative and qualitative evaluations of an HCI artifact changed based on the feedback to which they were exposed. We conducted two controlled experiments: an online experiment with 245 MTurk workers and a field experiment with 63 women in rural India. Our findings reveal significant differences between participants in the positive, negative, and no social proof conditions, both online and in the field. Participants in the negative condition provided lower ratings and a greater amount of critical feedback, while participants in the positive condition provided higher ratings and a greater amount of positive feedback. Taken together, our findings demonstrate that social proof is a practical and generalizable technique that could be used by HCI researchers to influence participant response bias in a wide range of contexts and domains.

BSpeak is an accessible crowdsourcing marketplace that enables blind people in developing regions to earn money by transcribing audio files through speech. We examine accessibility and usability barriers that 15 first-time users, who are low-income and blind, experienced while completing transcription tasks on BSpeak and Mechanical Turk (MTurk). Our mixed-methods analysis revealed severe accessibility barriers in MTurk due to the absence of landmarks, unlabeled UI elements, and improper use of HTML headings. Compared to MTurk, participants found BSpeak significantly more accessible and usable, and completed tasks with higher accuracy in lesser time due to its voice-based implementation. In a two-week field deployment of BSpeak in India, 24 low-income blind users earned rupee 7,310 by completing over 16,000 transcription tasks to yield transcriptions with 87% accuracy. Through our analysis of BSpeak's strengths and weaknesses, we provide recommendations for designing crowdsourcing marketplaces for low-income blind people in resource-constrained settings.

This paper presents eKichabi, a tool for retrieving contact information for agriculture-related enterprises in Tanzania. eKichabi is an Unstructured Supplementary Service Data (USSD) application which users can access through basic mobile phones. We describe our focus groups, a design iteration, deployment in four villages, and follow up interviews by phone. This work demonstrates the feasibility of USSD for information access applications that have the potential for deployment on a large scale in the developing world. From user interviews, we identified strong evidence of eKichabi fulfilling an unmet need for business related information, both in identifying business contacts in other villages, as well locating specific service providers. One of our key findings demonstrates that users access information through multiple modes, including text search, in addition to menu navigation organized by both business sector category and geographic area.

In resource-constrained economies, lack of financial participation prohibits women's economic empowerment and opportunities to improve circumstances. With the advent of Digital Financial Services (DFS), a growing emphasis has been placed on the possible positive impact of DFS on lives of individuals. However, for people to understand, adopt, and use DFS, they require certain prerequisites and enablers. In this paper, we use a mixed methods approach to analyze the gendered barriers in the readiness for and adoption of DFS as well as the impact of gendered roles in curtailing or enhancing the same. We present our analysis of 51 semi-structured interviews to evaluate the affordances or, lack thereof, in affordability of funds, authority of transactions, access to technological devices, and agency of social and cultural mobility--all of which are prerequisites to fully utilizing DFS. We discuss the sociocultural and religious context in Pakistan that underpins some of these gendered barriers and the perceived views of both men and women.

Maternal health outreach and engagement is a common goal of mobile health (mHealth) projects for development. Male partners of pregnant and postpartum women are known to be important influences on their health behavior. This paper presents a novel extension to previous HCI4D research by exploring how to engage male partners in SMS-based family planning conversations. First, we explore design considerations for inclusion of male partners in an existing semi-automated bidirectional SMS platform. A 12-month randomized controlled trial of a family planning counseling SMS program was conducted in western Kenya using our system. A total of 260 pregnant women and 101 of their male partners were enrolled in the system. We analyze enrollment and usage data from this trial to compare baseline technology use and demographics of mothers and their male partners. Our findings demonstrate significant technology gender divides in the study population. Finally, we explore how both the mothers and their male partners interacted with the SMS system through an analysis of over 11,500 messages. We conclude that it is feasible to include rural Kenyan men in an SMS-based family planning discussion program and that their inclusion does not dramatically affect the mothers' engagement.

Schools in the developing world frequently do not have high bandwidth or reliable connections, limiting their access to web content. As a result, schools are increasingly turning to Offline Educational Resources (OERs), employing purpose-built local hardware to serve content. These approaches can be expensive and difficult to maintain in resource-constrained settings. We present Siskin, an alternative approach that leverages the ubiquity of web browsers to provide a distributed content access cache between user devices on the local network. We demonstrate that this system allows access to web pages offline by identifying the browser as a ubiquitous platform. We build and evaluate a prototype, showing that existing web protocols and infrastructure can be leveraged to create a powerful content cache over a local network.

Prior research suggests that security and privacy needs of users in developing regions are different than those in developed regions. To better understand the underlying differentiating factors, we conducted a systematic review of Human-Computer Interaction for Development and Security & Privacy publications in 15 proceedings, such as CHI, SOUPS, ICTD, and DEV, from the past ten years. Through an in-depth analysis of 114 publications that discuss security and privacy needs of people in developing regions, we identified five key factors---culture, knowledge gaps, unintended technology use, context, and usability and cost considerations---that shape security and privacy preferences of people in developing regions. We discuss how these factors influence their security and privacy considerations using case studies on phone sharing and surveillance. We then present a set of design recommendations and research directions for addressing security and privacy needs of people in resource-constrained settings.

We present a mixed-methods study that compares and contrasts two distinct localization approaches for imparting video-based health education to rural Indian populations. Prior research efforts in the Human-Computer Interaction for Development (HCI4D) community have emphasized the value of localization of educational content. Our research uses a combination of focus groups, interviews, and knowledge retention tests to deconstruct what localization means and how it might be incorporated. Our findings highlight how characteristics of localized videos shape the participants' viewing experiences. For development-focused organizations that leverage video-based learning, our study provides insights regarding the costs and benefits of distinct localization approaches, and offers design recommendations for producing videos that yield greater traction and higher information absorption.

Speech transcription is an expensive service with high turnaround time for audio files containing languages spoken in developing countries and regional accents of well-represented languages. We present Respeak - a voice-based, crowd-powered system that capitalizes on the strengths of crowdsourcing and automatic speech recognition (instead of typing) to transcribe such audio files. We created Respeak and optimized its design through a series of cognitive experiments. We deployed it with 25 university students in India who completed 5464 micro-transcription tasks, transcribing 55 minutes of widely-varied audio content, and collectively earning USD 46 as mobile airtime. The Respeak engine aligned the transcript generated by five randomly selected users to transcribe Hindi and Indian English audio files with a word error rate (WER) of 8.6% and 15.2%, respectively. The cost of speech transcription was USD 0.83 per minute with a turnaround time of 39.8 hours, substantially less than industry standards. Using a mixed-methods analysis of cognitive experiments, system performance and qualitative interviews, we evaluate Respeak's design, user experience, strengths, and weaknesses. Our findings suggest that Respeak improves the quality of speech transcription while enhancing the earning potential of low-income populations in resource-constrained settings.

Worldwide, two billion people remain unbanked, the majority of whom reside in resource-constrained environments. While banks have limited reach due to high overhead costs of physical expansion, the global increase in mobile penetration has created opportunities to serve the unbanked using mobile-based Digital Financial Services (DFS). However, access to mobile applications alone is insufficient to ensure their trial, adoption, or continued usage. In this paper, we report a three phase learnability evaluation (N=118) of smartphone-based mobile wallet applications conducted in Pakistan. We discuss ways in which previous exposure or domain knowledge improve learnability, and we recommend that metrics for learnability should include effectiveness and help sought, independent of usability. We also identify DFS adoption opportunities such as user readiness, interface improvements, and women's independence. All of these opportunities stem from awareness and understanding of relevance, which in our case occurred as a consequence of exposure to the application under evaluation.

In resource-constrained communities, organizations often use information and communication technologies to amplify their limited resources to improve education, health, and economic opportunity. Over two-thirds of the world's population have mobile phones, yet less than half are connected to the Internet [23]. Organizations helping disadvantaged populations often rely on mobile devices as their primary computing resource because of their availability in resource-constrained contexts. However, to reach under-served populations, mobile applications often operate in areas with no connectivity or challenged network environments. Unfortunately, many mobile application frameworks are generally not well-suited for long periods of disconnected data collection and management. Furthermore, mobile application frameworks are generally aimed at users with significant technical skills and resources. In this paper, we discuss our experiences building, deploying, and refining the Open Data Kit (ODK) 2.0 tool suite. ODK 2.0 is a modular application framework that facilitates organizations with limited technical capacity to build application-specific information services for use in disconnected environments. We discuss ODK 2.0's flexible abstractions that enable users of varying technical skill levels to create customizable mobile data management solutions. We present ODK 2.0 case studies involving multiple organizations and discuss lessons learned from building a service-based mobile application framework for disconnected data management.

Many organizations in the developing world (e.g., NGOs), include digital data collection in their workflow. Data collected can include information that may be considered sensitive, such as medical or socioeconomic data, and which could be affected by computer security attacks or unintentional mishandling. The attitudes and practices of organizations collecting data have implications for confidentiality, availability, and integrity of data. This work, a collaboration between computer security and ICTD researchers, explores security and privacy attitudes, practices, and needs within organizations that use Open Data Kit (ODK), a prominent digital data collection platform. We conduct a detailed threat modeling exercise to inform our view on potential security threats, and then conduct and analyze a survey and interviews with technology experts in these organizations to ground this analysis in real deployment experiences. We then reflect upon our results, drawing lessons for both organizations collecting data and for tool developers.

We examine the dissemination of mobile phone videos in the context of Projecting Health - a community health project in rural India. Our research objective was to identify the most effective means of promoting the distribution of health videos on a largely offline network of mobile phones in a resource-constrained environment. We compared three different distribution channels: mobile shop owners, laptop owners, and community health workers in a fourteen-week intervention that relied on data collected via missed calls from viewers and callbacks made to them. We present the design of our experiment, describe the challenges in deploying this experiment, and discuss overall findings. All three distribution channels were successful in targeting the community; mobile shops had access to most community members but the community health workers were most successful in getting videos out to those who were most interested in viewing them. Many participants were motivated to distribute the videos for the benefit of community. However, the number of missed calls received decreased over time, suggesting the exploration of alternative mechanisms to extrinsically motivate intermediaries and viewers for broader video distribution.

We present the first analysis of the use and non-use of social media platforms by low-income blind users in rural and peri-urban India. Using a mixed-methods approach of semi-structured interviews and observations, we examine the benefits received by low-income blind people from Facebook, Twitter and WhatsApp and investigate constraints that impede their social media participation. We also present a detailed analysis of how low-income blind people used a voice-based social media platform deployed in India that received significant traction from low-income people in rural and peri-urban areas. In eleven-weeks of deployment, fifty-three blind participants in our sample collectively placed 4784 voice calls, contributed 1312 voice messages, cast 33,909 votes and listened to the messages 46,090 times. Using a mixed-methods analysis of call logs, qualitative interviews, and phone surveys, we evaluate the strengths and weaknesses of the platform and benefits it offered to low-income blind people.

We present our findings from a mixed methods study of mobile phone practices of rural Indian women. We situate our study in the context of Projecting Health, a public health initiative we deployed in Uttar Pradesh (India) to target the dissemination of health information for mothers and newborns. Adopting the lens of feminist reflexivity, we reconsider our design of Projecting Health by factoring in the mobile media consumption and sharing practices of our target audience. We stress the importance of taking a community-oriented approach and show that although there are strict social conventions and patriarchal norms that constrain various practices of these women, they are able to exercise agency and mobilize help within their communities when needed.

A growing body of HCI4D research studies the use of SMS communication to deliver health and information services to underserved populations. This paper contributes a novel dimension to this field of study by examining if a hybrid computer-human SMS system can engage pregnant women in Kenya in health-related communication. Our approach leverages the different strengths of both the computer and the human. The computer automates the bulk-sending of personalized messages to patients, allowing the human to read patients' replies and respond to those in need of attention. Findings from a 12-month deployment with 100 women show that our approach is capable of engaging the majority of participants in health-related conversations. We show that receiving messages from the system triggers participant communication and the amount of communication increases as participants approach their expected due date. In addition, analysis of participants' messages shows that they often contain sensitive health information conveyed through a complex mixture of languages and 'txting' abbreviations, all of which highlight the benefits of including a human in the workflow. Our findings are relevant for HCI researchers and practitioners interested in understanding or engaging underserved populations.

We present a qualitative study of Projecting Health, a public health project we deployed in rural Uttar Pradesh (India) to address persistently high maternal and infant mortality rates. This project is based on our model of Community-led Video Education (CVE), which leverages community resources for the generation, dissemination, and assimilation of visual media. We use the lens of information flows to examine how our instantiation of CVE enables the translation of globally approved health care norms to local household practices. We also demonstrate how CVE allows for integration with current community practices, existing state-supported health care infrastructure, social and patriarchal structures, and power dynamics within our target populations to drive community participation.

This note presents data from two large-scale data reporting projects in Pakistan and Laos using SMS as a channel of data collection. These projects share several major features: (1) the use of health workers personal mobile phones for data reporting (2) support from the Ministry of Health (3) planned expansion to every health facility in the country or province and (4) low ICT penetration at the periphery of the health system. Both projects are currently at the stage of rolling out to additional health facilities. The purpose of this note is to help understand the challenges faced in the early stages of the deployment by reviewing the content and errors in submitted SMS messages.

This note explores methods of analyzing questions asked during public health video showings. The goal is to provide feedback to content creators and session facilitators based a limited subset of the audience's questions. We analyze five videos produced in the first year of Digital Public Health focused on maternal health issues in rural India. We demonstrate a prototype web based tool to collaborate on the qualitative analysis of questions and propose mechanisms for systematically improving future videos based on this analysis. Initial results show that it is possible to extract useful information on how the target audience perceives the messaging in a video exclusively from questions asked. Based on these results we explain how Digital Public Health can integrate this feedback into an iterative review process for quality assurance of messaging.

In this paper we describe three different offerings of a multi-quarter multidisciplinary capstone experience where students engaged in designing and building technology to address problems faced by populations in local and remote resource-constrained environments. We define resource-constrained environments broadly (e.g., low-income communities, low bandwidth environments). These environments provide unique constraints (e.g., cultures where people are unfamiliar with or afraid of technology, environments where power and network connectivity are scarce and expensive). Students are partnered with organizations interested in piloting a solution they devise. The course brings together multidisciplinary teams of students to conduct fieldwork with potential user populations, design a technology to solve a problem inspired by a community-based organization, implement a solution, and evaluate that solution. Students work on projects with real-world impact and gain valuable experience with multidisciplinary design and multidisciplinary team work. In this paper we describe the three class formats we have attempted, sample student projects, and course outcomes based on student projects and survey responses. We also address the various ways projects have continued past the course, and we analyze the structural course and project elements that have contributed to student and research successes.

This paper describes the process of introducing software for managing vaccine cold chain equipment to the ministries of health in several countries. The software, Cold Chain Equipment Manager (CCEM), is used to maintain a country wide inventory of vaccine refrigerators and cold rooms, and provides analysis and forecasting capabilities. The paper examines the characteristics of software used at the national level and the role of multiple stakeholders in adoption and use of systems. Based on deployment of the system in countries in Africa and Latin America, and interviews with immunization program officers, we conclude that this type of software can meet country needs in planning a more efficient vaccine cold chain and increasing system transparency provided that it is situated is a broader system committed to strengthening immunization programs.

We describe a two-year study of the use of facilitated video instruction in government primary schools in North India. The study involved deploying Digital StudyHall (DSH) in eleven schools, and following the progress of participating teachers in adopting the technology and pedagogy. The goal of the study was to evaluate the potential for large scale expansion of the DSH model into other government schools. Even though the system was used consistently, and was evaluated favorably by teachers and students, we found significant obstacles to scalability and sustainability of DSH in North Indian government schools.

The educational system, especially in developing regions, remains one of the most challenging systems for intervention and implementation of change. The objectives of this paper are to present findings of the first year of an evaluation study of Digital StudyHall (DSH), a Facilitated Video Instruction system being used in rural primary schools in India. Our analysis shows that the DSH system supports classrooms by providing teachers with instructional resources, access to expertise, and in-practice professional development.

Applying information and communication technologies to development (ICTD) is emerging as an interesting and motivating research area in computer science and engineering. It spans application areas from healthcare to transportation, and requires the use of computing skills from networking to user interface design. Addressing problems of developing regions and under-served communities lets students explore a different part of the ICT design space, leading to new implementation and research questions. ICTD is also an area that has the potential to excite students about the CSE field more generally, with its emphasis on enabling social benefits with technology, and is rich in possibilities for interesting student projects. In this paper we report on two offerings of a course at the University of Washington that introduce students to the field by way of 1) reading papers from literature in the area to gain exposure to this very different design mindset and 2) doing practical projects that engage students in engineering problems under unique design constraints. Our hope is that CSE educators may find our experiences useful in identifying an approach to integrating the field of ICTD into their curricula.

We present a case study of an international distance education course involving two sites in the US and one site in Pakistan. We use the case study to examine the elements of the distance learning environment, and specifically how those elements can be best used to promote classroom interaction. In particular we discuss the effectiveness of two software tools for distance learning that we have developed: ConferenceXP for video conferencing and Classroom Presenter to facilitate interaction across sites. We bring special attention to the use of student artifacts including digital ink and text, and their use in the presentation of design proposals, the facilitation of critiques, and in the promotion of general interaction.

Past research has shown the benefits of increased engagement and collaboration for learning using multiple inputs for children sharing computers. Taking the work forth beyond clicks, we demonstrate the use of inexpensive numeric keypads as multiple input devices in shared computing scenarios, as many have argued are well-suited to the developing world, and show its utility in mathematical learning for young children.

In this paper, we describe preliminary work on an ink editing application that allows an instructor to correct mistakes to digital ink written during a presentation that is to be archived. These corrections are then seamlessly reintegrated into the digital archive so that when the presentation is replayed the corrected ink is displayed instead of the original incorrect ink. We base our results on a system we have developed and prototype the work flow from initial presentation, through correction, updating the archive and playback. We show that a simple mechanism for correction is effective and low effort for the instructor. A key technical challenge that is addressed is the substitution of strokes by matching of the original and corrected ink.

In this paper we discuss cultural issues encountered while offering an Algorithms course from a US university at a Chinese university using Tutored Video Instruction (TVI). TVI is a distance learning methodology where lectures are recorded at one site and then shown to a group of students at a remote site by Teaching Assistants (TAs) who stop the video periodically for questions and discussion. In conducting this cross-cultural class, we were interested in determining if we could overcome the issues of using English language materials for Chinese students, achieve a sense of local ownership of the course, and create an interactive classroom environment. We were generally successful in achieving these goals by providing supporting materials and working closely with the Teaching Assistants who served as facilitators.

This paper describes an application of classroom technology in support of teaching through the use of examples and active learning techniques. Here we report on using Classroom Presenter, a Tablet PC based classroom interaction syst, in a senior level course in Algorithms -- a domain for which the instructor believes working on sample probls is critical to student learning in the classroom. The role of the technology was to integrate activities into the lecture so that students have the opportunity to work with concrete examples in class, while the instructor can collect and review student work in real time, incorporating selected student answers into the discussion. In this paper, we describe the pedagogical goals of the instructor, the types of activities used to achieve those goals, and the role that technology played in supporting those goals and activities. The contributions of the paper are in showing how classroom technology can be used to support pedagogical choices, as well as in phasizing the value of having clear pedagogical goals when incorporating a new technology in the classroom. We believe the application of technology as illustrated in this work could bring similar benefits to the instruction in other disciplines.

This paper describes our experiences in promoting a learning environment where active student involvement and interaction, as well as openness to diversity of ideas are supported through innovative uses of technology in the classroom. In the context of an undergraduate course in software engineering, for two consecutive terms we have experimented with an existing software system for Tablet PCs that supports a set of classroom interaction styles. Our goal has been to determine if the use of the technology can increase the effectiveness of pedagogical techniques that naturally fit our instructional needs.We have found that student submissions -- a style of interaction whereby the instructor poses a question written on a slide and displayed on a tablet in front of each student, then students write their answers in digital ink and submit back to the instructor -- are a powerful tool for supporting the learning environment we aim to create in the classroom. We show that student submissions can help the instructor to engage all students, not merely the vocal ones, and to emphasize the value of diversity of opinions. They also enable immediate feedback from students to instructor -- something difficult in an environment without technological enhancements but which contributes to an improved understanding of everyone's needs and expectations.The discussion of how we used student submissions to support these pedagogical techniques may be relevant to educators interested in fostering student learning through creative uses of technology, as well as to instructors looking to expand their repertoires of teaching methods in software engineering and in other similar subjects.

Randomness and probability are essential notions in CS studies. They are invoked and employed in diverse courses at different levels. Although a structured course on these notions does not usually appear early in the curriculum, students and educators may benefit from their encapsulation already in CS0 and CS1. The special session will involve motivation, demonstration, and discussion with the audience of the assets of such an encapsulation. Attending CS educators will enrich their teaching perspectives, pedagogical tools, and assignment repertoires.

Abstract: Card sorts are a knowledge elicitation technique in which participants are given a collection of items and are asked to partition them into groups based on their own criteria. Information about the participant's knowledge structure is inferred from the groups formed and the names used to describe the groups through various methods ranging from simple quantitative statistical measures (e.g. co-occurrence frequencies) to complex qualitative methods (e.g. content analysis on the group names). This paper introduces a new technique for analyzing card sort data that uses quantitative measures to discover rich qualitative results. This method is based upon a distance metric between sorts that allows one to measure the similarity of groupings and then look for clusters of closely related sorts across individuals. By using software for computing these clusters, it is possible to identify common concepts across individuals, despite the use of different terminology.

Abstract: This paper presents a case study of the use of a repeated single-criterion card sort with an unusually large, diverse participant group. The study, whose goal was to elicit novice programmers' knowledge of programming concepts, involved over 20 researchers from four continents and 276 participants drawn from 20 different institutions. In this paper we present the design of the study and the unexpected result that there were few discernible systematic differences in the population. The study was one of the activities of the National Science Foundation funded Bootstrapping Research in Computer Science Education project (2003).

Digital inking systems are becoming increasingly popular across a variety of domains. In particular, many systems now allow instructors to write on digital surfaces in the classroom. Yet, our understanding of how people actually use writing in these systems is limited. In this paper, we report on classroom use of writing in one such system, in which the instructor annotates projected slides using a Tablet PC. Through a detailed analysis of lecture archives, we identify key use patterns. In particular, we categorize a major use of ink as analogous to physical gestures and present a framework for analyzing this ink; we explore the relationship between the ephemeral meaning of many annotations and their persistent representation; and we observe that instructors make conservative use of the system's features. Finally, we discuss implications of our study to the design of future digital inking systems.

In this paper, we report on an empirical exploration of digital ink and speech usage in lecture presentation. We studied the video archives of five Master's level Computer Science courses to understand how instructors use ink and speech together while lecturing, and to evaluate techniques for analyzing digital ink. Our interest in understanding how ink and speech are used together is to inform the development of future tools for supporting classroom presentation, distance education, and viewing of archived lectures. We want to make it easier to interact with electronic materials and to extract information from them. We want to provide an empirical basis for addressing challenging problems such as automatically generating full text transcripts of lectures, matching speaker audio with slide content, and recognizing the meaning of the instructor's ink. Our results include an evaluation of handwritten word recognition in the lecture domain, an approach for associating attentional marks with content, an analysis of linkage between speech and ink, and an application of recognition techniques to infer speaker actions.

Computer science instructors frequently teach using slides displayed with a computer and a data projector. This has many advantages, e.g., ability to present prepared materials and ease of switching the display to a development environment during mid-presentation. However, existing computer-based presentation systems severely limit flexibility in delivery, hindering instructors' extemporaneous adaptation of their presentations to match their audiences. One major limitation of computer-based systems is lack of support for high-quality handwriting over slides, as with overhead projectors and other manual presentation systems. We developed and deployed Classroom Presenter, a Tablet PC-based presentation system that (1) combines the advantages of existing computer-based and manual presentation systems and (2) builds on these systems, introducing novel affordances. Classroom Presenter has been used in 25 Computer Science courses at three universities. In this paper we describe the system, summarize results from its deployment, and detail several novel uses of the system by instructors in computer science courses.

We have developed and deployed a lecture presentation system in which the instructor uses a Tablet PC as a presentation device. The system was deployed in six university courses in Autumn 2002 and has been favorably received by students and instructors. In our system, the instructor holds a pen-based computer that is wirelessly networked with another computer driving the classroom projector. The instructor displays slides from the tablet and can write on top of them. Various navigation and control facilities are available.

In this paper we describe and evaluate Classroom Assessment Tools (CATs) designed to encourage interaction and student ownership in an introductory programming course (CS 1). Traditionally, Classroom Assessment Techniques allow instructors to collect feedback from students regarding their understanding of course material \citeangelo93. We developed and categorized over 60 specific CATs to facilitate discussion and learning in a CS 1 course.The Classroom Assessment Tools described in this paper highlight concepts from recorded lectures that are used in CS 1 distance courses employing the Tutored Video Instruction (TVI) model. We present a qualitative evaluation of Classroom Assessment Tools as discussion frameworks in a TVI course offering. Evidence from site observations, interviews with the instructor and students, and survey responses from the instructor and students indicate that the CATs created classroom interaction, improved students' attitudes in the course, and provided assessment opportunities for the instructor.

In this paper we describe our experiences of exporting our introductory programming courses to community colleges. We used Tutored Video Instruction (TVI) as the mode of instruction where recorded versions of our lectures were shown to groups of students with local instructors periodically stopping the lecture for questions and discussion. We have offered a total of 16 sections of TVI courses, 11 were of our first quarter programming course (CSE142), and 5 were of our second quarter programming course (CSE 143). The courses were offered at seven institutions. Approximately 180 students completed the courses.We identify factors which contributed positively and negatively to the use of TVI for introductory programming courses. The two most important changes to our TVI program based on these experiences will the use of studio produced lectures and the abandonment of centralized course administration.

Symbolic model checking based on binary decision diagrams is a powerful formal verification technique for reactive systems. In this paper, we present various optimizations for improving the time and space efficiency of symbolic modal checking for systems specified as statecharts. We used these techniques in our analyses of the models of a collision avoidance system and a fault-tolerant electrical power distribution (EPD) system, both used on commercial aircraft. The techniques together reduce the time and space requirements by orders of magnitude, making feasible some analysis that was previously intractable. We also elaborate on the results of verifying the EPD model. The analysis disclosed subtle modeling and logical flaws not found by simulation.

In this paper we study a geometric problem arising in typography: the problem of laying out a two dimensional table. Each cell of the table has content associated with it. We may have choices on the geometry of cells (e.g., number of rows to use for the text in a cell.) The problem is to choose configurations for the cells to optimize an objective function such as minimum table height given a fixed width for the table. We formulate a combinatorial version of the table layout problem, where the objective is to choose cell geometry to minimize table size. The table layout problem is NP-complete, even for very restricted instances. One of our main results is an algorithm for computing the convex hull of the set of feasible table configurations, which gives a heuristic algorithm for table layout. We establish a connection between the fractional (LP) solution to the table layout problem and generalized network flow. We also present experimental results comparing the performance of heuristic...

Article Free Access Share on Decoupling synchronization from local control for efficient symbolic model checking of statecharts Authors: William Chan Department of Computer Science and Engineering, University of Washington, Box 352350, Seattle, Washington Department of Computer Science and Engineering, University of Washington, Box 352350, Seattle, WashingtonView Profile , Richard J. Anderson Department of Computer Science and Engineering, University of Washington, Box 352350, Seattle, Washington Department of Computer Science and Engineering, University of Washington, Box 352350, Seattle, WashingtonView Profile , Paul Beame Department of Computer Science and Engineering, University of Washington, Box 352350, Seattle, Washington Department of Computer Science and Engineering, University of Washington, Box 352350, Seattle, WashingtonView Profile , David H. Jones The Boeing Company, Seattle, Washington The Boeing Company, Seattle, WashingtonView Profile , David Notkin Department of Computer Science and Engineering, University of Washington, Box 352350, Seattle, Washington Department of Computer Science and Engineering, University of Washington, Box 352350, Seattle, WashingtonView Profile , William E. Warner The Boeing Company, Seattle, Washington The Boeing Company, Seattle, WashingtonView Profile Authors Info & Claims ICSE '99: Proceedings of the 21st international conference on Software engineeringMay 1999 Pages 142–151https://doi.org/10.1145/302405.302460Online:16 May 1999Publication History 13citation235DownloadsMetricsTotal Citations13Total Downloads235Last 12 Months7Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

In this paper, we study data structures for use in N-body simulation. We concentrate on the spatial decomposition tree used in particle-cluster force evaluation algorithms such as the Barnes--Hut algorithm. We prove that a k-d tree is asymptotically inferior to a spatially balanced tree. We show that the worst case complexity of the force evaluation algorithm using a k-d tree is $\Theta(n\log^3n\log L)$ compared with $\Theta(n\log L)$ for an oct-tree. (L is the separation ratio of the set of points.) We also investigate improving the constant factor of the algorithm and present several methods which improve over the standard oct-tree decomposition. Finally, we consider whether or not the bounding box of a point set should be "tight" and show that it is safe to use tight bounding boxes only for binary decompositions. The results are all directly applicable to practical implementations of N-body algorithms.

We present various techniques for improving the time and space efficiency of symbolic model checking for system requirements specified as synchronous finite state machines. We used these techniques in our analysis of the system requirements specification of TCAS II, a complex aircraft collision avoidance system. They together reduce the time and space complexities by orders of magnitude, making feasible some analysis that was previously intractable. The TCAS II requirements were written in RSML, a dialect of state-charts.

In this paper, we present our experiences in using symbolic model checking to analyze a specification of a software system for aircraft collision avoidance. Symbolic model checking has been highly successful when applied to hardware systems. We are interested in whether model checking can be effectively applied to large software specifications. To investigate this, we translated a portion of the state-based system requirements specification of Traffic Alert and Collision Avoidance System II (TCAS II) into input to a symbolic model checker (SMV). We successfully used the symbolic model checker to analyze a number of properties of the system. We report on our experiences, describing our approach to translating the specification to the SMV language, explaining our methods for achieving acceptable performance, and giving a summary of the properties analyzed. Based on our experiences, we discuss the possibility of using model checking to aid specification development by iteratively applying the technique early in the development cycle. We consider the paper to be a data point for optimism about the potential for more widespread application of model checking to software systems.

In this paper, we prove new upper bounds on the complexity of the certified write-all problem with respect to an adaptive adversary. Our strongest result is that for any $\epsilon > 0$, there exists an $O(p^{1+\epsilon})$ work algorithm for the p-processor p-memory cell write-all. We also give a randomized $O(p^2\log p)$ work algorithm for a p-processor $p^2$-memory cell write-all.

In this paper, we study data structures for use in N-body simulation. We concentrate on the spatial decomposition tree used in particle-cluster force evaluation algorithms such as the Barnes-Hut algorithm. We prove that a k-d tree is asymptotically inferior to a spatially balanced tree. We show that the worst case complexity of the force evaluation algorithm using a k-d tree is /spl Theta/(nlog/sup 3/nlogL) compared with /spl Theta/(nlogL) for an oct-tree. (L is the separation ratio of the set of points.) We also investigate improving the constant factor of the algorithm, and present several methods which improve over the standard oct-tree decomposition. Finally, we consider whether or not the bounding box of a point set should be "tight", and show that it is only safe to use tight bounding boxes for binary decompositions. The results are all directly applicable to practical implementations of N-body algorithms.

In this paper we present our results and experiences of using symbolic model checking to study the specification of an aircraft collision avoidance system. Symbolic model checking has been highly successful when applied to hardware systems. We are interested in the question of whether or not model checking techniques can be applied to large software specifications.To investigate this, we translated a portion of the finite-state requirements specification of TCAS II (Traffic Alert and Collision Avoidance System) into a form accepted by a model checker (SMV). We successfully used the model checker to investigate a number of dynamic properties of the system.We report on our experiences, describing our approach to translating the specification to the SMV language and our methods for achieving acceptable performance in model checking, and giving a summary of the properties that we were able to check. We consider the paper as a data point that provides reason for optimism about the potential for successful application of model checking to software systems. In addition, our experiences provide a basis for characterizing features that would be especially suitable for model checkers built specifically for analyzing software systems.The intent of this paper is to evaluate symbolic model checking of state-machine based specifications, not to evaluate the TCAS II specification. We used a preliminary version of the specification, the version 6.00, dated March, 1993, in our study. We did not have access to later versions, so we do not know if the properties identified here are present in later versions.

Inequality constraints are useful for specifying various aspects of user interfaces, such as constraints that clne window is to the left of another, or that an object is contained within a rectangle.However, current local propagation constraint solvers can't handle inequality constraints.We present Indigo, an efficient local propagation algorithm for satisfying acyclic constraint hierarchies, including inequality constraints.

Article Free Access Share on Primitives for asynchronous list compression Author: Richard J. Anderson View Profile Authors Info & Claims SPAA '92: Proceedings of the fourth annual ACM symposium on Parallel algorithms and architecturesJune 1992 Pages 199–208https://doi.org/10.1145/140901.140922Published:01 June 1992Publication History 5citation97DownloadsMetricsTotal Citations5Total Downloads97Last 12 Months9Last 6 weeks3 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

We describe an efficient parallel implementation of Goldberg's maximum flow algorithm for a shared-memory multiprocessor.Our main technical innovation is a method that allows a "global relabeling" heuristic to be executed concurrently with the main algorithm; this heuristic is essential for good performance in practice.We present performance results from a Sequent Symmetry for a variety of input distributions.We achieve speed-ups of up to 8.8 with 16 processors, relative to the parallel program with 1 processor (5.8 when compared to our best sequential program).We consider these speed-ups very good and we provide evidence that hardware effects and insufficient parallelism in certain inputs are the main obstacles to achieving better performance.

We are interested in designing efficient data structures for a shared memory multiprocessor. In this paper we focus on the Union-Find data structure. We consider a fully asynchronous model of computation where arbitrary delays are possible. Thus we require our solutions to the data structure problem have the wait-free property, meaning that each thread continues to make progress on its operations, independent of the speeds of the other threads. In this model efficiency is best measured in terms of the total number of instructions used to perform a sequence of data structure operations, the work performed by the processors. We give a wait-free implementation of an efficient algorithm for Union-Find. In addition we show that the worst case performance of the algorithm can be improved by simulating a synchronized algorithm, or by simulating a larger machine if the data structure requests support sufficient parallelism. Our solutions apply to a much more general adversary model than has be...

Four algorithms are analyzed in the shared and nonshared (distributed) memory models of parallel computation. The analysis shows that the shared memory model predicts optimality for algorithms and programming styles that cannot be realized on any physical parallel computers. Programs based on these techniques are inferior to programs written in the nonshared memory model. The unit cost charged for a reference to shared memory is argued to be the source of the shared memory model's inaccuracy. The implications of these observations are discussed.>

In this paper we consider the problem of generating random permutations on small parallel machines.The machines that we have in mind are shared memory machines with a constant number of processors such as the Sequent Symmetry.We describe a parallel implementation of the "shuffling" algorithm for generating a random permutation.If the hardware operates in a fair manner, this algorithm generates a fully random permutation.However, if the machine resolves contention in a malicious manner, then the algorithm does not generate permutations uniformly.We give almost tight bounds on the degree that an adversary can reduce the randomness.We also discuss the cost of locking data in the algorithm and present a method of generating random permutations with substantially reduced locking cost.

We give the first efficient parallel algorithms for solving the arrangement problem. We give a deterministic algorithm for the CREW PRAM which runs in nearly optimal bounds of O(log n log * n) time and n²/log n processors. We generalize this to obtain an O(logn log* n) time algorithm using n^d/logn processors for solving the problem in d dimensions. We also give a randomized algorithm for the EREW PRAM that constructs an arrange-ment of n lines on-line, in which each insertion is done in optimal O(logn) time using n / log n processors. Our algorithms develop new parallel data structures and new methods for traversing an arrangement.

We introduce a task scheduling model which is useful in the design and analysis of algorithms for small parallel machines.We prove that under our model, the overhead experienced in scheduling an n x n grid graph is O(loglogn) for p processors, p > 2. We also prove a matching lower bound of Q(loglog n) for p processors, p 1 2. We give an extension of the model to cover the case where the processors can have varying speed or are subject to delay.

A directed cycle separator of an n-vertex directed graph is a vertex-simple directed cycle such that when the vertices of the cycle are deleted, the resulting graph has no strongly connected component with more than ${n / 2}$ vertices. It is shown that the problem of finding a directed cycle separator is in randomized NC. It is also proved that computing cycle separators and conducting depth-first search in directed graphs are deterministically NC-equivalent. These two results together yield the first randomized NC algorithm for depth-first search in general directed graphs.

A simple O(n log n) algorithm is presented for performing one-dimensional tile compaction on a planar constraint network. The algorithm works only on planar constraints networks: those resulting from considering all components to be on single layer. The top and bottom zones in this example attain their minimum widths of 15 only by forcing the other zone to have width 25, while the best configuration has width 20 which is the minimum width of the middle zone. VLSI circuits often result in nonplanar constraint networks, even though interconnect parallel to the direction of compaction is not part of the constraint network. The algorithm could be used to obtain an initial guess at the width, possibly saving several iterations of the more expensive minimum-cost flow method.>

A directed cycle separator of an n-vertex directed graph is a simple directed cycle such that when the vertices of the cycle are deleted, the resulting graph has no strongly connected component with more than n/2 vertices. This paper shows that the problem of finding a directed cycle separator is in randomized NC. The paper also proves that computing cycle separators and conducting depth-first search in directed graphs are deterministic NC-equivalent. These two results together yield the first RNC algorithm for depth-first search in directed graphs.

In this paper we present a fast parallel algorithm for constructing a depth first search tree for an undirected graph. The algorithm is an RNC algorithm, meaning that it is a probabilistic algorithm that runs in polylog time using a polynomial number of processors on a P-RAM. The run time of the algorithm is O(TMM(n)log3n), and the number of processors used is PMM(n) where TMM(n) and PMM(n) are the time and number of processors needed to find a minimum weight perfect matching on an n vertex graph with maximum edge weight n.

Article A parallel algorithm for the maximal path problem Share on Author: R Anderson Computer Science Department, Stanford University, Stanford, California Computer Science Department, Stanford University, Stanford, CaliforniaView Profile Authors Info & Claims STOC '85: Proceedings of the seventeenth annual ACM symposium on Theory of computingDecember 1985 Pages 33–37https://doi.org/10.1145/22145.22149Online:01 December 1985Publication History 4citation771DownloadsMetricsTotal Citations4Total Downloads771Last 12 Months6Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access