Increased sensing and data collection in electric power systems from utility to minigrid to individual household scale are resulting in an explosion of data collection about users and providers of electricity services. In the push to expand energy access for poor communities, the collection, use, and curation of these data have historically taken a back seat to the goal of expanding energy access but are increasingly being recognized as important issues. We review the nascent literature on this topic, characterize current data management practices, and examine how expanding access to data and data sharing are likely to provide value and pose risks to key stakeholders: end users of electricity, microutilities, macroutilities, governments, development institutions, and researchers. We identify the key opportunities and tensions and provide recommendations for the design and implementation of new data-sharing practices and platforms. Our review and analysis suggest that although a common and open platform for sharing technical data can mitigate risks and enable efficiency, fewer benefits are likely to be realized from sharing detailed financial data. We also recommend codesigning practices with each stakeholder group, increasing legal protections for end users of electricity and using deep qualitative data in addition to quantitative metrics.

No abstract available.

We are in the midst of an important shift to higher levels of abstraction than virtual machines. Kubernetes aims to simplify the deployment and management of services, including the construction of applications as sets of interacting but independent services. We explain some of the key concepts in Kubernetes and show how they work together to simplify evolution and scaling.

The smartphone has been touted as the technology of the 21st century. Global smartphone adoption rates are growing rapidly, up to over 24% in 2014, with usage increasing 25% in the last year. However, rural areas are often the last places to benefit from these technological trends. Utilizing cellular network registration logs, we explore the adoption and usage of smartphones in an extremely remote community in Indonesia. We found that 16% of the phones in the area were smartphones (compared to between 14--24% in Indonesia). This shows that smartphone adoption in rural Indonesia is similar to the rest of the country. We also explored usage in the network, and found that smartphone users were more likely to text, especially to other smartphone users.

When engaged in ICTD research, it is often simpler to focus efforts on a single specific technology, whether that entails computers for telecenters, mobile phones for data collection, or text messages for public health education. In practice, however, people and organizations use a variety of technologies together, smoothly interweaving them as they navigate their lives. In this paper we analyze the ways in which a health financing organization in Uganda integrates a variety of communications technologies together to achieve reliable communications with their partnering health facilities distributed throughout Southwest Uganda. Based on four years of participant observation, we describe two communication scenarios in this organization to illustrate braided communications at work. We find that stakeholders work together to develop and maintain effective relationships using many different communications channels together in parallel, a combined channel we describe as braided communications. Braided communications have three primary characteristics. Firstly, they use co-existing channels, employing each as best suits a given set of goals. Secondly, they are co-dependent, or co-reinforcing, with strengths of individual channels reinforcing weaknesses of other channels. Finally, they are co-evolving; as available technologies and the ways in which they are used change, the nature of the braided use changes as well.

Over five billion people are active cellular subscribers, spending over a trillion dollars a year on communications. Despite this, hundreds of millions of people are still not connected.

Paper forgery is among the leading causes of corruption in many developing regions. In this paper, we introduce PaperSpeckle, a robust system that leverages the natural randomness property present in paper to generate a fingerprint for any piece of paper. Our goal in developing PaperSpeckle is to build a low-cost paper based authentication mechanism for applications in rural regions such as microfinance, healthcare, land ownership records, supply chain services and education which heavily rely on paper based records. Unlike prior paper fingerprinting techniques that have extracted fingerprints based on the fiber structure of paper, PaperSpeckle uses the texture speckle pattern, a random bright/dark region formation at the microscopic level when light falls on to the paper, to extract a unique fingerprint to identify paper. In PaperSpeckle, we show how to extract a "repeatable" texture speckle pattern of a microscopic region of a paper using low-cost machinery involving paper, pen and a cheap microscope. Using extensive testing on different types of paper, we show that PaperSpeckle can produce a robust repeatable fingerprint even if paper is damaged due to crumpling, printing or scribbling, soaking in water or aging with time.

We believe datacenters can benefit from more focus on per-node efficiency, performance, and predictability, versus the more common focus so far on scalability to a large number of nodes. Improving per-node efficiency decreases costs and fault recovery because fewer nodes are required for the same amount of work. We believe that the use of complex, general-purpose operating systems is a key contributing factor to these inefficiencies.

