Andrea W. Richa - US grants

The research component of this project focuses on two fundamental
distributed network problems. The first problem is that of devising
an efficient method for accessing shared information (objects) in a
distributed scenario (Problem A); the second problem is probably the
most fundamental problem that arises in any communication network,
namely that of devising efficient point-to-point routing protocols
(Problem B).

More specifically, the PI proposes to accomplish the following
research items:

- to deliver solutions to Problem A in fixed-connection networks,
taking into account several important network parameters -- such as
link congestion, dynamic link costs, and multiple representations of
objects -- and in cellular and ad-hoc wireless mobile scenarios.

- to deliver solutions to Problem B in conjunction with Problem A,
with the aim of minimizing the cost of accessing an object.

- to deliver solutions to Problem B on its own, in wireless mobile and
fixed-connection scenarios.

Not surprisingly, the problem of accessing shared objects and the
routing problem in distributed environments are strongly related in
many ways. For example, they are directly related in dynamic
scenarios. Therefore the PI anticipates that studying these two
problems together in mobile scenarios will help devise better
solutions for both problems.

Computer Science (31), Mathematical Sciences (21), Computer Engineering (32), Engineering Technology (58) This Computer Science, Engineering, and Mathematics, Scholarship (CSEMS) Program is providing scholarships and an infrastructure that will enable academically talented, financially disadvantaged students to maintain full-time enrollment and achieve degree completion in the fields of engineering, engineering technology, mathematics, computer science, and computer technology. As the project administrator, the university's existing SUMS Institute is coordinating efforts between the Department of Mathematics and the College of Engineering and Applied Sciences to: 1) recruit and select program students; 2) provide activities designed to support the students through degree achievement; and 3) prepare the students for future employment and/or higher education. The project expects to increase the enrollment and the graduation of students in science, engineering, mathematics, and other technical fields from groups that have traditionally been underrepresented. The CSEMS Program is expanding and enhancing the continuum of services available to students of diverse gender, ethnic, social, and economic backgrounds, and is evidence of the university's commitment to providing a high quality education for all students.

The Computer Science, Engineering, and Mathematics, Scholarship Program at Arizona State University provides scholarships and a support infrastructure that enables academically talented, financially disadvantaged lower division students to maintain fulltime enrollment and progress toward degree completion into upper division status where attrition rates are reduced. Targeted fields include engineering, engineering technology, mathematics, computer science, and computer technology. The program offers a supported summer bridge program for recruited high school seniors (entering freshman) across the state and a variety of carefully designed activities to enhance learning and career opportunities. The program also expands and enhances the continuum of services available to students of diverse gender, ethnic, social, and economic backgrounds, clearly supporting the university's commitment to provide a high quality education to all students.

The DIALM-POMC Joint Workshop is devoted to discrete algorithms and
discrete modelling in the context of mobile and wireless computing and
communications. It is intended to be a lively meeting, covering many
of the algorithmic and discrete aspects of this field going from
operations research to radio engineering problems. It aims, in
particular, at fostering the cooperation among practitioners and
theoreticians of the field.
If this project is awarded, the funds provided by NSF to support
DIALM-POMC'2003 will be used to provide funds for inviting two renowed
speakers in the area of mobile computing to present at the workshop,
to allow for reduced registration costs for students, and to provide
travel support for students attending the workshop.

This project is a continuation of a previously and currently successful CSEMS program at Arizona State University. The project implements a comprehensive mentor driven scholarship program that significantly improves the retention, graduation, and placement of low income lower division students majoring in CSEM disciplines; e.g. computer science, computer technology, engineering, engineering technology, and mathematics. The program makes use of existing services made possible by the Arizona State University (ASU) SUMS Institute.
Intellectual Merit: Selected students participate in a variety of mentor-supervised activities designed to insure success in their undergraduate studies and successful transition from their undergraduate environment into graduate school and/or industry. The program builds on an extensive track record established by the ASU SUMS Institute in managing such programs. This includes two prior CSEMS programs; one aimed at incoming freshmen and lower division students; the other aimed at juniors and seniors. These programs provide the project directors with extensive knowledge - knowledge that serves as the basis for the program.
The program selects a total of 30 lower division students to receive CSEMS scholarships each year. Twenty of the selected students are incoming freshmen. The incoming freshmen participate in a summer bridge program where they enroll in either calculus (8 weeks) or pre-calculus (5 weeks). This bridge program assists the students in their transition to the university environment. An additional ten students, already enrolled, lower division ASU students will also be selected to receive CSEMS scholarships.
Broader Impacts: As the students transition from lower division to upper division, efforts are made by the project directors to assist in the transition of capable students to funded faculty-directed research projects.

