The growing use of computing and proliferation of computing devices requires a holistic focus on sustainability as the environmental impacts of computing technologies go beyond their energy consumption.Environmental impacts span all stages of the lifecycle -manufacturing, operation, and disposal.A sustainability mindset must permeate all organizations involved in design, manufacturing, operation, and disposal/recycling of computational devices.This panel will discuss current and new research on sustainability in computing that spans the full lifecycle, all layers of the computing stack and across the computing spectrum from edge to cloud.The panel will also discuss potential crossdisciplinary approaches to sustainable computing and new notions and metrics to quantify sustainability.

The growing use of computing and proliferation of computing devices requires a holistic focus on sustainability as the environmental impacts of computing technologies go beyond their energy consumption. Environmental impacts span all stages of the lifecycle - manufacturing, operation, and disposal. A sustainability mindset must permeate all organizations involved in design, manufacturing, operation, and disposal/recycling of computational devices. This panel will discuss current and new research on sustainability in computing that spans the full lifecycle, all layers of the computing stack and across the computing spectrum from edge to cloud. The panel will also discuss potential cross-disciplinary approaches to sustainable computing and new notions and metrics to quantify sustainability.

INSIGHT, an innovate graduate STEM Fellowship Program integrates sensor technology and computer science within in a K-12 standards-based science, technology, and engineering curricula. Graduate STEM Fellows are teamed with science, technology, and physical education teachers for two years to carry out hands-on classroom activities utilizing technology and engineering practice with a focus on the use of sensors, computing, and information technology aligned with K-12 state curriculum standards. One of the projects main goals is the establishment of sensor, computing, and information technology as a foundational high school skill by accelerating the integration of sensor technology content into K-12 classrooms. This project encourages participation in engineering and technology from a wider, more diverse group of students from rural Kansas. This paper shares detailed examples of summer institute and academic-year K-12 activities that have been successful. It also provides a preliminary assessment of the project.

With the increased deployment of pervasive systems, there has been an explosive growth in the number of applications being developed for such systems. Distributed applications typically depend on the underlying middleware infrastructure to provide services to perform their tasks. Many applications rely on a service which can detect the termination of a distributed activity being performed by a set of entities. Existing algorithms for termination detection are based on the layering paradigm wherein the algorithm can monitor application level communication. Pervasive applications, however, may not be structured as strictly layered systems. This paper proposes algorithms for termination detection of distributed applications in pervasive systems. We propose two algorithms for this problem, and show that each performs better than the other under certain conditions. Subsequently, we propose an hybrid algorithm which combines the features of the two algorithms and provides performance comparable to the better of the two algorithms under different conditions.

InDiGO framework provides an infrastructure which allows design of generic but customizable algorithms encapsulated as middleware services and provides tools to customize such algorithms for specific applications. Such customization allows one to optimize algorithms by removing communication which is redundant in the context of a specific application. Information necessary for optimization is derived by running queries of interest on the application abstraction. Each new query requires a new algorithm to be written that would operate on the application abstraction to give a yes or no answer. In this paper, we describe a different approach to answer the queries. It uses model checking and is fully automated. It also allows to answer the queries precisely as well as to verify more general properties. We present experimental results to demonstrate the optimizations when our infrastructure is utilized.

The problem of synchronization can be formulated in terms of rules constraining the occupancy of regions in different processes, where a region is a block of code whose execution may require synchronization. In this region synchronization problem, the region occupancy rules (or the synchronization policy) can be specified using a global invariant. The task of a region synchronization algorithm is to constrain the region entry and exit of processes in a manner that satisfies the global invariant. This paper proposes efficient algorithms for region synchronization in message passing systems. In particular, we propose extension of two existing mutual exclusion algorithms to solve the region synchronization problem. We show that our algorithms are message efficient and satisfy the property of absence of unnecessary synchronization. We show that many existing synchronization problems such as group mutual exclusion, readers/writers, committee coordination, and barrier can be specified as instances of the region synchronization problem, and hence our algorithms can be used to solve a large class of problems.