Many children, especially in the developing world, must share a computer at school. Often, more advanced or aggressive students dominate, leaving others frustrated and disengaged. One promising approach is to provide each student with their own input device, usually a mouse, while sharing a common computer and display. Previous multiple mouse sharing efforts for education have relied on developing custom applications that encourage collaboration --- for example, by requiring that all users click on an icon or option to proceed. Implementing this requires access to application source code, which is unlikely to be available, and would require significant engineering effort to adapt even if it was. To address these limitations, we developed Metamouse. Metamouse only conveys clicks to the application when users have already agreed on a screen location, within a pre-defined tolerance (a novel sharing technique that we call "location-voting") and requires no access to the application source code. We have implemented two versions of location-voting --- one that requires all users to agree ("Consensus"), and another where only a majority is required ("Majority"). To evaluate Metamouse, we conducted a user study with 24 fifth-grade students in a low-income school in Bangalore, India. Our results demonstrate that Metamouse is intuitive, usable and has the potential to outperform other sharing strategies in terms of user engagement, generating discussion, and overall satisfaction. We also show that the Majority approach provides all of these benefits as effectively as Consensus with less frustration for faster users and less embarrassment for slower ones.

Short Messaging Service (SMS) based mobile information services have become increasingly common around the world, especially in emerging regions among users with low-end mobile devices. This paper presents the design and implementation of SMSFind, an SMS-based search system that enables users to obtain extremely concise (one SMS) message of 140 bytes) and appropriate search responses for queries across arbitrary topics in one round of interaction. SMSFind is designed to complement existing SMS-based search services that are either limited in the topics they recognize or involve a human in the loop.

At PODC 2000, the CAP theorem received its first broad audience. Surprisingly for an impossibility result, one important effect has been to free designers to explore a wider range of distributed systems. Designers of wide-area systems, in which network partitions are considered inevitable, know they cannot have both availability and consistency, and thus can now justify weaker consistency. The rise of the "NoSQL" movement ("Not Only SQL") is an expression of this freedom.

Traditional Single Display Groupware (SDG) solutions have been used to create software for developing regions. SDG allows for greater utilization of the limited infrastructure available in such areas. This technology is particularly appropriate in classrooms where groups of children often use educational software on a single computer. However, SDG has faced several challenges working with legacy applications. Our technology, called metamouse, takes a step toward an integrated multi-user application by allowing users to collaborate within unmodified legacy educational software.

Although existing write-ahead logging algorithms scale to conventional database workloads, their communication and synchronization overheads limit their usefulness for modern applications and distributed systems. We revisit write-ahead logging with an eye toward finer-grained concurrency and an increased range of workloads, then remove two core assumptions: that pages are the unit of recovery and that times-tamps (LSNs) should be stored on each page. Recovering individual application-level objects (rather than pages) simplifies the handing of systems with object sizes that differ from the page size. We show how to remove the need for LSNs on the page, which in turn enables DMA or zero-copy I/O for large objects, increases concurrency, and reduces communication between the application, buffer manager and log manager. Our experiments show that the looser coupling significantly reduces the impact of latency among the components. This makes the approach particularly applicable to large scale distributed systems, and enables a "cross pollination" of ideas from distributed systems and transactional storage. However, these advantages come at a cost; segments are incompatible with physiological redo, preventing a number of important optimizations. We show how allocation enables (or prevents) mixing of ARIES pages (and physiological redo) with segments. We present an allocation policy that avoids undesirable interactions that complicate other combinations of ARIES and LSN-free pages, and then present a proof that both approaches and our combination are correct. Many optimizations presented here were proposed in the past. However, we believe this is the first unified approach.

We consider the problem of efficientMAC design for long-distance WiFi-based mesh networks. In such networks it is common to find long propagation delays, the use of directional antennas, and the presence of inter-link interference. Prior work has shown that these characteristics make traditional CSMA-based MACs a poor choice for long-distance mesh networks and this finding has led to several recent research efforts exploring the use of TDMA-based approaches to media access. In this paper we first identify, and then address, several shortcomings of current TDMA-based proposals. First, because they use fixed-length transmission slots, current TDMA-based solutions do not adapt to dynamic variations in traffic load leading to inefficiencies in both throughput and delay. As we show in this paper, the throughput achieved by existing solutions falls far short of the optimal achievable network throughput. Finally, due to the scheduling constraints imposed by inter-link interference, current TDMA-based solutions only apply to bipartite network topologies.

Unintended or unmediated data sharing is a frequent cause of insidious bugs in multithreaded programs. We present a tool called SharC (short for Sharing Checker) that allows a user to write lightweight annotations to declare how they believe objects are being shared between threads in their program. SharC uses a combination of static and dynamic analyses to check that the program conforms to this specification.

