Max Home IndustryСложно ли параллельное программирование, и если да, что с этим делать?
Выбор подмножества столбцов является NP-полным
Балансировочная атака на блокчейны Proof-of-Work: испытательный стенд R3 в качестве примера
Иногда новости достаточно хорошо сообщаются в других местах, и нам нечего добавить, кроме как обратить на это ваше внимание.
Без комментариев — это формат, в котором мы представляем исходную информацию об источнике, слегка отредактированную, чтобы вы могли решить, хотите ли вы следить за ней.
Сложно ли параллельное программирование, и если да, что с этим делать?
Параллельное программирование важно. Сейчас и в будущем это единственный способ сделать что-либо быстрее. Каждому программисту говорят, что параллельное программирование сложно, настолько сложно, что вам действительно следует избегать его любой ценой. Затем внутри большинства из нас есть голос, который говорит: «Продолжайте, это не может быть так сложно». Прежде чем сдаться, вам, вероятно, следует прочитать этот опрос:
Цель этой книги — помочь вам запрограммировать параллельные машины с общей памятью, не рискуя своим рассудком. Мы надеемся, что принципы проектирования, изложенные в этой книге, помогут вам избежать по крайней мере некоторых ошибок параллельного программирования. Тем не менее, вы должны думать об этой книге как об фундаменте для строительства, а не как о законченном соборе.
Ваша миссия, если вы решите согласиться, состоит в том, чтобы помочь добиться дальнейшего прогресса в захватывающей области параллельного программирования — прогресса, который со временем сделает эту книгу устаревшей. Параллельное программирование не так сложно, как некоторые говорят, и мы надеемся, что эта книга сделает ваши проекты параллельного программирования проще и увлекательнее.
Короче говоря, там, где когда-то параллельное программирование было сосредоточено на науке, исследованиях и сложных проектах, оно быстро становится инженерной дисциплиной. Поэтому мы исследуем конкретные задачи параллельного программирования и описываем, как к ним подойти. В некоторых удивительно распространенных случаях их можно даже автоматизировать.
Эта книга написана в надежде, что представление инженерной дисциплины, лежащей в основе успешных проектов параллельного программирования, освободит новое поколение параллельных хакеров от необходимости медленно и кропотливо изобретать старые колеса, позволяя им вместо этого сосредоточить свою энергию и творческий потенциал на новых рубежах. Мы искренне надеемся, что параллельное программирование принесет вам, по крайней мере, столько же удовольствия, азарта и проблем, сколько оно принесло нам!
Выбор подмножества столбцов является NP-полным
Проблема выбора подматрицы S данной матрицы M, которая оптимизирует аппроксимацию AS матрицы M, важна во многих практических приложениях. Другими словами, насколько близко матрица может подойти к пространству, занимаемому всего k ее столбцов.
Если вы исправите S, то A, который оптимизирует приближение, легко вычислить, но насколько сложно найти оптимальную подматрицу. Кажется, как бы сложно это ни было:
Пусть M — вещественная матрица размера r × c, а k — натуральное число. В задаче выбора подмножества столбцов (CSSP) нам нужно минимизировать количество ∥M − SA∥, где A может быть произвольной матрицей размера k × c, а S пробегает все подматрицы размера r × k матрицы M.
Эта проблема и ее приложения в численной линейной алгебре обсуждаются уже несколько десятилетий, но ее алгоритмическая сложность остается открытым вопросом. Мы показываем, что CSSP является NP-полным.
Более того, в статье доказывается, что для рациональных матриц проблема NP-полна.
Балансировочная атака на блокчейны Proof-of-Work: испытательный стенд R3 в качестве примера
Блокчейн — это большая надежда на будущее многих приложений, которым в противном случае потребовался бы центральный доверенный орган, но это работает только в том случае, если вы можете доверять блокчейну. Это делает очень важным исследование безопасности и атак на блокчейн:
В этой статье мы идентифицируем новую форму атаки, называемую атакой баланса, на системы цепочки блоков с доказательством работы. Новизна этой атаки состоит в задержке сетевых коммуникаций между несколькими подгруппами узлов со сбалансированной мощностью майнинга.
Наш теоретический анализ фиксирует точный компромисс между задержкой в сети и мощностью майнинга злоумышленника, необходимой для удвоения затрат в Ethereum с высокой вероятностью.
Мы количественно оцениваем наш вероятностный анализ со статистикой, взятой из консорциума R3, и показываем, что одной машине требуется 20 минут для атаки на консорциум. Наконец, мы запускаем частную цепочку Ethereum в распределенной системе с настройками, аналогичными R3, чтобы продемонстрировать осуществимость подхода и обсудить применение атаки Balance к Биткойну.
Наши результаты ясно подтверждают, что основные протоколы блокчейнов с доказательством работы могут плохо подходить для блокчейнов консорциума.
Чтобы быть в курсе новых статей на I Programmer, подпишитесь на нашу еженедельную рассылку новостей, подпишитесь на RSS-канал и подпишитесь на нас в Twitter, Facebook, Google+ или Linkedin.
Комментарии
Оставьте комментарий или просмотрите существующие комментарии с помощью Disqus