Bogdan S. Chlebus

IJCAI Conference 2023 Conference Paper

Adversarial Contention Resolution Games

• Giorgos Chionas
• Bogdan S. Chlebus
• Dariusz R. Kowalski
• Piotr Krysta

We study contention resolution (CR) on a shared channel modelled as a game with selfish players. There are n agents and the adversary chooses some k smaller than n of them as players. Each participating player in a CR game has a packet to transmit. A transmission is successful if it is performed as the only one at a round. Each player aims to minimize its packet latency. We introduce the notion of adversarial equilibrium (AE), which incorporates adversarial selection of players. We develop efficient deterministic communication algorithms that are also AE. We characterize the price of anarchy in the CR games with respect to AE.

TCS Journal 2023 Journal Article

Flexible scheduling of transactional memory on trees

• Costas Busch
• Bogdan S. Chlebus
• Maurice Herlihy
• Miroslav Popovic
• Pavan Poudel
• Gokarna Sharma

We study the efficiency of executing transactions in a distributed transactional memory system. The system is modeled as a static network with the topology of a tree. Contrary to previous approaches, we allow the flexibility for both transactions and their requested objects to move simultaneously among the nodes in the tree. Given a batch of transactions and shared objects, the goal is to produce a schedule of executing the transactions that minimizes the cost of moving the transactions and the objects in the tree. We consider both techniques for accessing a remote object with respect to a transaction movement. In the first technique, instead of moving, transactions send control messages to remote nodes where the requested objects are gathered. In the second technique, the transactions migrate to the remote nodes where the objects are gathered to access them. When all the transactions use a single object, we give an offline algorithm that produces optimal schedules for both techniques. For the general case of multiple objects per transaction, in the first technique, we obtain a schedule with a constant-factor approximation of optimal. In the second technique, with transactions migrating, we give a k factor approximation where k is the maximum number of objects per transaction.

I&C Journal 2017 Journal Article

Doing-it-All with bounded work and communication

• Bogdan S. Chlebus
• Leszek Gąsieniec
• Dariusz R. Kowalski
• Alexander A. Schwarzmann

We consider the Do-All problem, where p cooperating processors need to complete t similar and independent tasks in an adversarial setting. Here we deal with a synchronous message passing system with processors that are subject to crash failures. Efficiency of algorithms in this setting is measured in terms of workcomplexity and communication complexity. When work and communication are considered to be comparable resources, then the overall efficiency is meaningfully expressed in terms of effort defined as work + communication. We develop and analyze a constructive algorithm that has work O ( t + p log ⁡ p ( p log ⁡ p + t log ⁡ t ) ) and a nonconstructive algorithm that has work O ( t + p log 2 ⁡ p ). The latter result is close to the lower bound Ω ( t + p log ⁡ p / log ⁡ log ⁡ p ) on work. The effort of each of these algorithms is proportional to its work when the number of crashes is bounded above by c p, for some positive constant c < 1. We also present a nonconstructive algorithm that has effort O ( t + p 1. 77 ).

TCS Journal 2016 Journal Article

Scalable wake-up of multi-channel single-hop radio networks

• Bogdan S. Chlebus
• Gianluca De Marco
• Dariusz R. Kowalski

We consider single-hop radio networks with multiple channels as a model of wireless networks. There are n stations connected to b radio channels that do not provide collision detection. A station uses all the channels concurrently and independently. Some k stations may become active spontaneously at arbitrary times. The goal is to wake up the network, which occurs when all the stations hear a successful transmission on some channel. Duration of a waking-up execution is measured starting from the first spontaneous activation. We present a deterministic algorithm that wakes up a network in O ( k log 1 / b ⁡ k log ⁡ n ) time, where k is unknown. We give a deterministic scalable algorithm for the special case when b > d log ⁡ log ⁡ n, for some constant d > 1, which wakes up a network in O ( k b log ⁡ n log ⁡ ( b log ⁡ n ) ) time, with k unknown. This algorithm misses time optimality by at most a factor of O ( log ⁡ n ( log ⁡ b + log ⁡ log ⁡ n ) ), because any deterministic algorithm requires Ω ( k b log ⁡ n k ) time. We give a randomized algorithm that wakes up a network within O ( k 1 / b ln ⁡ 1 ϵ ) rounds with a probability that is at least 1 − ϵ, for any 0 < ϵ < 1, where k is known. We also consider a model of jamming, in which each channel in any round may be jammed to prevent a successful transmission, which happens with some known parameter probability p, independently across all channels and rounds. For this model, we give two deterministic algorithms for unknown k: one wakes up a network in time O ( log − 1 ⁡ ( 1 p ) k log ⁡ n log 1 / b ⁡ k ), and the other in time O ( log − 1 ⁡ ( 1 p ) k b log ⁡ n log ⁡ ( b log ⁡ n ) ) when the inequality b > log ⁡ ( 128 b log ⁡ n ) holds, both with probabilities that are at least 1 − 1 / poly ( n ).

