BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Grzegorz Stachowiak

Grzegorz Stachowiak appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Distributed, Parallel, and Cluster ComputingData Structures and Algorithms

Catalog footprint

What is connected

7works
2topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

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.

Published work

7 published item(s)

preprint2022arXiv

A time and space optimal stable population protocol solving exact majority

We study population protocols, a model of distributed computing appropriate for modeling well-mixed chemical reaction networks and other physical systems where agents exchange information in pairwise interactions, but have no control over their schedule of interaction partners. The well-studied *majority* problem is that of determining in an initial population of $n$ agents, each with one of two opinions $A$ or $B$, whether there are more $A$, more $B$, or a tie. A *stable* protocol solves this problem with probability 1 by eventually entering a configuration in which all agents agree on a correct consensus decision of $\mathsf{A}$, $\mathsf{B}$, or $\mathsf{T}$, from which the consensus cannot change. We describe a protocol that solves this problem using $O(\log n)$ states ($\log \log n + O(1)$ bits of memory) and optimal expected time $O(\log n)$. The number of states $O(\log n)$ is known to be optimal for the class of polylogarithmic time stable protocols that are "output dominant" and "monotone". These are two natural constraints satisfied by our protocol, making it simultaneously time- and state-optimal for that class. We introduce a key technique called a "fixed resolution clock" to achieve partial synchronization. Our protocol is *nonuniform*: the transition function has the value $\left \lceil {\log n} \right \rceil$ encoded in it. We show that the protocol can be modified to be uniform, while increasing the state complexity to $Θ(\log n \log \log n)$.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Deterministic Symmetry Breaking in Ring Networks

We study a distributed coordination mechanism for uniform agents located on a circle. The agents perform their actions in synchronised rounds. At the beginning of each round an agent chooses the direction of its movement from clockwise, anticlockwise, or idle, and moves at unit speed during this round. Agents are not allowed to overpass, i.e., when an agent collides with another it instantly starts moving with the same speed in the opposite direction (without exchanging any information with the other agent). However, at the end of each round each agent has access to limited information regarding its trajectory of movement during this round. We assume that $n$ mobile agents are initially located on a circle unit circumference at arbitrary but distinct positions unknown to other agents. The agents are equipped with unique identifiers from a fixed range. The {\em location discovery} task to be performed by each agent is to determine the initial position of every other agent. Our main result states that, if the only available information about movement in a round is limited to %information about distance between the initial and the final position, then there is a superlinear lower bound on time needed to solve the location discovery problem. Interestingly, this result corresponds to a combinatorial symmetry breaking problem, which might be of independent interest. If, on the other hand, an agent has access to the distance to its first collision with another agent in a round, we design an asymptotically efficient and close to optimal solution for the location discovery problem.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

On the Impact of Geometry on Ad Hoc Communication in Wireless Networks

In this work we address the question how important is the knowledge of geometric location and network density to the efficiency of (distributed) wireless communication in ad hoc networks. We study fundamental communication task of broadcast and develop well-scalable, randomized algorithms that do not rely on GPS information, and which efficiency formulas do not depend on how dense the geometric network is. We consider two settings: with and without spontaneous wake-up of nodes. In the former setting, in which all nodes start the protocol at the same time, our algorithm accomplishes broadcast in $O(D\log n + \log^2 n)$ rounds under the SINR model, with high probability (whp), where $D$ is the diameter of the communication graph and $n$ is the number of stations. In the latter setting, in which only the source node containing the original message is active in the beginning, we develop a slightly slower algorithm working in $O(D\log^2 n)$ rounds whp. Both algorithms are based on a novel distributed coloring method, which is of independent interest and potential applicability to other communication tasks under the SINR wireless model.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Distributed Broadcasting in Wireless Networks under the SINR Model

