|
Concurrent Reading and Writing using Mobile Agents
|
bet | 6/7 | Sana | 27.05.2022 | Hajmi | 1.92 Mb. | | #22085 |
Bog'liq taqsimlangan O‘zbekiston respublikasi oliy va o‘rta maxsus ta’lim vazirligi u, 1111 - Thirty nine silent nights went by, and on the fortieth night, gunshots were heard.
- What was going on for 39 nights?
- How many unfaithful husbands were there?
- Why did it take so long?
- W2 does not know of any other unfaithful husband.
- W2 knows that there is at least one (common knowledge)
- W2 concludes that it must be H2, and kills him on the first night.
Theorem -
- If there are N unfaithful H’s, then they will all be killed on the midnight of the Nth day.
- If you are interested to learn more, then read the original paper.
The Complexity of Distributed Algorithms Common measures - Space complexity
- How much space is needed per process to run an algorithm?
- (measured in terms of N, the size of the network)
- Time complexity
- What is the max. time (number of steps) needed to complete the
- execution of the algorithm?
- Message complexity
- How many message are exchanged to complete the execution of the algorithm?
Other measures - Bit complexity
- Measures how many bits are transmitted when the algorithm runs. It may be a better measure, since messages may be of arbitrary size.
- LOCAL and CONGEST models
- (LOCAL) In unit time, each process can send a message of arbitrarily large size to its neighbors. This ignores link congestion.
- (CONGEST) In unit time, a process can send a message of size up to O(log n) bits to each of its neighbors
- (These are variations of the synchronous message passing models)
|
| |