Source author record

Avery Miller

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Distributed, Parallel, and Cluster Computing Data Structures and Algorithms

Catalog footprint

Research overview

9works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

Deterministic Leader Election in Anonymous Radio Networks

We consider leader election in anonymous radio networks modeled as simple undirected connected graphs. Nodes communicate in synchronous rounds. Nodes are anonymous and execute the same deterministic algorithm, so symmetry can be broken only in one way: by different wake-up times of the nodes. In which situations is it possible to break symmetry and elect a leader using time as symmetry breaker? To answer this question, we consider configurations. A configuration is the underlying graph with nodes tagged by non-negative integers with the following meaning. A node can either wake up spontaneously in the round shown on its tag, according to some global clock, or can be woken up hearing a message sent by one of its already awoken neighbours. The local clock of a node starts at its wakeup and nodes do not have access to the global clock determining their tags. A configuration is feasible if there exists a distributed algorithm that elects a leader for this configuration. Our main result is a complete algorithmic characterization of feasible configurations: we design a centralized decision algorithm, working in polynomial time, whose input is a configuration and which decides if the configuration is feasible. We also provide a dedicated deterministic distributed leader election algorithm for each feasible configuration that elects a leader for this configuration in time $O(n^2σ)$ , where $n$ is the number of nodes and $σ$ is the difference between the largest and smallest tag of the configuration. We then prove that there cannot exist a universal deterministic distributed algorithm electing a leader for all feasible configurations. In fact, we show that such a universal algorithm cannot exist even for the class of 4-node feasible configurations. We also prove that a distributed version of our decision algorithm cannot exist.

preprint2020arXiv

Fast Byzantine Gathering with Visibility in Graphs

We consider the gathering task by a team of $m$ synchronous mobile robots in a graph of $n$ nodes. Each robot has an identifier (ID) and runs its own deterministic algorithm, i.e., there is no centralized coordinator. We consider a particularly challenging scenario: there are $f$ Byzantine robots in the team that can behave arbitrarily, and even have the ability to change their IDs to any value at any time. There is no way to distinguish these robots from non-faulty robots, other than perhaps observing strange or unexpected behaviour. The goal of the gathering task is to eventually have all non-faulty robots located at the same node in the same round. It is known that no algorithm can solve this task unless there at least $f+1$ non-faulty robots in the team. In this paper, we design an algorithm that runs in polynomial time with respect to $n$ and $m$ that matches this bound, i.e., it works in a team that has exactly $f+1$ non-faulty robots. In our model, we have equipped the robots with sensors that enable each robot to see the subgraph (including robots) within some distance $H$ of its current node. We prove that the gathering task is solvable if this visibility range $H$ is at least the radius of the graph, and not solvable if $H$ is any fixed constant.

preprint2020arXiv

Four Shades of Deterministic Leader Election in Anonymous Networks

Leader election is one of the fundamental problems in distributed computing: a single node, called the leader, must be specified. This task can be formulated either in a weak way, where one node outputs 'leader' and all other nodes output 'non-leader', or in a strong way, where all nodes must also learn which node is the leader. If the nodes of the network have distinct identifiers, then such an agreement means that all nodes have to output the identifier of the elected leader. For anonymous networks, the strong version of leader election requires that all nodes must be able to find a path to the leader, as this is the only way to identify it. For any network in which leader election (weak or strong) is possible knowing the map of the network, there is a minimum time in which this can be done. We consider four formulations of leader election discussed in the literature in the context of anonymous networks : one is the weak formulation, and the three others specify three different ways of finding the path to the leader in the strong formulation. Our aim is to compare the amount of initial information needed to accomplish each of these "four shades" of leader election in minimum time. We show that the amount of information required to accomplish leader election in the weak formulation in minimum time is exponentially smaller than that needed for any of the strong formulations. Thus, if the required amount of advice is used as a measure of the difficulty of the task, the weakest version of leader election in minimum time is drastically easier than any version of the strong formulation in minimum time.

preprint2015arXiv

Global Synchronization and Consensus Using Beeps in a Fault-Prone MAC