This program provides 33 scholarships per year to academically talented, financially disadvantaged upper division students, including women and students from underrepresented minorities. The program is associated with well-established student support infrastructure and student-centered programs. A community-of-mentors model is used to help students achieve degree completion in computer, science, engineering, and mathematics disciplines. The project is administered through the SUMS Institute (Strengthening Understanding of Mathematics and Science) that is working to expand and enhance the continuum of services available to students of diverse gender, ethnic, social, and economic backgrounds in order to further this university's commitment to provide a high quality education to all students. The program includes a network with local industry to offer ample internship and training experiences, employment opportunities, and to encourage the scholarship students to complete community service projects. A comprehensive and realistic evaluation plan is gathering evidence about the outcomes from these initiatives.

Intellectual Merit. The project provides 32 scholarships per year to academically talented, financially disadvantaged lower-division computer science, engineering, and mathematics (CSEM) students, especially women and underrepresented minorities. These scholarships, together with a well-established infrastructure and student-centered programs, exploiting a community-of mentors, enable selected students to maintain full-time enrollment and achieve degree completion. The project is administered through the university's SUMS Institute (Strengthening Understanding of Mathematics and Science). The function of SUMS is to: (1) recruit and select program students from across the state; (2) provide activities that increase retention, support student academic/professional development through degree completion, and prepare students for graduate school and future employment.

Broader Impacts. The program helps ensure a successful transition to upper-division work, research, graduate school, and the STEM workforce. Building on prior and current projects, program activities are designed to transition lower-division students from S-STEM funds to cutting-edge student-funded research projects. Toward this end, 10 NSF-LSAMP-WAESO and 5 NASA Space Grant slots are available for mentor-guided undergraduate research projects. Intel, Microchip, and NASA provide technical mentors. Prior CSEMS programs average over 87% retention with over 35% of recent upper-division students going on to graduate school full-time -- nearly double the national rate. The project is expanding and enhancing the continuum of services available to students of diverse gender, ethnic, social, and economic backgrounds, clearly supporting the university's commitment to provide a high quality education to all students. It also introduces students to exciting new research developments spanning all CSEM disciplines and encourages them to earn a technical graduate degree.

This project addresses the problem of efficient and scalable routing in dynamic distributed networks. The goal is to design compact routing schemes (that is, schemes with low memory overhead) with locality-sensitive node join, leave and move operations (that is, the cost of a node move operation should be proportional to the distance the node moves). An important application of routing is the design of object location services and distributed hash tables. The novel features of this research include improved bounds on the quality of routing paths, the ability to efficiently deal with highly dynamic node operations, and fault tolerance. Further, an important goal is to provide graceful degradation: if the assumptions under which the routing and location scheme works are violated or relaxed, the failure should not be abrupt, but instead the performance should worsen only as a function of the degree to which the assumptions were relaxed.

New paradigms of computation motivated by the development of the Internet lead to viewing the computer network itself as a computer and require an understanding of computation distributed across a large-scale and unstructured networks, whose many nodes are capable of performing computations independently. A basic operation in such a system is routing: nodes should be able to send each other messages without necessarily having complete information about the network. The messages should be sent along efficient routes, and individual nodes should not be required to store too much information about the network structure. Further, the network may change over time, with nodes joining or leaving, or moving within the network. An additional complication arises when fault tolerance is considered, since the system must be able to continue working correctly even in the presence of faults. This project will advance our understanding of the structure of networks that we rely on in everyday life, improve the efficiency and reduce the vulnerability of computer networks and applications, thus contributing to the development and deployment of secure network applications and infrastructure. The PIs' earlier work on distributed object location has been integrated in real-world systems. Since the focus of this project is on more realistic scenarios but problems just as important, it is likely that it will lead to further implementations and systems of wide applicability.

The rapid rise of overlay networks -- as for example, in the form of social networks and other peer-to-peer systems, sensor networks, or mobile ad hoc networks -- is revolutionizing the way we group and exchange information. However, not much is known about self-stabilization mechanisms for these highly dynamic networks. Minimum requirements for overlay network protocols to be useful in practice are that they be local, simple, and self-stabilizing. Locality is important for fast response times and for minimizing the impact of topology changes on the overlay network properties, simplicity is important so that the protocols can be used in a wide range of systems and for a formal verification of their effectiveness, and self-stabilization is important for automatic recovery from any illegal state since protocols requiring human intervention will not scale to systems potentially spanning millions of sites.

