Solving problems efficiently in distributed systems is often impossible, the main reason being that each device in the system doesn't have information about the system as a whole. In particular, each device only has $\textit{local}$ information: it might know its own ID (or MAC address) and maybe some information about its immediate neighbours, but doesn't know anything beyond that. The study of $\textit{advice complexity}$ aims to determine how much additional information should be given to each device in order to bring down the complexity of the problem. This often comes in the form of $\textit{global}$ information, e.g., the size, diameter, or maximum degree of the network. So far, we have studied the advice complexity of various problems in networks, including: broadcasting, robot gathering, and leader election.

When we theoretically study online problems, we often compare an online algorithm with an optimal offline algorithm. This comparison, known as competitive analysis, is often criticized as being unfair to the online algorithm. One way to address this issue is to give some bits of advice to the algorithm to enhance its performance. The advice can encode any information that the algorithm needs. In this project, we study the advice complexity of a variety of online problems. We consider questions of the following form: -How much advice is required/sufficient to achieve an optimal algorithm or an algorithm whose cost is within a given ratio of an optimal cost? -How much a constant number of bits of advice can hep in achieving better algorithms? (e.g., with 1 bit of advice, an algorithm can select the better option among 2 algorithms that run in parallel; how those 2 algorithm should be designed to `complement' each other?

In many cloud-related applications, we need to hots cloud objects (e.g., database tenants or instances of online games) into cloud servers. The objective is to minimize a cost which is function of the number of servers or the amount of time they have been used. These applications can be modeled as variant instances of the bin packing problem. In the classic online bin packing, the goal is to place a sequence of items of different sizes into a minimum number of bins of uniform capacity; items arrive one by one and each should be placed without any knowledge about forthcoming items. For cloud purposes, bins represent servers and items are cloud objects. In mult-tenant server consolidation problem, the objective is to achieve a `fault-tolerant' bin packing where failure of one -or more- servers does not interrupt tasks. For that, we place each item (e.g., database tenant) into at least two servers (bins) in a way that the extra load redirected from a failed bin does not overload other bins. Renting servers in cloud is another application in which items have an unknown expiry time (e.g., a game with no time limit) and the goal is to place items into bins so that the total rental cost is minimized; here the cost for renting a server is a function of the total time that it has been used. We study different algorithms for the above-mentioned and other applications of bin packing under the framework of competitive analysis.

Given a list $A[1:n]$ of $n$ items, we consider the problem of constructing a (typically linear-space) data structure that efficiently answers subsequent range frequency queries on $A$. Each query consists of an input pair of indices $(i, j)$ for which a particular statistic of $A[i:j]$ must be returned (e.g., a mode, minimum, least-frequent element, minority, or majority).

Communication among nodes in a wireless radio network has to overcome the challenge that simultaneous transmissions by nearby nodes can lead to message loss due to signal interference. Algorithms that avoid all interference can be very costly, so our research involves designing algorithms that work efficiently despite the loss of some messages. This becomes especially challenging when we consider networks of mobile nodes. So far, our work has focused on problems such as broadcasting (one-to-all communication), gossiping (all-to-all communication), and neighbour discovery.

This project involves research in simplifying and estimating geometric point data, including work on:

• nonparametric simplication for piecewise linear curves, and
• measures of data depth defined in terms of combinatorial geometry.

Compression schemes such as bzip2 are based on encoding/decoding characters stored in a list which is adjusted using Move-To-Front algorithm. If we apply this scheme for an input with high locality (e.g., Burrows-Wheeler transformation of a given text) the result will have high compression. This projects considers variants of Move-To-Front for updating the list as well as other techniques such as including advice bits into the input to achieve even better compression. We study the problem from both theoretical and practical points of view.

We study situations where mobile robots must collectively accomplish a task without the help of a central coordinator. One common task is Gathering (or Rendezvous): we want all robots to meet at the same place at the same time, perhaps in order to share information or coordinate future actions. We consider environments such as networks or the 2D-plane, and we want to design good algorithms with respect to performance measures such as: minimizing time to completion, maximizing resilience to faults/failures, or minimizing how much initial information the robots need.

When wireless nodes are represented by points in Euclidean space, networks edges are defined by a geometric proximity graph, and the distance between two nodes is measured by the number of network hops on a shortest path connecting them, the resulting facility location problems are set neither solely in Euclidean space nor on a graph. Although similar to problems of facility location in both settings, existing solutions do not necessarily apply to this new combination of graph-theoretic and geometric constraints. Unit disc graphs are proximity graphs that are frequently used to model wireless networks. We consider the $k$-centre problem on unit disc graphs: given a set of points $P$ in the plane, find a set $F$ of $k$ points in the plane that minimizes the maximum graph distance from any vertex in $P$ to the nearest vertex in $F$ in the unit disc graph induced by $P \cup F$. We describe exact and approximate polynomial-time solutions to this problem for any fixed k and show that the problem is NP-hard when $k$ is an arbitrary input parameter.

Saeed Mehrabi is a Ph.D. student that worked with Dr. Durocher in the Computational Geometry Laboratory working on algorithms for exact and approximate solutions to problems in geometric optimization, including results on:

• sliding cameras (art galleries with line segment guards), and
• partitions with minimum stabbing number.

Graph burning is a model for the spread of social influence in networks. The objective is to measure how quickly a fire (e.g., a piece of fake news) can be spread in a network. The burning process takes place in discrete rounds. In each round, a new fire breaks out at a selected vertex and burns it. Meanwhile, the old fires extend to their adjacent vertices and burn them. A "burning schedule" selects where the new fire breaks out in each round, and the "burning problem" asks for a schedule that burns all vertices in a minimum number of rounds, termed the "burning number" of the graph. We have worked on creating efficient algorithms that find optimal (or near-optimal) burning schedules, and also on proving bounds on how quickly graphs can be burned.

Debajyoti Mondal is a Ph.D. student that worked with Dr. Durocher in the Computational Geometry Laboratory working on problems in graph drawing, including results on:

• minimum-segment drawings of planar graphs,
• plane 3-trees,
• thickness and colourability,
• pairwise compatibility graphs, and
• point-set embeddings.

A local routing algorithm makes a sequence of distributed forwarding decisions, each of which is made using only local information. Specifically, in addition to knowing the node for which a message is destined, an intermediate node might also know: the node from which the message originated, which of its neighbours last forwarded the message, and the subgraph corresponding to all network nodes within $k$ hops of itself, for some value of $k$. We examine theoretical bounds on the locality of routing. Our objective is to determine which of these parameters are necessary and/or sufficient to permit local routing as k varies on a network modelled by a connected undirected graph. Our results include: showing that no k-local routing algorithm succeeds on unit ball graphs for any fixed k when nodes are location-aware, establishing tight bounds on k for the feasibility of deterministic k-local routing under various combinations of these parameters, and establishing tight bounds on the dilation (the worst-case ratio of actual route length to shortest path length) for k-local routing algorithms.

Consider a set of routers forming a network, and each router has a memory buffer with limited size. If more packets arrive at a router than it can store in its memory, it must drop some of the packets, and they are lost forever. Packets arrive at routers in two ways: either they are forwarded by other routers in the network, or they are injected into the router directly from an external source. We consider the task of creating and analyzing algorithms that decide when and where each router should forward packets in the network, with the goal of dropping as few packets as possible.

Publications

Last updated: Wed, 23 Sep 20 22:04:58 -0500

News