TCS Journal 2015 Journal Article

Broadcasting in ad hoc multiple access channels

• Lakshmi Anantharamu
• Bogdan S. Chlebus

We study broadcast in multiple access channels in dynamic adversarial settings. There is an unbounded supply of anonymous stations attached to a synchronous channel. There is an adversary who injects packets into stations to be broadcast on the channel. The adversary is restricted by injection rate, burstiness, and by how many passive stations can be simultaneously activated by providing them with packets. We consider deterministic distributed broadcast algorithms, which are further categorized by their properties. We investigate for which injection rates can algorithms attain bounded packet latency, when adversaries are restricted to be able to activate at most one station per round. The rates of algorithms we present make the increasing sequence consisting of 1 3, 3 8 and 1 2, reflecting the additional features of algorithms. We show that injection rate 3 4 cannot be handled with bounded packet latency.

TCS Journal 2007 Journal Article

Centralized asynchronous broadcast in radio networks

• Bogdan S. Chlebus
• Mariusz A. Rokicki

We study asynchronous broadcasting in packet radio networks. A radio network is represented by a directed graph, in which one distinguished source node stores a message that needs to be disseminated among all the remaining nodes. An asynchronous execution of a protocol is a sequence of events, each consisting of simultaneous deliveries of messages. The correctness of protocols is considered for specific adversarial models defined by restrictions on events the adversary may schedule. A protocol specifies how many times the source message is to be retransmitted by each node. The total number of transmissions over all the nodes is called the work of the broadcast protocol; it is used as complexity measure. We study computational problems, to be solved by deterministic centralized algorithms, either to find a broadcast protocol or to verify the correctness of a protocol, for a given network. The amount of work necessary to make a protocol correct may have to be exponential in the size of network. There is a polynomial-time algorithm to find a broadcast protocol for a given network. We show that certain problems about broadcasting protocols for given networks are complete in NP and co-NP complexity classes.

STOC Conference 2005 Conference Paper

Cooperative asynchronous update of shared memory

• Bogdan S. Chlebus
• Dariusz R. Kowalski

The Write-All problem for an asynchronous shared-memory system has the objective for the processes to update the contents of a set of shared registers, while minimizing the total number of read and write operations. First abstracted by Kanellakis and Shvartsman [12], Write-All is among the standard problems in distributed computing. The model consists of $n$ asynchronous processes and n registers, where every process can read and write to any register. Processes may fail by crashing. The most efficient previously known deterministic algorithm performs O(n 1+ε ) reads and writes, for an arbitrary fixed constant ε>0, and is due to Anderson and Woll [4]. This paper presents a new deterministic algorithm that performs O(n polylog n) read/write operations, thus improving the best previously known upper bound from polynomial to polylogarithmic in the average number of read/write operations per process. Using an approach to store and retrieve information about progress made in auxiliary registers, the novelty of the new algorithm is in using a family of multi-partite graphs with expansion properties to structure a set of registers as a graph and then have each asynchronous process explore a part of the graph according to its pattern of traversals. An explicit instantiation of our Write-All algorithm, based on best-known polynomial-time constructions of lossless expanders and a-expanding graphs, performs n • 2 O(log 3 log n) reads and writes. In this explicit solution to Write-All, the processes perform asymptotically less read/write operations than the most efficient non-explicit solution known before.

STOC Conference 2004 Conference Paper

Collective asynchronous reading with polylogarithmic worst-case overhead

• Bogdan S. Chlebus
• Dariusz R. Kowalski
• Alexander A. Shvartsman

TCS Journal 2000 Journal Article

Algorithms for the parallel alternating direction access machine

• Bogdan S. Chlebus
• Artur Czumaj
• Leszek Ga̧sieniec
• Mirosław Kowaluk
• Wojciech Plandowski

We describe a number of algorithms for the model for parallel computation called parallel alternating-direction access machine (padam). This model has the memory modules of the global memory arranged as a two-dimensional array, with each processor assigned to a row and a column, the processors can switch synchronously between row and column access modes. We study the issues of inter-processor communication and of efficient use of memory on the padam, and develop: an optimal routing scheme among memory modules, algorithms enhancing random access of processors to all memory blocks, and general simulations of shared memory machines. Finally, we present optimal algorithms for the problems of selection, merging, and sorting.

SODA Conference 2000 Conference Paper

Deterministic broadcasting in unknown radio networks

• Bogdan S. Chlebus
• Leszek Gasieniec
• Alan Gibbons
• Andrzej Pelc
• Wojciech Rytter

MFCS Conference 1996 Conference Paper

Parallel Alternating-Direction Access Machine

• Bogdan S. Chlebus
• Artur Czumaj
• Leszek Gasieniec
• Miroslaw Kowaluk
• Wojciech Plandowski