This project provides mechanisms that allow overlay networks to self-stabilize from an arbitrary connected state in an efficient and robust way. Moreover, our mechanisms will self-stabilize from an arbitrary state even under adversarial behavior of some of the nodes. Since overlay networks and self-stabilization are used in many contexts, this project benefits a number of research communities within and outside of computer science. Moreover, it consolidates strong international collaboration with the Tech. U. of Munich, Germany, while advancing education and enhancing diversity at Arizona State University.

This award is co-funded in part by NSF's Office of International Science and Engineering (OISE).

From an algorithmic point of view, systems based on wireless communication pose unique challenges that are not present in standard networks. Wireless devices may move around and communication between these devices can be disrupted for several reasons including obstacles, background noise, and interference problems due to transmissions from the own wireless network, from a malicious jammer trying to disrupt communication, as well as coexisting networks using the same frequency band. Finding suitable models that on one hand allow the rigorous design and analysis of protocols and on the other hand are useful in practice is a major challenge and deserves significant research efforts.

We will investigate models for wireless communication that cover a wide range of physical layer phenomena and that are yet simple enough so that they are useful in theory and practice. In contrast to prior algorithmic approaches, our approach will be to model communication problems due to physical layer issues (such as ackground noise, obstacles, jammers, etc.) with the help of an adversary, and to develop medium access (MAC) protocols that are provably robust against these adversaries. Such an approach has many interesting applications. First, it allows for more general scenarios for the background noise than previous approaches as it covers bursty situations that might be due to some temporary obstacle or operation of a machine that creates interference. Second, the adversarial model would also allow us to determine how robust a protocol is against wireless jamming attacks, which are a real threat to standard protocols such as the 802.11 family or networks of simple sensing wireless devices (where traditional physical layer techniques cannot be successfully applied). Finally, the adversarial model may allow us to abstract from interference problems due to transmissions of far away devices in the wireless network. In addition, we will also focus on important applications such as leader election and broadcasting.

Since wireless networks are a component of many widespread and/or critical systems, the proposed research will have an impact in several respects, including immediate applications to emergency services, the military, and local area networks in hazardous areas. Moreover, the proposed research will also have an impact in solidifying the international collaboration with the U. of Paderborn, Germany, and in advancing education and enhancing diversity.

This project supports participation for 20 US-based students to the 14th International Symposium on Stabilization, Safety, and Security
(SSS 2012) to be held in Toronto, Canada during October 1?4, 2012. The purpose of the participation is to expose students to the theoretical modeling of important properties such as safety, robustness, stability, etc. in large systems.

The goal of this project is to lay the foundations for algorithmic research on self-organizing particle systems. Particle systems are physical systems of simple computational particles that can bond to other particles and that can use these bonds in order to communicate with neighboring particles and to move from one spot to another (non-occupied) spot. These particle systems are supposed to be able to self-organize in order to adapt to a desired shape without any central control. Self-organizing particle systems have many interesting applications like coating objects for monitoring and repair purposes and the formation of nano-scale devices for surgery and molecular-scale electronic structures. While there has been quite a lot of systems work in this area, especially in the context of modular self-reconfigurable robotic systems, only very little theoretical work has been done in this area so far. This project will prepare the ground for rigorous algorithmic research on self-organizing particle systems by proposing some basic models and solving some basic algorithmic problems in this area.

The main objectives of this one-year project are (i) to develop appropriate models for particle systems; (ii) to develop self-organizing algorithms for smart paint problems; and (iii) to better educate the Computer Science (CS) Theory/Algorithms community on self-organizing particle systems. The proposed NSF sponsored workshop will foster collaboration of research in this interdisciplinary area.

The goal of this project is to lay the foundations for algorithmic research on self-organizing particle systems. Particle systems are physical systems of simple computational particles that can bond to other particles and that can use these bonds in order to communicate with neighboring particles and to move from one spot to another (non-occupied) spot. These particle systems are supposed to be able to self-organize in order to adapt to a desired shape without any central control. Self-organizing particle systems have many interesting applications like coating objects for monitoring and repair purposes and the formation of nano-scale devices for surgery and molecular-scale electronic structures. While there has been quite a lot of systems work in this area, especially in the context of modular self-reconfigurable robotic systems, only very little theoretical work has been done in this area so far.

