Grant: Discovery Grants Program - Individual

Presently, most of the algorithms for solving problems in a distributed fashion do not make any assumptions regarding the degree to which the components of the underlying distributed system are synchronized.  Although such assumptions allow for a very general design methodologies, they ignore a useful attribute of most distributed systems;  namely, that the components of many distributed are comparatively synchronized.  The amount of synchrony in a system is the degree to which the system's components operate in concert. I propose to investigate how this synchrony among a system's components can be leveraged in order to design faster and more efficient distributed algorithms.  Specifically, I am interested in determining the types of synchrony present in distributed systems, which forms are most useful, and how to design distributed algorithms so that they can leverage these forms of synchrony. This is useful for several reasons.  First, it improves our understanding of the foundations of computer science.  We know that that synchrony plays an important role in determining whether and how efficiently a particular problem can be solved in a distributed manner; the challenge is to determine what this role is. Second, by determining what forms of synchrony are useful, we can design more efficient distributed systems.  These lessons are applicable to both the hardware designers and the software architects, and would facilitate better integration between a system's hardware and software.  This would improve the operation, efficiency and safety of distributed systems, which are being utilized more and more in research and industry.