In the advent of large-scale multi-hop wireless technologies, such as MANET, VANET, iThings, it is of utmost importance to devise efficient distributed protocols to maintain network architecture and provide basic communication tools. One of such fundamental communication tasks is broadcast, also known as a 1-to-all communication. We propose several new efficient distributed algorithms and evaluate their time performance both theoretically and by simulations. First randomized algorithm accomplishes broadcast in O(D+log(1/d)) rounds with probability at least 1-d on any uniform-power network of n nodes and diameter D, when equipped with local estimate of network density. Additionally, we evaluate average performance of this protocols by simulations on two classes of generated networks - uniform and social - and compare the results with performance of exponential backoff heuristic. Ours is the first provably efficient and well-scalable distributed solution for the (global) broadcast task. The second randomized protocol developed in this paper does not rely on the estimate of local density, and achieves only slightly higher time performance O((D+log(1/d))log n). Finally, we provide a deterministic algorithm achieving similar time O(D log^2 n), supported by theoretical analysis.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Distributed Deterministic Broadcasting in Uniform-Power Ad Hoc Wireless Networks

Development of many futuristic technologies, such as MANET, VANET, iThings, nano-devices, depend on efficient distributed communication protocols in multi-hop ad hoc networks. A vast majority of research in this area focus on design heuristic protocols, and analyze their performance by simulations on networks generated randomly or obtained in practical measurements of some (usually small-size) wireless networks. %some library. Moreover, they often assume access to truly random sources, which is often not reasonable in case of wireless devices. In this work we use a formal framework to study the problem of broadcasting and its time complexity in any two dimensional Euclidean wireless network with uniform transmission powers. For the analysis, we consider two popular models of ad hoc networks based on the Signal-to-Interference-and-Noise Ratio (SINR): one with opportunistic links, and the other with randomly disturbed SINR. In the former model, we show that one of our algorithms accomplishes broadcasting in $O(D\log^2 n)$ rounds, where $n$ is the number of nodes and $D$ is the diameter of the network. If nodes know a priori the granularity $g$ of the network, i.e., the inverse of the maximum transmission range over the minimum distance between any two stations, a modification of this algorithm accomplishes broadcasting in $O(D\log g)$ rounds. Finally, we modify both algorithms to make them efficient in the latter model with randomly disturbed SINR, with only logarithmic growth of performance. Ours are the first provably efficient and well-scalable, under the two models, distributed deterministic solutions for the broadcast task.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Distributed Deterministic Broadcasting in Wireless Networks of Weak Devices under the SINR Model

In this paper we initiate a study of distributed deterministic broadcasting in ad-hoc wireless networks with uniform transmission powers under the SINR model. We design algorithms in two settings: with and without local knowledge about immediate neighborhood. In the former setting, our solution has almost optimal O(Dlog2 n) time cost, where n is the size of a network, D is the eccentricity of the network and {1,...,N} is the set of possible node IDs. In the latter case, we prove an Omega(n log N) lower bound and develop an algorithm matching this formula, where n is the number of network nodes. As one of the conclusions, we derive that the inherited cost of broadcasting techniques in wireless networks is much smaller, by factor around min{n/D,Delta}, than the cost of learning the immediate neighborhood. Finally, we develop a O(D Delta log2 N) algorithm for the setting without local knowledge, where Delta is the upper bound on the degree of the communication graph of a network. This algorithm is close to a lower bound Omega(D Delta).

0 citations0 reviewsNo code linkedOpen access
preprint2008arXiv

Generalized Whac-a-Mole

We consider online competitive algorithms for the problem of collecting weighted items from a dynamic set S, when items are added to or deleted from S over time. The objective is to maximize the total weight of collected items. We study the general version, as well as variants with various restrictions, including the following: the uniform case, when all items have the same weight, the decremental sets, when all items are present at the beginning and only deletion operations are allowed, and dynamic queues, where the dynamic set is ordered and only its prefixes can be deleted (with no restriction on insertions). The dynamic queue case is a generalization of bounded-delay packet scheduling (also referred to as buffer management). We present several upper and lower bounds on the competitive ratio for these variants.

0 citations0 reviewsNo code linkedOpen access