This project will prepare the ground for rigorous algorithmic research on self-organizing particle systems by proposing basic models and solving some basic algorithmic problems in this area. More specifically, the main objectives of this three-year project are (i) to refine an amoeba-inspired model  for particle systems in 2D, and to develop appropriate models for particle systems in 3D; and (ii) to develop self-organizing algorithms for the smart paint problem, covering and bridging problems, shape formation problems, and the macrophage problem in 2D and 3D. A transformative, novel thinking approach will be needed if one indeed wants to capture the essential nature of these systems, in some ways mimicking those that already exist in nature.

The proposed research will have an impact in several respects, such as: (i) bridging the gap between theory and practice in the area of self-organizing particle systems, with impact on many application areas such as micro-fabrication and cellular engineering; (ii) international collaboration; (iii) multidisciplinary activities, since the topics in this proposal will foster collaboration with researchers in multiple areas such as nano-scale micro-fabrication, cellular engineering, nano-scale medical applications, biochemistry, and computer science; and (iv) enhancing diversity at Arizona State University and at the Computer Science Theory\Algorithms community at large.

Swarm robotics explores how groups of robots can work towards a singular goal. Such a goal is typically achieved by equipping each robot with sensory capabilities, basic computing power, and actuation. The sensors detect something about the environment, this information is used to make a decision about the next action, and some resulting actuation is performed. Swarm robotics has made many advances in recent years, but it is still in its infancy. The PIs will take a "task-oriented" approach and start from a desired macroscopic emergent collective behavior to develop the distributed and stochastic algorithmic underpinnings that the robots will run (at the microscopic level) in order to converge to the desired macroscopic behavior; as part of the process, they will also provide the understanding for yet unexplored collective and emergent systems. The robots envisioned are small in scale, ranging in size from millimeters to centimeters, so that when deployed in crowded (i.e., dense) environments, they will behave as active matter, more specifically as macroscopic programmable active matter. The emergent behaviors of interest for simulations include clustering (forming a tight-knit community that is mostly well-connected), compression (maintaining coherence of a connected community while minimizing perimeter), flocking (determining an agreed upon direction of orientation), and locomotion (collectively moving while maintaining cohesiveness). Many of these have interesting converse problems which are also equally worthwhile, such as exploration (maintaining a connected population, but exploring maximal area) and desegregation (preventing separation in a binary mixture of particles).

The PIs have strong records for interdisciplinary research, including initiating interdisciplinary areas, e.g., robo-physics (Goldman), self-organizing particle systems (Richa), and the fusion of statistical physics and randomized algorithms (Randall). The PIs also have a strong commitment toward supporting minorities, women, and undergraduate research (e.g., through NSF S-STEM programs at ASU; ADVANCE and S.U.R.E. programs at Georgia Tech). This project will bring together techniques from multiple disciplines, and new research approaches and findings will be incorporated into graduate courses. Findings (including open source code) will be published in the various disciplines, and will be made available on the web and ArXiv.

The specific goals of this project are to work toward developing a theoretical framework for task-oriented active matter, informed by models of simple physical systems, that can realize and test the algorithms. The swarm robotics systems that biophysicists build to understand nature can be modified to perform the tasks these new algorithms require. The physical models will allow refinements to the theories under additional constraints, such as gravity and limited energy. It also will allow the PIs to test their algorithms for robustness, as physical systems admit some error. The fundamentals of swarm robotics will be studied from a physics standpoint, by viewing the ensemble as active matter composed of programmable elements at the micro-level. Thus, a (macro-)task oriented approach will be followed in order to design a distributed, stochastic algorithmic framework to construct and evaluate algorithms at the micro-level that yield the targeted emergent macro-behavior.

Swarm robotics explores how groups of robots can work towards a singular goal, which is typically achieved by equipping each robot with sensory capabilities, basic computing power, and movement. The sensors detect and use information about the environment to decide on the next action. Swarm robotics has made many advances in recent years, but is still in its infancy. This project proposes to explore swarm robotics systems in a non-standard way as physical systems. The PIs take a "task-oriented" approach to develop the distributed algorithmic rules that the robots will run (at the microscopic level) in order to converge to the desired collective behavior (at the macroscopic level). This will provide understanding of the minimal requirements for individuals to accomplish the desired behavior, for both algorithmic and physical realizations, and will provide a more principled approach for studying swarm robotics. The robots envisioned are small in scale, ranging in size from millimeters to centimeters, so that when deployed in dense environments, they will behave as programmable active matter.