Consensus is one of the fundamental tasks studied in distributed computing. Processors have input values from some set $V$ and they have to decide the same value from this set. If all processors have the same input value, then they must all decide this value. We study the task of consensus in a Multiple Access Channel (MAC) prone to faults, under a very weak communication model called the $\mathit{beeping\ model}$ . Communication proceeds in synchronous rounds. Some processors wake up spontaneously, in possibly different rounds decided by an adversary. In each round, an awake processor can either listen, i.e., stay silent, or beep, i.e., emit a signal. In each round, a fault can occur in the channel independently with constant probability $0<p<1$ . In a fault-free round, an awake processor hears a beep if it listens in this round and if one or more other processors beep in this round. A processor still dormant in a fault-free round in which some other processor beeps is woken up by this beep and hears it. In a faulty round nothing is heard, regardless of the behaviour of the processors. An algorithm working with error probability at most $ε$ , for a given $ε>0$ , is called $ε$ - $\mathit{safe}$ . Our main result is the design and analysis, for any constant $ε>0$ , of a deterministic $ε$ -safe consensus algorithm that works in time $O(\log w)$ in a fault-prone MAC, where $w$ is the smallest input value of all participating processors. We show that this time cannot be improved, even when the MAC is fault-free. The main algorithmic tool that we develop to achieve our goal, and that might be of independent interest, is a deterministic algorithm that, with arbitrarily small constant error probability, establishes a global clock in a fault-prone MAC in constant time.

preprint2015arXiv

Time Versus Cost Tradeoffs for Deterministic Rendezvous in Networks

Two mobile agents, starting from different nodes of a network at possibly different times, have to meet at the same node. This problem is known as $\mathit{rendezvous}$ . Agents move in synchronous rounds. Each agent has a distinct integer label from the set $\{1,\dots,L\}$ . Two main efficiency measures of rendezvous are its $\mathit{time}$ (the number of rounds until the meeting) and its $\mathit{cost}$ (the total number of edge traversals). We investigate tradeoffs between these two measures. A natural benchmark for both time and cost of rendezvous in a network is the number of edge traversals needed for visiting all nodes of the network, called the exploration time. Hence we express the time and cost of rendezvous as functions of an upper bound $E$ on the time of exploration (where $E$ and a corresponding exploration procedure are known to both agents) and of the size $L$ of the label space. We present two natural rendezvous algorithms. Algorithm $\mathtt{Cheap}$ has cost $O(E)$ (and, in fact, a version of this algorithm for the model where the agents start simultaneously has cost exactly $E$ ) and time $O(EL)$ . Algorithm $\mathtt{Fast}$ has both time and cost $O(E\log L)$ . Our main contributions are lower bounds showing that, perhaps surprisingly, these two algorithms capture the tradeoffs between time and cost of rendezvous almost tightly. We show that any deterministic rendezvous algorithm of cost asymptotically $E$ (i.e., of cost $E+o(E)$ ) must have time $Ω(EL)$ . On the other hand, we show that any deterministic rendezvous algorithm with time complexity $O(E\log L)$ must have cost $Ω(E\log L)$ .

preprint2015arXiv

Time vs. Information Tradeoffs for Leader Election in Anonymous Trees

The leader election task calls for all nodes of a network to agree on a single node. If the nodes of the network are anonymous, the task of leader election is formulated as follows: every node $v$ of the network must output a simple path, coded as a sequence of port numbers, such that all these paths end at a common node, the leader. In this paper, we study deterministic leader election in anonymous trees. Our aim is to establish tradeoffs between the allocated time $τ$ and the amount of information that has to be given $\textit{a priori}$ to the nodes to enable leader election in time $τ$ in all trees for which leader election in this time is at all possible. Following the framework of $\textit{algorithms with advice}$ , this information (a single binary string) is provided to all nodes at the start by an oracle knowing the entire tree. The length of this string is called the $\textit{size of advice}$ . For an allocated time $τ$ , we give upper and lower bounds on the minimum size of advice sufficient to perform leader election in time $τ$ . We consider $n$ -node trees of diameter $diam \leq D$ . While leader election in time $diam$ can be performed without any advice, for time $diam-1$ we give tight upper and lower bounds of $Θ(\log D)$ . For time $diam-2$ we give tight upper and lower bounds of $Θ(\log D)$ for even values of $diam$ , and tight upper and lower bounds of $Θ(\log n)$ for odd values of $diam$ . For the time interval $[β\cdot diam, diam-3]$ for constant $β>1/2$ , we prove an upper bound of $O(\frac{n\log n}{D})$ and a lower bound of $Ω(\frac{n}{D})$ , the latter being valid whenever $diam$ is odd or when the time is at most $diam-4$ . Finally, for time $α\cdot diam$ for any constant $α<1/2$ (except for the case of very small diameters), we give tight upper and lower bounds of $Θ(n)$ .

preprint2015arXiv

Tradeoffs Between Cost and Information for Rendezvous and Treasure Hunt