Wikis have proven to be a valuable tool for collaboration and content generation on the web. Simple semantics and ease-of-use make wiki systems well suited for meeting many emerging region needs in the areas of education, collaboration and local content generation. Despite their usefulness, current wiki software does not work well in the network environments found in emerging regions. For example, it is common to have long-lasting network partitions due to cost, power and poor connectivity. Network partitions make a traditional centralized wiki architecture unusable due to the unavailability of the central server. Existing solutions towards addressing connectivity problems include web-caching proxies and snapshot distribution. While proxies and snapshots allow wiki data to be read while disconnected, they prevent users from contributing updates back to the wiki.

Rose is a database storage engine for high-throughput replication. It targets seek-limited, write-intensive transaction processing workloads that perform near real-time decision support and analytical processing queries. Rose uses log structured merge (LSM) trees to create full database replicas using purely sequential I/O, allowing it to provide orders of magnitude more write throughput than B-tree based replicas. Also, LSM-trees cannot become fragmented and provide fast, predictable index scans. Rose's write performance relies on replicas' ability to perform writes without looking up old values. LSM-tree lookups have performance comparable to B-tree lookups. If Rose read each value that it updated then its write throughput would also be comparable to a B-tree. Although we target replication, Rose provides high write throughput to any application that updates tuples without reading existing data, such as append-only, streaming and versioning databases. We introduce a page compression format that takes advantage of LSM-tree's sequential, sorted data layout. It increases replication throughput by reducing sequential I/O, and enables efficient tree lookups by supporting small page sizes and doubling as an index of the values it stores. Any scheme that can compress data in a single pass and provide random access to compressed values could be used by Rose. Replication environments have multiple readers but only one writer. This allows Rose to provide atomicity, consistency and isolation to concurrent transactions without resorting to rollback, blocking index requests or interfering with maintenance tasks. Rose avoids random I/O during replication and scans, leaving more I/O capacity for queries than existing systems, and providing scalable, real-time replication of seek-bound workloads. Analytical models and experiments show that Rose provides orders of magnitude greater replication bandwidth over larger databases than conventional techniques.

Despite the increasing number of WiFi-based Long Distance (WiLD) network deployments, there is a lack of understanding of how WiLD networks perform in practice. In this paper, we perform a systematic study to investigate the commonly cited sources of packet loss induced by the wireless channel and by the 802.11 MAC protocol. The channel induced losses that we study are external WiFi, non-WiFi and multipath interference. The protocol induced losses that we study are protocol timeouts and the breakdown of CSMA over WiLD links. Our results are based on measurements performed on two real-world WiLD deployments and a wireless channel emulator. The two deployments allow us to compare measurements across rural and urban settings. The channel emulator allows us to study each source of packet loss in isolation in a controlled environment. Based on our experiments we observe that the presence of external WiFi interference leads to significant amount of packet loss in WiLD links. In addition to identifying the sources of packet loss, we analyze the loss variability across time. We also explore the solution space and propose a range of MAC and network layer adaptation algorithms to mitigate the channel and protocol induced losses. The key lessons from this study were also used in the design of a TDMA based MAC protocol for high performance long distance multihop wireless networks [12].

We present HeapSafe, a tool that uses reference counting to dynamically verify the soundness of manual memory management of C programs. HeapSafe relies on asimple extension to the usual malloc/free memory management API: delayed free scopes during which otherwise dangling references can exist. Porting programs for use with HeapSafe typically requires little effort (on average 0.6% oflines change), adds an average 11% time overhead (84% in the worst case), and increases space usage by an average of 13%. These results are based on portingover half a million lines of C code, including perl where we found sixpreviously unknown bugs.Many existing C programs continue to use unchecked manual memorymanagement. One reason is that programmers fear that moving to garbage collection is too big a risk. We believe that HeapSafe is a practical way toprovide safe memory management for such programs. Since HeapSafe checks existing memory management rather than changing it, programmers need not worrythat HeapSafe will introduce new bugs; and, since HeapSafe does not managememory itself, programmers can choose to deploy their programs without HeapSafe if performance is critical (a simple header file allows HeapSafe programs to compile and run with a regular C compiler). In contrast, we foundthat garbage collection, although faster, had much higher space overhead, and occasionally caused a space-usage explosion that made the program unusable.