Many frameworks have been proposed which provide distributed algorithms encapsulated as middleware services to simplify application design. The developers of such algorithms are faced with two opposing forces. One is to design generic algorithms that are reusable in a large number of applications. Efficiency considerations, on the other hand, force the algorithms to be customized to specific operational contexts. This problem is often attacked by simply re-implementing all or large portions of an algorithm. The goals of this project are to (a) Develop techniques to design distributed algorithms amenable to customization, (b) Develop infrastructure to analyze applications and the target platform specifications to determine when customization can take place, (c) Develop tools to perform the necessary code transformation and compositions to carry out the identified optimizations in the algorithms. We are pursuing a number of different approaches to achieve these goals. We have developed two frameworks, FRAMES and InDiGO, which provides tools and techniques to perform optimization following two different approaches. We have performed experimental studies to demonstrate the advantages of our infrastructure. Another approach based on proof-based optimization is also being pursued. This paper highlights the results from these efforts and discuss our future work plans to apply these techniques to distributed sensor network middleware.

The developers of distributed algorithms are faced with two opposing forces. One is to design generic algorithms that are reusable in a large number of applications. Efficiency considerations, on the other hand, force the algorithms to be customized to specific operational contexts. This problem is often attacked by simply re-implementing all or large portions of an algorithm. This paper proposes InDiGO, an infrastructure which allows design of generic but customizable algorithms and provides tools to customize such algorithms for specific applications. InDiGO provides the following capabilities: (a) Tools to generate intermediate representations of an application which can be leveraged for analysis, (b) Mechanisms to allow developers to design customizable algorithms by exposing design knowledge in terms of configurable options, and (c) An optimization engine to analyze an application to derive the information necessary optimize the algorithms. We perform three types of optimizations: static, dynamic and physical topology-based optimization. We present experimental results to demonstrate the advantages of our infrastructure.

The stringent performance requirements of distributed realtime embedded systems often require highly optimized implementations of middleware services. Performing such optimizations manually can be tedious and error-prone. This paper proposes a model-driven approach to generate customized implementations of event ordering services in the context of component based systems. Our approach is accompanied by a number of tools to automate the customization. Given an application App, an event ordering service Order and a middleware platform P, we provide tools to analyze high-level specifications of App to extract information relevant to event ordering and to use the extracted application information to obtain a customized service, Order(App), with respect to the application usage.

An important requirement of pervasive applications is that of data collection, aggregation and dissemination. Event communication middleware based on the publish/subscribe paradigm has been used extensively to address these data flow requirements. In addition to the data flow, the designer of a system may also want to regulate the actions performed by the components in order to implement some constraints and policies. For example, the designer may want to ensure that actions performed a set of components on receiving an event notification are triggered in a specific sequence. In this paper, we propose a framework to implement such constraints by regulating the flow of events in the middleware. Since components perform actions on receiving events, by controlling the notifications delivered to the components and the sequence in which they are delivered, the order in which actions are performed in the application can be controlled. We have implemented the framework in the context of two event services, one in C++ and another in Java. We give several examples demonstrating the use of the proposed approach.

Real-time concurrent systems typically involve a large number of components interacting with one another in complex ways. In such systems, proper and often complex and elaborate resource access policies must be incorporated to eliminate undesirable executions and to ensure maximum possible concurrency. In this paper, we present a technique for priority inversion control when using such complex resource access policies. We present a systematic approach to design resource access control code based on a formal development methodology called the global invariant approach, along with appropriate priority inversion control code. Our solution relies only on mutex locks with priority inversion control, which are found in many real-time operating systems, and priority-based binary semaphores; therefore, our solution can be implemented on existing infrastructures. We present an implementation of our solution on VxWorks.

To satisfy the stringent QoS requirements of distributed real-time embedded (DRE) systems, middleware services customized to the specific needs of the application may be needed. This problem is often attacked by reimplementing all or large portions of an existing middleware service, which can be a time-consuming and an error prone task. In this paper, we propose a model-driven approach for middleware customization. To enable this approach, we propose event communication framework (ECF), a customizable middleware framework which provides a number of different options for implementing various features of event communication. To determine when to exercise each option, we have performed experiments to identify the application contexts in which each ECF mechanism performs better than the others. Heuristics from these experiments have been incorporated into algorithms which analyze high-level specifications of application scenarios to identify where ECF customizations can be applied. We provide configuration tools that generate customized push paths for event notifications using a combination of code synthesis, weaving and transformation techniques. We have applied our approach to the application scenarios in the Boeing BoldStroke system.

