Source author record

Gianluca De Marco

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

ResearcherUnclaimed source record

Data Structures and Algorithms Distributed, Parallel, and Cluster Computing

Catalog footprint

Research overview

3works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2016arXiv

Anonymous Processors with Synchronous Shared Memory

We consider synchronous distributed systems in which anonymous processors communicate by shared read-write variables. The goal is to have all the processors assign unique names to themselves. We consider the instances of this problem determined by whether the number $n$ is known or not, and whether concurrently attempting to write distinct values into the same memory cell is allowed or not, and whether the number of shared variables is a constant independent of $n$ or it is unbounded. For known $n$ , we give Las Vegas algorithms that operate in the optimum expected time, as determined by the amount of available shared memory, and use the optimum $O(n\log n)$ expected number of random bits. For unknown $n$ , we give Monte Carlo algorithms that produce correct output upon termination with probabilities that are $1-n^{-Ω(1)}$ , which is best possible when terminating almost surely and using $O(n\log n)$ random bits.

preprint2015arXiv

A Distributed Message-Optimal Assignment on Rings

Consider a set of items and a set of $m$ colors, where each item is associated to one color. Consider also $n$ computational agents connected by a ring. Each agent holds a subset of the items and items of the same color can be held by different agents. We analyze the problem of distributively assigning colors to agents in such a way that (a) each color is assigned to one agent only and (b) the number of different colors assigned to each agent is minimum. Since any color assignment requires the items be distributed according to it (e.g. all items of the same color are to be held by only one agent), we define the cost of a color assignment as the amount of items that need to be moved, given an initial allocation. We first show that any distributed algorithm for this problem requires a message complexity of $Ω(n\cdot m)$ and then we exhibit an optimal message complexity algorithm for synchronous rings that in polynomial time determines a color assignment with cost at most three times the optimal. We also discuss solutions for the asynchronous setting. Finally, we show how to get a better cost solution at the expenses of either the message or the time complexity.

preprint2011arXiv

Computing Majority with Triple Queries

Consider a bin containing $n$ balls colored with two colors. In a $k$ -query, $k$ balls are selected by a questioner and the oracle's reply is related (depending on the computation model being considered) to the distribution of colors of the balls in this $k$ -tuple; however, the oracle never reveals the colors of the individual balls. Following a number of queries the questioner is said to determine the majority color if it can output a ball of the majority color if it exists, and can prove that there is no majority if it does not exist. We investigate two computation models (depending on the type of replies being allowed). We give algorithms to compute the minimum number of 3-queries which are needed so that the questioner can determine the majority color and provide tight and almost tight upper and lower bounds on the number of queries needed in each case.

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.