The movement to multi-core processors increases the need for simpler, more robust parallel programming models. Atomic sections have been widely recognized for their ease of use. They are simpler and safer to use than manual locking and they increase modularity. But existing proposals have several practical problems, including high overhead and poor interaction with I/O. We present pessimistic atomic sections, a fresh approach that retains many of the advantages of optimistic atomic sections as seen in "transactional memory" without sacrificing performance or compatibility. Pessimistic atomic sections employ the locking mechanisms familiar to programmers while relieving them of most burdens of lock-based programming, including deadlocks. Significantly, pessimistic atomic sections separate correctness from performance: they allow programmers to extract more parallelism via finer-grained locking without fear of introducing bugs. We believe this property is crucial for exploiting multi-core processor designs.We describe a tool, Autolocker, that automatically converts pessimistic atomic sections into standard lock-based code. Autolocker relies extensively on program analysis to determine a correct locking policy free of deadlocks and race conditions. We evaluate the expressiveness of Autolocker by modifying a 50,000 line high-performance web server to use atomic sections while retaining the original locking policy. We analyze Autolocker's performance using microbenchmarks, where Autolocker outperforms software transactional memory by more than a factor of 3.

In this paper we present an analysis of HTTP traffic captured from Internet cafés and kiosks from two different developing countries -- Cambodia and Ghana. This paper has two main contributions. The first contribution is a analysis of the characteristics of the web trace, including the distribution and classification of the web objects requested by the users. We outline notable features of the data set which effect the performance of the web for users in developing regions. Using the trace data, we also perform several simulation analyses of cache performance, including both traditional caching and more novel off-line caching proposals. The second contribution is a set of suggestions on mechanisms to improve the user experience of the web in these regions. These mechanisms include both applications of well-known research techniques as well as offering some less well-studied suggestions based on intermittent connectivity.

Computer-aided learning is fast gaining traction in developing regions as a means to augment classroom instruction. Reasons for using computer-aided learning range from supplementing teacher shortages to starting underprivileged children off in technology, and funding for such initiatives range from state education funds to international agencies and private groups interested in child development. The interaction of children with computers is seen at various levels, from unsupervised self-guided learning at public booths without specific curriculum to highly regulated in-class computer applications with modules designed to go with school curriculum. Such learning is used at various levels from children as young as 5 year-old to high-schoolers. This paper uses field observations of primary school children in India using computer-aided learning modules, and finds patterns by which children who perform better in classroom activities seat themselves in front of computer monitors, and control the mouse, in cases where children are required to share computer resources. We find that in such circumstances, there emerges a pattern of learning, unique to multi-user environments - wherein certain children tend to learn better because of their control of the mouse. This research also shows that while computer aided learning software for children is primarily designed for single-users, the implementation realities of resource-strapped learning environments in developing regions presents a strong case for multi-user design.

We propose a system architecture for real-time hardware speech recognition on low-cost, power-constrained devices. The system is intended to support real-time speech-based user interfaces as part of an effort to bring Information and Communication Technologies (ICTs) to underdeveloped regions of the world.Our system architecture exploits a shared infrastructure model. The computationally intensive task of speech model training and retraining is performed offline by shared servers, while the actual recognition of speech is conducted on low-cost hand-held devices using custom hardware.The recognizer is extremely flexible and can support multiple languages or dialects with speaker-independent recognition. Dynamic loading of speech models is used for changing language grammar and retraining, while reprogramming is used to support evolution of recognition algorithms. The focus on small sets of words (at one time) reduces the complexity, cost and power consumption. We design the speech decoder, the central component of the recognizer, and we validate it via a prototype FPGA implementation. We then use ASIC synthesis to estimate power and size for the design.Our evaluations demonstrate an order of magnitude improvement in power compared with optimized recognition software running on a low-power embedded general-purpose processor of the same technology and of similar capabilities. The synthesis also estimates the area of the design to be about 2.5mm2, showing potential for lower cost. In designing and testing our recognizer we use datasets in both English and Tamil languages.

The C language is among the most widely used in the world, particularly for critical infrastructure software. C programs depend upon macros processed using the C preprocessor, but these macros are difficult to analyze and are often error-prone[4]. Existing tools that analyze and transform C source code have rudimentary support for the preprocessor, leading to obscure error messages and difficulty refactoring. We present a three part solution: (1) a replacement macro language, ASTEC, that addresses the most important important deficiencies of the preprocessor and that eliminates many of the errors it introduces; (2) a translator, MACROSCOPE, that converts existing code into ASTEC semi-automatically; and (3), an ASTEC-aware refactoring tool that handles preprocessor constructs naturally.ASTEC's primary benefits are its analyzability and its refactorability. We present several refactorings that are enabled by ASTEC. Additionally, ASTEC eliminates many of the sources of errors that can plague C preprocessor macros; Ernst et al.[4] estimate that more than 20% of macros may contain errors. In this paper, we describe our translation and refactoring tools and evaluate them on a suite of programs including OpenSSH and the Linux kernel.

