Two Generals problem

by Dmitry Kirsanov 27. July 2020 08:44

There is a logical problem, a thought experiment for emulating the communication over an unreliable link, called “the Two Generals’ Problem”. In case if, like most people, you never heard of it, here is the definition:

Two armies, each led by a different general, are preparing to attack a fortified city. The armies are encamped near the city, each in its own valley. A third valley separates the two hills, and the only way for the two generals to communicate is by sending messengers through the valley. Unfortunately, the valley is occupied by the city's defenders and there's a chance that any given messenger sent through the valley will be captured.

While the two generals have agreed that they will attack, they haven't agreed upon a time for attack. It is required that the two generals have their armies attack the city at the same time in order to succeed, else the lone attacker army will die trying. They must thus communicate with each other to decide on a time to attack and to agree to attack at that time, and each general must know that the other general knows that they have agreed to the attack plan. Because acknowledgement of message receipt can be lost as easily as the original message, a potentially infinite series of messages is required to come to consensus.

The thought experiment involves considering how they might go about coming to consensus. In its simplest form one general is known to be the leader, decides on the time of attack, and must communicate this time to the other general. The problem is to come up with algorithms that the generals can use, including sending messages and processing received messages, that can allow them to correctly conclude:

Yes, we will both attack at the agreed-upon time.

Allowing that it is quite simple for the generals to come to an agreement on the time to attack (i.e. one successful message with a successful acknowledgement), the subtlety of the Two Generals' Problem is in the impossibility of designing algorithms for the generals to use to safely agree to the above statement.

It’s even called a “paradox” for “inability to find a logical solution” to this problem. Because the proposed solution is to send confirmation for confirmation, and messenger could disappear.

If so many people are saying, that there is no solution, then perhaps there isn’t one, right? More...

Tags:

Other

Building social platform for everyone - a free speech utopia brainstorm

by Dmitry Kirsanov 15. May 2019 01:08

We have seen it often, with almost every known social network and platform built to express yourself - at some point it gets to a milestone which changes the platform to the opposite of its original vision.

"Don't be evil" becomes THE evil, the outlaw becomes the law enforcer, independent form alliances and neutral become ferocious fighters against neutrality. There are still islands of free speech, where borders are wide enough to call it unbiased, but they are doing it with serious personal risk and at significant expenses.

In this essay I'll try to analyse the history, trends and risks of self-expression platforms, and provide some food for thought for those who will attempt to build the next platform.

The most important aspect of this work is technology, second is sociology and third - economy. We'll scrape the law a bit, but the main premise will be that whatever you are doing is illegal somewhere, and if not - then content certainly will be. And so we'll use technology to obey the law when possible, and protect from it when it's not.

But first - let's look at existing platforms and their pitfalls. This will help us to list the known problems and caveats, and see how titans fell and why.  More...

Tags:

Analytics | Other | Social

Design Language is not Design

by Dmitry Kirsanov 7. June 2013 19:14

Last year I visited event at Dublin’s Aviva stadium, where Microsoft’s principal researcher at Microsoft Research, Bill Buxton, presented a keynote about design. Microsoft Windows Apps team was generous enough to share this video with the world, and I highly recommend it to everyone who wants to understand the concepts and reasons behind the design shift we experience today.

It’s almost 90 minutes, but they might well worth it, despite the quality.

Bill Buxton–Design Language is not Design, keynote at Aviva Stadium, Dublin

Reimagination

by Dmitry Kirsanov 13. September 2012 20:02

Alice is about to reimagine flamingoIn some future articles I am going to use this term, as well as you’ll hear it more often, because it may turn into a buzzword soon. So I’ll explain it to make sure we’re on the same page in the future.

People are habit-driven. We invent something and then we are just following the path. We are building paths for ourselves and for other people, depending from what we do. Manuals, instructions, laws and policies – these are perhaps the biggest examples of rules we make, but there are others, which you follow without consent. Why do you pour coffee before milk?

Some of the rules and habits we have are perfectly reasonable. Like when you are taking your umbrella when you are expecting showers. Or the way you are using the elevator or doing any other routine in never changing principles. However, some rules outlive the reason why they were created. More...


Month List