Loading...
Please wait, while we are loading the content...
Similar Documents
Symmetry breaking in congested models: lower and upper bounds
| Content Provider | Semantic Scholar |
|---|---|
| Author | Riaz, Talal |
| Copyright Year | 2019 |
| Abstract | A fundamental issue in many distributed computing problems is the need for nodes to distinguish themselves from their neighbors in a process referred to as symmetry breaking. Many well-known problems such as maximal independent set (mis), t-ruling set, maximal matching, and (∆ + 1)−coloring, belong to the class of problems that require symmetry breaking. These problems have been studied extensively in the local model, which assumes arbitrarily large message sizes, but not as much in the congest and k-machine models, which assume messages of size O(log n) bits. This dissertation focuses on finding upper and lower bounds for symmetry breaking problems, such as mis and t-ruling set, in these congested models. Chapter 2 shows that an mis can be computed in O( √ log n log log n) rounds for graphs with constant arboricity in the congest model. Chapter 3 shows that the t-ruling set problem, for t ≥ 3, can be computed in o(log n) rounds in the congest model. Moreover, it is shown that a 2-ruling set can be computed in o(log n) rounds for a large range of values of the maximum degree in the graph. In the k-machine model, k machines must work together to solve a problem on an arbitrary n-node graph, where n is typically much larger than k. Chapter 4 shows that any algorithm in the beep model (which assumes “primitive” single bit messages) with message complexity M and round complexity T can be simulated in Õ(M/k + T ) rounds in the k-machine model. Using this result, it is shown that mis, minimum |
| File Format | PDF HTM / HTML |
| DOI | 10.17077/etd.nwoh-93qn |
| Alternate Webpage(s) | https://ir.uiowa.edu/cgi/viewcontent.cgi?article=8520&context=etd |
| Alternate Webpage(s) | https://doi.org/10.17077/etd.nwoh-93qn |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