Moore's Law and the wave of technologies it enabled have led to tremendous improvements in productivity and the quality of life in the industrialized world. Yet, technology has had almost no effect on the four billion people that make less US$2000/day. In this talk I argue that the decreasing costs of computing and wireless networking make this the right time to spread the benefits of technology, and that the biggest missing piece is a lack of focus on the problems that matter, including health, education, and government. After covering some example applications that have shown very high impact, I take an early look at the research agenda for developing regions. Finally, I examine some of the pragmatic issues required to make progress on these very challenging problems. My goal is to convince high-tech researchers that technology for developing regions is an important and viable research topic.

We propose a distributed on-demand power-management protocol for collecting data in sensor networks. The protocol aims to reduce power consumption while supporting fluctuating demand in the network and provide local routing information and synchronicity without global control. Energy savings are achieved by powering down nodes during idle times identified through dynamic scheduling. We present a real implementation on wireless sensor nodes based on a novel, two-level architecture. We evaluate our approach through measurements and simulation, and show how the protocol allows adaptive scheduling and enables a smooth trade-off between energy savings and latency. An example current measurement shows an energy savings of 83% on an intermediate node.

This paper proposes a neighborhood programming abstraction for sensor networks, wherein a node can identify a subset of nodes around it by a variety of criteria and share state with those nodes. This abstraction allows developers to design distributed algorithms in terms of the neighborhood abstraction itself, instead of decomposing them into component parts such as messaging protocols, data caches, and neighbor lists. In those applications that are already neighborhood-based, this abstraction is shown to facilitate good application design and to reduce algorithmic complexity, inter-component coupling, and total lines of code. The abstraction as defined here has been successfully used to implement several complex applications and is shown to capture the essence of many more existing distributed sensor network algorithms.

We present a technique that masks failures in a cluster to provide high availability and fault-tolerance for long-running, parallelized dataflows. We can use these dataflows to implement a variety of continuous query (CQ) applications that require high-throughput, 24x7 operation. Examples include network monitoring, phone call processing, click-stream processing, and online financial analysis. Our main contribution is a scheme that carefully integrates traditional query processing techniques for partitioned parallelism with the process-pairs approach for high availability. This delicate integration allows us to tolerate failures of portions of a parallel dataflow without sacrificing result quality. Upon failure, our technique provides quick fail-over, and automatically recovers the lost pieces on the fly. This piecemeal recovery provides minimal disruption to the ongoing dataflow computation and improved reliability as compared to the straight-forward application of the process-pairs technique on a per dataflow basis. Thus, our technique provides the high availability necessary for critical CQ applications. Our techniques are encapsulated in a reusable dataflow operator called Flux, an extension of the Exchange that is used to compose parallel dataflows. Encapsulating the fault-tolerance logic into Flux minimizes modifications to existing operator code and relieves the burden on the operator writer of repeatedly implementing and verifying this critical logic. We present experiments illustrating these features with an implementation of Flux in the TelegraphCQ code base [8].

We present nesC, a programming language for networked embedded systems that represent a new design space for application developers. An example of a networked embedded system is a sensor network, which consists of (potentially) thousands of tiny, low-power "motes," each of which execute concurrent, reactive programs that must operate with severe memory and power constraints.nesC's contribution is to support the special needs of this domain by exposing a programming model that incorporates event-driven execution, a flexible concurrency model, and component-oriented application design. Restrictions on the programming model allow the nesC compiler to perform whole-program analyses, including data-race detection (which improves reliability) and aggressive function inlining (which reduces resource consumption).nesC has been used to implement TinyOS, a small operating system for sensor networks, as well as several significant sensor applications. nesC and TinyOS have been adopted by a large number of sensor network research groups, and our experience and evaluation of the language shows that it is effective at supporting the complex, concurrent programming style demanded by this new class of deeply networked systems.

This paper presents Capriccio, a scalable thread package for use with high-concurrency servers. While recent work has advocated event-based systems, we believe that thread-based systems can provide a simpler programming model that achieves equivalent or superior performance.By implementing Capriccio as a user-level thread package, we have decoupled the thread package implementation from the underlying operating system. As a result, we can take advantage of cooperative threading, new asynchronous I/O mechanisms, and compiler support. Using this approach, we are able to provide three key features: (1) scalability to 100,000 threads, (2) efficient stack management, and (3) resource-aware scheduling.We introduce linked stack management, which minimizes the amount of wasted stack space by providing safe, small, and non-contiguous stacks that can grow or shrink at run time. A compiler analysis makes our stack implementation efficient and sound. We also present resource-aware scheduling, which allows thread scheduling and admission control to adapt to the system's current resource usage. This technique uses a blocking graph that is automatically derived from the application to describe the flow of control between blocking points in a cooperative thread package. We have applied our techniques to the Apache 2.0.44 web server, demonstrating that we can achieve high performance and scalability despite using a simple threaded programming model.