The PIs have strong records for interdisciplinary research, including initiating interdisciplinary areas (e.g., robo-physics, self-organizing particle systems, and the fusion of statistical physics and randomized algorithms). They have a strong commitment toward supporting minorities, women, and undergrad research (e.g., through NSF REUs, including through this project, NSF S-STEM programs at ASU; ADVANCE and S.U.R.E. programs at Georgia Tech). Any breakthrough in this combination of swarm and active matter systems will require employing analyses and techniques from stochastic systems, condensed matter physics, swarm systems, robotics, and distributed algorithms to understand and achieve the desired group dynamics, and hence will bring together and educate researchers from different disciplines and specialties. New research approaches and findings will be incorporated into multiple graduate courses and workshops will provide tutorials for bridging multiple disciplines, making material accessible to young researchers and helping to widely disseminate results. Findings (including open source code) will be published in the various disciplines, and will be be made available on our web pages and ArXiv.

The project explores the fundamentals of swarm robotics from a physics standpoint, by viewing the ensemble as active matter composed of programmable elements at the micro-level. The project will follow a (macro-)task oriented approach, and design a distributed stochastic algorithmic framework to design and evaluate algorithms at the micro-level that will yield the targeted emergent macroscopic behavior. The emergent behaviors it addresses include compression (maintaining coherence of a connected community while minimizing perimeter), bridging (connecting two or more locations in the most efficient manner), alignment (determining an agreed upon direction of orientation), jamming (obstruction of movement by increased collective flow), and locomotion (collectively moving while maintaining cohesiveness). Many of these have interesting converse problems which are also equally worthwhile, such as exploration (maintaining a connected population, but exploring maximal area) and non-alignment (representing a disordered ensemble). In some cases the collective behavior acts like a physical system changing between a liquid (disordered) and a solid (ordered) state, as determined by phase transitions in the systems. The project will explore stochastic and distributed algorithms for rigorously achieving these goals.

Self-organization can be viewed as a phenomenon whereby unanticipated global configurations and patterns of a collective emerge from fully distributed and simplistic rules performed by each individual, without any global coordination or external intervention. Self-organization and emergent behavior arise naturally across many fields: distributed systems and swarm robotics in computer science, interacting particle systems in physics, population dynamics and flock coordination in biology, autonomous systems in robotics and control theory, and smart materials, to name a few. Recently, the synergy between discrete probability, algorithms and statistical physics has provided a new approach for designing self-organizing particle systems by harnessing collective, emergent behavior of physical systems. The laws of physics play an increasingly important role in collective behavior at the nano- and micro-scales, especially since individual agents are far less capable than their macroscopic counterparts. Yet, while the principles of statistical physics have motivated many experimental systems, little has been done to make the corresponding underlying distributed algorithms rigorous.

This project investigates how to program collections of agents to perform tasks by modeling the dynamics as self-organizing particle systems performing steps of Markov chains through local interactions that can be rigorously analyzed. The limiting distributions of these chains have distinct equilibrium characteristics that can be used to program collective behavior. The principal investigators take a three-pronged approach: First, they introduce and study generalizations of common statistical physics models, such as the Potts, Ising and hard-core models, to better capture the constraints imposed by micro-scale systems of interacting agents. Next, they explore methods to better understand the nonequilibrium dynamics of these systems long before convergence and possibly subject to forces that make the Markov chains nonreversible. Finally, they explore how collective systems might be programmed through deliberate placement of obstacles and features in the environment, rather than programming the agents themselves, as many of these tiny agents are incapable of any sophisticated (traditional) computation. As an example of programming the environment, a new version of the Schelling segregation model is being studied where people move with higher probabilities if they are unhappy with the local demographics of their neighborhoods, but these preferences can be somewhat mitigated by the placement of desirable urban infrastructures that modify individuals' incentive structures and biases. The project is having impact in promoting and advancing interdisciplinary research across many fields; education, through advanced graduate courses and broad, interdisciplinary talks; diversity at the graduate, undergraduate, and faculty levels; outreach to the general public and for K-12 education; and municipal planning, through coordination with regional planning faculty and the City of Atlanta.

This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.