With the advances in processor and memory technology, sensor nodes are likely to be widely deployed leading to creation of sensor networks involving a large number of sensors for monitoring and tracking data. In this paper, we study the problem of rate-based data collection and routing in the context of sensor networks. We consider networks wherein data sources are sampling/collecting data and making it available to potential consumers. Consumers may require data at rates that may vary for each consumer. The problem studied is that of constructing a data distribution tree to efficiently disseminate data at the required rate to each consumer. We first propose an algorithm based on breadth-first tree construction which operates in two phases. The first phase constructs a breadth first tree (by ignoring the rates) and the second phase assigns rates to the tree edges. Subsequently, we present a more efficient algorithm that constructs the tree in a single phase taking rates into account. We also study a variation of the problem taking into consideration weights of the edges. The algorithms have been evaluated using discrete event simulation and we present experimental results comparing the performance of the algorithms.

The ant systems optimization approach is a new method of solving combinatorial optimization problems. It was originally introduced as a metaheuristic approach for the well-known traveling salesman problem. But it was subsequently shown to be an equally effective algorithm for solving other optimization problems. This article supplies more results for an extended ant colony algorithm, which can be used to compute a minimum cost Steiner tree from a graph. In each pass of the proposed algorithm, ants are placed at the terminal nodes of the Steiner tree to be computed. They are then allowed to move towards one another, along the edges of the graph, until they merge into a single entity. In this process, the paths taken by the ants define a Steiner tree. Edges receive reinforcement in the form of pheromone deposits along the paths taken by the ant, that is based on the quality of the Steiner tree produced. Pheromones eventually accrue most along better edges. As a result, after several iterations, a good Steiner tree can be extracted from the deposit. The algorithm can easily be used in several practical applications.

Designing protocols to support collaborative applications is a non-trivial task that must be aided with design methodologies and middleware support. Support for multicasting is an important requirement in collaborative applications and several multicast frameworks supporting different ordering semantics such as FIFO, causal and total ordering have been studied. In this paper, we study the ordering requirements imposed by the modular, compositional structure of a protocol on the underlying multicast communication service (MCS). Collaborative protocols often consist of multiple functions, and techniques for designing multifunction protocols can be used for their development. The modular structure of such multifunction protocols may impose certain ordering requirements on the underlying MCS. We propose a scheme that allows a protocol to specify its ordering requirements and a technique to implement these requirements using an underlying MCS. We show that protocol design and composition is simplified if the messages are delivered in the application-specified order. We also show that the underlying MCS can exploit the structured communication pattern imposed by the modular structure of a protocol to improve the performance.

We propose the notion of invariant consistency that allows programmers to specify inter-process ordering requirements. In our approach, we allow a programmer to label a program and provide an ordering specification. In particular, we associate a counter count/sub l/ with each label l that counts the number of times the operation labeled l has been executed. The ordering specification is given by an invariant on these counters.

The development of correct synchronization code for distributed programs is a challenging task. In this paper, we propose an aspect oriented technique for developing synchronization code for message passing systems. Our approach is to factor out synchronization as a separate aspect, synthesize synchronization code and then compose it with the functional code. Specifically, we allow the designer of an application to first design the functional code. The designer can then annotate the functional code with regions and specify a high-level global specifying the synchronization policy. A synchronization policy essentially gives the occupancy rules for the various regions. The solution to this problem, which we term the region synchronization problem, involves deriving a set of rules for entering and exiting each region. We provide a systematic invariant into a message passing algorithm for a point-to-point message passing system. We show that many existing synchronization problems can be specified as instances of the region synchronization problem. Hence, our algorithms can be used to solve a large class of synchronization problems.