Abstract This paper presents a theoretical study of a model of parallel computations called Parallel Alternating-Direction Access Machine ( Padam ). Padam is an abstraction of the multiprocessor computers Adena /adenart and a prototype architecture usc/omp. The main feature of Padam is the organization of access to the global memory: (1) the memory modules are arranged as a 2-dimensional array, (2) each processor is assigned to a row and a column, (3) the processors switch synchronously between row and column access modes, and can access any of the assigned modules in each mode without conflicts. Since the padam processors have such a restricted access to the partially shared memory, developing tools to enhance flexibility of access to the memory is important. The paper concentrates on these issues.

MFCS Conference 1994 Conference Paper

Shorter Queues for Permutation Routing on Meshes

• Jop F. Sibeyn
• Bogdan S. Chlebus
• Michael Kaufmann 0001

Abstract New deterministic algorithms for routing permutations on an n × n MIMD mesh are presented. They are very efficient in terms of the size of auxiliary memory at each processor, measured as the maximum number of packets that need to be queued. One algorithm runs in the optimal time 2· n — 2 with a maximum queue length of 33. Another runs in the near-optimal time 2 · n + O (1) with a maximum queue length of only 12. The attained queue sizes are less than half of the previously best queue bounds. The improvements in the queue sizes are due to a new general routing scheme, a better scattering algorithm, and a new technique called spreading.

I&C Journal 1990 Journal Article

Turing machines with access to history

• Bogdan S. Chlebus

We study remembering Turing machines, that is Turing machines with the capability to access freely the history of their computations. These devices can detect in one step via the oracle mechanism whether the storage tapes have exactly the same contents at the moment of inquiry as at some past moment in the computation. The s(n)-space-bounded remembering Turing machines are shown to be able to recognize exactly the languages in the time-complexity class determined by bounds exponential in s(n). This is proved for deterministic, non-deterministic, and alternating Turing machines.

TCS Journal 1989 Journal Article

A hierarchy of propositional Horn formulas

• Bogdan S. Chlebus

A hierarchy of propositional Horn formulas is introduced. The levels σH k and ∏H k of the hierarchy are defined by way of the number of alternations between players in a certain game related to the satisfiability of Horn formulas. The satisfiability problems for formulas from a given level of the hierarchy are shown to be complete in NSPACE(log n). A certain relationship between the hierarchy and the bounded-depth circuits is exhibited. Using it we show that for some σH k and ∏H k formulas the equivalent formulas in the lower levels of the hierarchy must be exponentially longer.

MFCS Conference 1989 Conference Paper

Parallel Complexity of Lexicographically First Order Problems for Tree-Structured Graphs (Extended Abstract)

• Bogdan S. Chlebus
• Krzysztof Diks
• Wojciech Rytter
• Tomasz Szymacha

Abstract We study several P-complete graph problems and show that they are in NC if the input graphs are restricted to be tree-structured. These graphs are also known as partial k-trees, decomposable graphs or graphs of bounded tree width, and include outerplanar graphs, series-parallel graphs and Halin graphs. The particular problems investigated herein include the lexicographically first (l. f.) depth-first search tree and the l. f. maximal independent set. It is also shown that if a tree of faces of an outerplanar graph is given, then its dfs tree can be found in O(log 2 n) time using O(n/log 2 n) processors.

MFCS Conference 1988 Conference Paper

Efficient Simulations Between Concurrent-Read Concurrent-Write PRAM Models

• Bogdan S. Chlebus
• Krzysztof Diks
• Torben Hagerup
• Tomasz Radzik

Abstract We give several simple and efficient algorithms for simulations of stronger CRCW PRAMs on weaker ones. The models that we consider are the well-known PRIORITY, ARBITRARY and COMMON PRAMs, and COLLISION and COLLISION +, defined by the property that a special collision symbol is stored in each memory cell into which more than one processor attempts to write, or more than one value is attempted to be written, respectively, in a given step. Our results are the following, where n denotes the number of processors of the simulated PRAM: 1) A O (1)-time simulation between any pair of models, provided that the simulating machine has O( n log n ) processors; 2) Two n -processor simulations: of PRIORITY on ARBITRARY with O(loglog n ) slowdown, and of PRIORITY on COLLISION + with O((loglog n ) 2 ) slowdown.

MFCS Conference 1988 Conference Paper

Testing Isomorphism of Outerplanar Graphs in Parallel

• Bogdan S. Chlebus
• Krzysztof Diks
• Tomasz Radzik

Abstract It is shown that isomorphism of two outerplanar graphs with n vertices can be verified on CRCW PRAM in time O(log n ) using n processors. This improves the previous results of Ruzzo [R] and Miller & Reif [MR] concerning parallel isomorphism of trees.

TCS Journal 1982 Journal Article

On the computational complexity of satisfiability in propositional logics of programs

• Bogdan S. Chlebus

The satisfiability problems of propositional algorithmic logic and propositional dynamic logic are shown to be complete in the classes of languages accepted in polynomial space by the deterministic and alternating Turing machines respectively. Explicit upper and lower bounds on the space complexity are calculated. Exponential lower bounds on the space complexity of the satisfiability problems of these logics extended by adding a certain program connective are proved.