Despite traditional web caching techniques, redundant data is often transferred over HTTP links. These redundant transfers result from both resource modification and aliasing. Resource modification causes the data represented by a single URI to change; often, in transferring the new data, some old data is retransmitted. Aliasing, in contrast, occurs when the same data is named by multiple URIs, often in the context of dynamic or advertising content. Traditional web caching techniques index data by its name and thus often fail to recognize and take advantage of aliasing.Despite traditional web caching techniques, redundant data is often transferred over HTTP links. These redundant transfers result from both resource modification and aliasing. Resource modification causes the data represented by a single URI to change; often, in transferring the new data, some old data is retransmitted. Aliasing, in contrast, occurs when the same data is named by multiple URIs, often in the context of dynamic or advertising content. Traditional web caching techniques index data by its name and thus often fail to recognize and take advantage of aliasing.

Traditional problem determination techniques rely on static dependency models that are difficult to generate accurately in today's large, distributed, and dynamic application environments such as e-commerce systems. We present a dynamic analysis methodology that automates problem determination in these environments by 1) coarse-grained tagging of numerous real client requests as they travel through the system and 2) using data mining techniques to correlate the believed failures and successes of these requests to determine which components are most likely to be at fault. To validate our methodology, we have implemented Pinpoint, a framework for root cause analysis on the J2EE platform that requires no knowledge of the application components. Pinpoint consists of three parts: a communications layer that traces client requests, a failure detector that uses traffic-sniffing and middleware instrumentation, and a data analysis engine. We evaluate Pinpoint by injecting faults into various application components and show that Pinpoint identifies the faulty components with high accuracy and produces few false-positives.

We propose a new connection management architecture for clustered Internet services called active connection management (ACM) to improve the availability, quality of service, and manageability of Internet services. ACM extends the API of load-balancing switches to include application-level primitives. These primitives enable Internet services to manage load-balancing switches dynamically to control how client connections are mapped to physical resources as they enter the cluster. ACM provides several properties ideal for Internet services over static configuration. First, ACM increases availability through automated configuration, rolling reboots, and reduced server failure detection and recovery time. Second, ACM provides better load conditioning by enabling dynamic allocation of front-end resources and enabling more control over graceful degradation. Third, it provides better manageability by automating configuration, reducing human errors and improving scalability. We present a design, implementation, and evaluation of an ACM system, called COMICS (COnnection Manager for Internet-Centric Services), that enables services to actively control how connections are mapped to servers. We believe that ACM primitives should be implemented into future switches and be utilized by application servers to build more robust Internet service platforms.

We propose a new design for highly concurrent Internet services, which we call the staged event-driven architecture (SEDA). SEDA is intended to support massive concurrency demands and simplify the construction of well-conditioned services. In SEDA, applications consist of a network of event-driven stages connected by explicit queues. This architecture allows services to be well-conditioned to load, preventing resources from being overcommitted when demand exceeds service capacity. SEDA makes use of a set of dynamic resource controllers to keep stages within their operating regime despite large fluctuations in load. We describe several control mechanisms for automatic tuning and load conditioning, including thread pool sizing, event batching, and adaptive load shedding. We present the SEDA design and an implementation of an Internet services platform based on this architecture. We evaluate the use of SEDA through two applications: a high-performance HTTP server and a packet router for the Gnutella peer-to-peer file sharing network. These results show that SEDA applications exhibit higher performance than traditional service designs, and are robust to huge variations in load.

Although IP multicast is an effective network primitive for best-effort, large-scale, multi-point communication, many multicast applications such as shared whiteboards, multi-player games and software distribution require reliable data delivery. Building services like reliable sequenced delivery on top of IP multicast has proven to be a hard problem. The enormous extent of network and end-system heterogeneity in multipoint communication exacerbates the design of scalable end-to-end reliable multicast protocols. In this paper, we propose a radical departure from the traditional end-to-end model for reliable multicast and instead propose a hybrid approach that leverages the successes of unicast reliability protocols such as TCP while retaining the efficiency of IP multicast for multi-point data delivery. Our approach splits a large heterogeneous reliable multicast session into a number of multicast data groups of co-located homogeneous participants. A collection of application-aware agents-reliable multicast proxies (RMX)-organizes these data groups into a spanning tree using an overlay network of TCP connections. Sources transmit data to their local group, and the RMX in that group forwards the data towards the rest of the data groups. RMX use detailed knowledge of application semantics to adapt to the effects of heterogeneity in the environment. To demonstrate the efficacy of our architecture, we have built a prototype implementation that can be customized for different kinds of applications.