The service specification ss(P) of a protocol P defines the services provided by the protocol and its protocol specification ps(P) specifies the rules of message exchange to ensure the service. Protocol composition has been advocated as an attractive way to design complex protocols. Several techniques have been studied for composition of protocol specifications. In these techniques, to combine component protocols P and and to design R, ps(P) and ps(and) are first combined to obtain ps(R) and then inference rules are used to derive ss(R). In this paper, we explore an alternative strategy in which we allow composition to be specified at the service specification level (that is, ss(P) and ss(Q) are first combined to obtain ss(R)). Given ss(R), we provide an algorithm to mechanically combine ps(P) and ps(Q) to generate ps(R) such that ps(R) satisfies ss(R). We show that analysis of ss(R) is sufficient to ensure that ps(R) satisfies certain safety and liveness properties. This results in efficient validation as state space of ss(R) is typically significantly smaller than that of ps(R).

With the recent advances in communication technology and the availability of powerful desktop computers, networking has gained popularity and many applications are being moved onto the Internet. To ease the development of distributed applications, software support to facilitate coordination and communication is needed. The paper describes an object oriented system for structured design and development of distributed applications. The basic system consists of a set of multithreaded servers, one server for each site in the network, which provide some basic communication facilities. The system has been developed using JAVA as the programming language. We use the software support provided by this basic system to define commonly used patterns of interaction in distributed applications. We also identify several different techniques for systematic composition of patterns to develop different applications. We illustrate the use of our system by defining some patterns and using them to build a sample application.

Leader election is a fundamental problem in distributed computing and has a number of applications. This paper studies the problem of leader election in complete asynchronous networks. We present a message-optimal protocol that requires $O(N\log{N})$ messages and $O(N/\log{N})$ time, where N is the number of nodes in the system. The time complexity of this protocol is a significant improvement over currently known protocols for this problem. We also give a family of protocols with message and time complexities $O(N k)$ and $O(N/k)$, respectively, where $\log{N} \leq k \leq N$. Many problems such as spanning-tree construction and computing a global function are equivalent to leader election in terms of their message and time complexities, and therefore our result improves the time complexity of these problems as well.

We propose a compositional technique to design multifunction protocols. The technique involves first designing the protocols performing the various functions separately and then combining them using a set of constraints. The constraints are used to specify the interactions between the component protocols. The interactions, for example, specify when a function has to be performed and whether two functions can be performed concurrently or not. We illustrate the use of our technique by designing several protocols. We give sufficient conditions to infer properties of the composite protocol from those of the component protocols.

The paper presents a functional view of end-system protocol implementations whereby the protocol is decomposed into multiple functions, each causing a change in the protocol state. This view makes the interactions and the relationships among the various functional modules explicit. In terms of this view, currently prevalent architectural optimizations for performance improvement (such as 'parallel executions' and 'integrated layer processing') can be easily described as a set of control flow relationships among modules. If a protocol implementation is analyzed using our functional model, the possible architectural optimizations in the protocol can be easily identified and implemented without violating correctness. Thus, our approach can be used to optimize existing implementations by casting the underlying protocols in our framework, and it is particularly useful in developing implementations for new protocols.