In rendezvous, two agents traverse network edges in synchronous rounds and have to meet at some node. In treasure hunt, a single agent has to find a stationary target situated at an unknown node of the network. We study tradeoffs between the amount of information ( $\mathit{advice}$ ) available $\mathit{a\ priori}$ to the agents and the cost (number of edge traversals) of rendezvous and treasure hunt. Our goal is to find the smallest size of advice which enables the agents to solve these tasks at some cost $C$ in a network with $e$ edges. This size turns out to depend on the initial distance $D$ and on the ratio $\frac{e}{C}$ , which is the $\mathit{relative\ cost\ gain}$ due to advice. For arbitrary graphs, we give upper and lower bounds of $O(D\log(D\cdot \frac{e}{C}) +\log\log e)$ and $Ω(D\log \frac{e}{C})$ , respectively, on the optimal size of advice. For the class of trees, we give nearly tight upper and lower bounds of $O(D\log \frac{e}{C} + \log\log e)$ and $Ω(D\log \frac{e}{C})$ , respectively.

preprint2014arXiv

Election vs. Selection: Two Ways of Finding the Largest Node in a Graph

Finding the node with the largest label in a network, modeled as an undirected connected graph, is one of the fundamental problems in distributed computing. This is the way in which $\textit{leader election}$ is usually solved. We consider two distinct tasks in which the largest-labeled node is found deterministically. In $\textit{selection}$ , this node must output 1 and all other nodes must output 0. In $\textit{election}$ , the other nodes must additionally learn the largest label. Our aim is to compare the difficulty of these two tasks executed under stringent running time constraints. The measure of difficulty is the amount of information that nodes of the network must initially possess in order to solve the given task in an imposed amount of time. Following the standard framework of $\textit{algorithms with advice}$ , this information (a single binary string) is provided to all nodes at the start by an oracle knowing the entire graph. The length of this string is called the $\textit{size of advice}$ . Consider the class of $n$ -node graphs with any diameter $diam \leq D$ . If time is larger than $diam$ , then both tasks can be solved without advice. For the task of $\textit{election}$ , we show that if time is smaller than $diam$ , then the optimal size of advice is $Θ(\log n)$ , and if time is exactly $diam$ , then the optimal size of advice is $Θ(\log D)$ . For the task of $\textit{selection}$ , the situation changes dramatically, even within the class of rings. Indeed, for the class of rings, we show that, if time is $O(diam^ε)$ , for any $ε<1$ , then the optimal size of advice is $Θ(\log D)$ , and, if time is $Θ(diam)$ (and at most $diam$ ) then this optimal size is $Θ(\log \log D)$ .

preprint2014arXiv

Fast Rendezvous with Advice

Two mobile agents, starting from different nodes of an $n$ -node network at possibly different times, have to meet at the same node. This problem is known as rendezvous. Agents move in synchronous rounds using a deterministic algorithm. In each round, an agent decides to either remain idle or to move to one of the adjacent nodes. Each agent has a distinct integer label from the set $\{1,...,L\}$ , which it can use in the execution of the algorithm, but it does not know the label of the other agent. If $D$ is the distance between the initial positions of the agents, then $Ω(D)$ is an obvious lower bound on the time of rendezvous. However, if each agent has no initial knowledge other than its label, time $O(D)$ is usually impossible to achieve. We study the minimum amount of information that has to be available a priori to the agents to achieve rendezvous in optimal time $Θ(D)$ . This information is provided to the agents at the start by an oracle knowing the entire instance of the problem, i.e., the network, the starting positions of the agents, their wake-up rounds, and both of their labels. The oracle helps the agents by providing them with the same binary string called advice, which can be used by the agents during their navigation. The length of this string is called the size of advice. Our goal is to find the smallest size of advice which enables the agents to meet in time $Θ(D)$ . We show that this optimal size of advice is $Θ(D\log(n/D)+\log\log L)$ . The upper bound is proved by constructing an advice string of this size, and providing a natural rendezvous algorithm using this advice that works in time $Θ(D)$ for all networks. The matching lower bound, which is the main contribution of this paper, is proved by exhibiting classes of networks for which it is impossible to achieve rendezvous in time $Θ(D)$ with smaller advice.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Avery Miller

Research overview

Is this your work?

9 publications

Deterministic Leader Election in Anonymous Radio Networks

Fast Byzantine Gathering with Visibility in Graphs

Four Shades of Deterministic Leader Election in Anonymous Networks

Global Synchronization and Consensus Using Beeps in a Fault-Prone MAC

Time Versus Cost Tradeoffs for Deterministic Rendezvous in Networks

Time vs. Information Tradeoffs for Leader Election in Anonymous Trees

Tradeoffs Between Cost and Information for Rendezvous and Treasure Hunt

Election vs. Selection: Two Ways of Finding the Largest Node in a Graph

Fast Rendezvous with Advice

See the researcher in context

Building this map preview