The proliferation of broadband access, enhancements in production and encoding technologies and increasing consumer demand for rich, high bandwidth content are fueling the need for reliable and cost-effective streaming media delivery networks that ensure a high quality end-user experience. These networks provide a scalable infrastructure for both live and on-demand streaming media. In his keynote, Dr. Brewer will address specific IP infrastructure needs for streaming media delivery; the importance of caching, multicast and bandwidth provisioning; enhancing media delivery with network edge services; and putting it all together to create a high-performance, reliable streaming media delivery network.

Current distributed systems, even the ones that work, tend to be very fragile: they are hard to keep up, hard to manage, hard to grow, hard to evolve, and hard to program. In this talk, I look at several issues in an attempt to clean up the way we think about these systems. These issues include the fault model, high availability, graceful degradation, data consistency, evolution, composition, and autonomy.

IP Multicast has proven to be an effective communication primitive for best effort, large-scale, multi-point audio/video conferencing applications. While the best-effort transport of real-time digital audio/video is a relatively straightforward and well understood problem, many other applications like multicast-based shared whiteboards and shared text editors are more challenging to design because their underlying media require reliable transport, i.e., a "reliable multicast" protocol. The design of scalable end-to-end reliable multicast protocols has unfortunately proven to be an especially hard problem, exacerbated by the enormous degree of network and system heterogeneity present in the Internet. In this paper, we propose to tackle the heterogeneity problem with a hybrid model for reliable multicast that relies in part on end-to-end loss recovery mechanisms and in part on intelligent and application-aware adaptation carried out within the network. In our framework, application-aware agents -- or proxies -- use detailed knowledge of application semantics to hide the effects of heterogeneity from the rest of the system. We present a general architecture for proxy-based reliable multicast called the Reliable Multicast proXy (RMX) model and describe a prototype implementation of an RMX for a shared whiteboard application for hand-held PDAs.

We demonstrate that high-level file system events exhibit self-similar behaviour, but only for short-term time scales of approximately under a day. We do so through the analysis of four sets of traces that span time scales of milliseconds through months, and that differ in the trace collection method, the filesystems being traced, and the chronological times of the tracing. Two sets of detailed, short-term file system trace data are analyzed; both are shown to have self-similar like behaviour, with consistent Hurst parameters (a measure of self-similarity) for all file system traffic as well as individual classes of file system events. Long-term file system trace data is then analyzed, and we discover that the traces' high variability and self-similar behaviour does not persist across time scales of days, weeks, and months. Using the short-term trace data, we show that sources of file system traffic exhibit ON/OFF source behaviour, which is characterized by highly variably lengthed bursts of activity, followed by similarly variably lengthed periods of inactivity. This ON/OFF behaviour is used to motivate a simple technique for synthesizing a stream of events that exhibit the same self-similar short-term behaviour as was observed in the file system traces.

Inktomi provides the back-end for several well-known search engines, including Wired's HotBot and Microsoft's MS Start page. The services are supported by a highly available cluster with more than 300 CPUs and several hundred disks.

We identifit three fundamental requirements for scalable network services: incremental scalability and oveflow growth provisioning, 24x7 availability through fault masking, and costeffectiveness.We argue that clusters of commodity workstations interconnected by a high-speed SAN are exceptionally well-suited to meeting these challenges for Internet-server workloads, provided the software infrastructure for managing partial failures and administering a large cluster does not have to be reinvented for each new service.To this end, we propose a general, layered architecture for building cluster-based scalable network services that encapsulates the above requirements for reuse, and a service-programming model based on composable workers thatpe$onn transformation, aggregation, caching, i and customization (TACC) of Internet content.For both performance and implementation simplicity, the architecture and TACC programming model exploit BASE, a weaker-than-ACID data semantics that results from trading consistency for availability and relying on sof state for robustness in failure management., Our ,qychitecture can be used as an "off the shelf * irtfrastructural platfonn for creating new network services, allowing authors to focus on the "content" of the service {by composing TACC building blocks) rather than its implementation.We discuss two real implemeritations of services based on this architecture: TranSend, a Web distillation proxy deployed to the UC Berkeley dialup IP population, and HotBot, the commercial implementation of the Inktomi search engine.We present detailed measurements of TranSend's performance based on substantial client traces, as well as anecdotal evidence from the TranSend and HotBot experience, to support the claims made for the architecture.