Randomized selection algorithms on k-dimensional mesh-connected computers with multiple broad-casting are proposed in this paper. We first show that a leader can be elected in O(log N) time on any k-dimensional mesh-connected computers with multiple broadcasting of size N. We then show that we can find the p-th smallest element among a data set of size N in O((logN + k + N1/k(k + 1))) log N) expected time using a regular N1/k ×…×N1/kk-dimensional mesh and in O((log N + k2N1/k2k)) log N) expected time using an irregular N(2k-1k + 1)/(k2k)×N(2k-2k + 1)/(k2k×…×N(k + 1)/(k2kk-dimensional mesh. This leads to a selection algorithm which runs in O((log N)2) expected time on a regular ((log N/log log N)1/2)-dimensional mesh or on an irregular (log log N)-dimensional mesh each with N processors. To our best knowledge, this is the first polylogarithmic selection algorithm on meshes with multiple broadcasting.

We study the problem of leader election in the presence of intermittent link failures. We assume that up to N/2-1 links incident on each node may fail during the execution of the protocol. We present a message optimal algorithm with message complexity O(N/sup 2/).

No abstract available.

We study the problem of placement of replicas of a database (or a shared resource) in a dynamic network. We develop a set of protocols that maintain a path from each site to its nearest replica such that the cost of accessing the nearest replica is below a certain threshold. The protocols determine the number of replicas needed and the sites where these replicas must be placed. This is useful in read-intensive applications which impose time constraints on read operations. The protocols reconfigure the placement in response to changes in link costs. This may involve recomputing paths and relocating, adding or removing replicas.>

The complexity of communication protocols has led to compositional techniques to design and verify protocols. We propose a framework for sequential composition of protocols. We identify two types of interactions, ordering and inhibition, required to specify such compositions. By describing these interactions separately, our framework enhances the applicability to the technique to a larger class of protocols. The technique facilitates modular design and verification. We illustrate the use of our technique by deriving several protocols.>

No abstract available.

We propose a compositional technique for designing protocols. The technique involves specifying constraints between the events of the component protocols. A constraint may either require synchronization between certain events of the component protocols or may require inhibiting an event in one protocol on the occurrence of an event in another component protocol. We find both types of constraints useful in composing protocols. We demonstrate the applicability of the technique by deriving several protocols. The technique facilitates modular design and verification. Our technique, in conjunction with the sequential composition technique, can be used to design complex protocols.

Connectivity among a set of user entities in a network can be provided by a network level abstraction of an acyclic graph (or spanning tree). The authors discuss the reconfiguration of a graph in the presence of failures of network nodes. A reconfiguration manifests itself as a graph fragmentation problem, whereby two or more disjoint subgraphs attempt to connect with one another to form a composite graph. Fragment interconnection requires contention resolution between fragments to avoid cycles. Two classes of contention resolution algorithms applicable for environments with a potentially large number of fragments are presented. They are based on preestablished ranking among fragments and random arbitration among fragments. The algorithms have been evaluated by simulation and compared. The algorithms are useful in supporting data multicasting across workstations and distributed computations involving data on different machines.>

The complexity of designing distributed protocols has led to compositional techniques for designing and verifying protocols. The author proposes a technique based on the notion of parallel composition of protocols. It allows the component protocols to share messages and variables. The composite protocol is an interleaved execution of the component protocols with the constraint that they be synchronized at events updating shared variables or sending/receiving shared messages. All invariants of the component protocols are preserved in the composite protocol. The technique allows modular design and verification of protocols. It can be viewed as an inverse of the projection method for verifying protocols.>

This paper presents protocols for leader election in complete networks. The protocols are message optimal and their time complexities are a significant improvement over currently known protocols for this problem. For asynchronous complete networks with sense of direction, we propose a protocol which requires O(N) messages and O(log N) time. For asynchronous complete network without sense of direction, we show that Ω(N/log N) is a lower bound on the time complexity of any message optimal election protocol and we present a family of protocols which requires O(Nk) messages and O(N/k) time, log N ≤ k ≤ N. Our results also improve the time complexity of several other related problems such as spanning tree construction, computing a global function, etc.

An efficient protocol for leader election in an asynchronous complete network is presented. The time complexity of the protocol is better than the currently known protocols for this problem. A message optimal protocol is presented that requires O(N/log N) time, where N is the number of nodes in the network. Also given is family of protocols with message and time complexities O(Nk) and O(N/k) respectively, where log N>

A formalism for comparing the average execution time of distributed protocols is provided. The comparisons are made independently of the properties of the network on which the protocols are executed. The formalism takes into account computation time, the time to transfer information, the time spent by a site waiting to synchronize with other sites, and the overlap among them. A framework in which the information transfer and synchronization requirements of a protocol are separately and explicitly specified is developed. A knowledge formalism is used to specify the protocol's specification requirements. Transformations on protocols which may change the synchronization structure, the information transferred, or the amount of local computation are defined. It is shown that, if a sequence of such transformations can be applied to a protocol to obtain another protocol, the final protocol runs at least as fast as the initial. Two notions of comparison, containment and reducibility, are given, and their properties are explored. Several protocols, including those for atomic commitment and snapshot recording, are analyzed to illustrate the technique.>