Theory of Distributed Systems (TDS)

We consider the task of measuring time with probabilistic threshold gates implemented by bio-inspired spiking neurons.

A famous result in sequential data structures that the Union-Find object can be implemented in amortized inverse-Ackermann work per operation.

Multiple walks in graph move in parallel across the edges of an initially unknown graph without central control with the goal of visiting all the vertices.

Abstract: In an increasingly data-rich world, brain-inspired computing concepts operating neuromorphic hardware have shown great promise for processing large datasets within tight volume and power budgets.

Autonomous vehicles will establish a spontaneous connection over a wireless radio channel while coordinating actions and information.

We are considering distributed network computing, in which computing entities are connected by a network modeled as a connected graph. These entities are located at the nodes of the graph, and they exchange information by message-passing along its edges.

Abstract: Motivated by the increasing need for fast distributed processing of large-scale graphs such as the Web graph, biological networks and various social networks, we study a number of fundamental graph problems

For decades, randomized exponential backoff has provided a critical algorithmic building block in situations where multiple devices seek access to a shared resource.

The (Delta+1)-coloring problem and the MIS (maximal independent set) problem are fundamental distributed symmetry-breaking problems.