lligent services. Our extensions are orthogonal in that they provide an interface to a service, which complements the Web browsing experience but is independent of the content of any particular site. We base our experiments on the TranSend service at UC Berkeley, which performs lossy compression on inline images to accelerate dialup Web access for a community of 25,000 subscribers. The service keeps a separate "preferences profile" for each user, which allows each user to vary the aggressiveness of lossy compression, selectively turn off the service for certain pages, and select the type of interface provided for refinement of degraded (lossily compressed) content. We are exploring three technologies for implementing the TranSend service interface: HTML decoration, Java, and JavaS- Server Client Browser Client Browser Proxy Server Server cript. The accompanying video demonstrates prototypes of all three mechanisms. We no

The explosive growth of the Internet and the proliferation of smart cellular phones and handheld wireless devices is widening an already large gap between Internet clients. Clients vary in their hardware resources, software sophistication, and quality of connectivity, yet server support for client variation ranges from relatively poor to none at all. In this paper we introduce some design principles that we believe are fundamental to providing "meaningful" Internet access for the entire range of clients. In particular, we show how to perform on-demand datatype-specific lossy compression on semantically typed data, tailoring content to the specific constraints of the client. We instantiate our design principles in a proxy architecture that further exploits typed data to enable application-level management of scarce network resources. Our proxy architecture generalizes previous work addressing all three aspects of client variation by applying well-understood techniques in a novel way, resulting in quantitatively better end-to-end performance, higher quality display output, and new capabilities for low-end clients.

In this paper we describe a new algorithm for maintaining a balanced search tree on a message-passing MIMD architecture; the algorithm is particularly well suited for implementation on a small number of processors. We introduce a (2/sup B-2/, 2/sup B/) search tree that uses a bidirectional ring of O(log n) processors to store n entries. Update operations use a bottom-up node-splitting scheme, which performs significantly better than top-down search tree algorithms. The bottom-up algorithm requires many fewer messages and results in less blocking due to synchronization than top-down algorithms. Additionally, for a given cost ratio of computation to communication the value of B may be varied to maximize performance. Implementations on a parallel-architecture simulator are described.

We develop the use of statistical modeling for portable high-level optimizations such as data layout and algorithm selection. We build the models automatically from profiling information, which ensures robust and accurate models that reflect all aspects of the target platform.

Article Remote queues: exposing message queues for optimization and atomicity Share on Authors: Eric A. Brewer UC Berkeley UC BerkeleyView Profile , Frederic T. Chong MIT MITView Profile , Lok T. Liu UC Berkeley UC BerkeleyView Profile , Shamik D. Sharma University of Maryland University of MarylandView Profile , John D. Kubiatowicz MIT MITView Profile Authors Info & Claims SPAA '95: Proceedings of the seventh annual ACM symposium on Parallel algorithms and architecturesJuly 1995 Pages 42–53https://doi.org/10.1145/215399.215416Online:20 July 1995Publication History 50citation349DownloadsMetricsTotal Citations50Total Downloads349Last 12 Months10Last 6 weeks2 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

Recent work has shown marry advantages to randomly wired expander-based networks.Unfortunately, the win"ng complexity of such networks becomes physically problematic as they become large.This paper introduces a technique for sca3ing expanders that avoids this wirr"ng complexity.Specifically, we make the following contributions:1. We introduce hierarchical expanders, which use a method of scaling small expanders to larger ones while ma"nta"m"ng practical physical construction.We present an example of such a scalable network, called the metabutterjly, which is scaled from the randomJy wired multibutterfly.2. We present a proof that we can scale any (cY,/?, M, N)exprmder with dbf > 1 into an (a',,@, kM, kN) -expander with probability at least 1 -2e-a M, where a' = ~2e~~4= arrd/3' =/3-2.3. Wepresent empirical evidence that the performance and fault tolerance of metabuttertlies equals that of traditionid randomly wired multibutterflies, despite the greatly simplified wiring of the metabuttertly

PROTEUS is a high-performance simulator for MIMD multiprocessors. It is fast, accurate, and flexible: it is one to two orders of magnitude faster than comparable simulators, it can reproduce results from real multiprocessors, and it is easily configured to simulate a wide range of architectures. PROTEUS provides a modular structure that simplifies customization and independent replacement of parts of architecture. There are typically multiple implementations of each module that provide different combinations of accuracy and performance; users pay for accuracy only when and where they need it. Finally, PROTEUS provides repeatability, nonintrusive monitoring and debugging, and integrated graphical output, which result in a development environment superior to those available on real multiprocessors.